week 1

Question 1

hash function takes as argument§

Answer 1

hash key

Question 2

hash function has as output

Answer 2

bucket number

Question 3

task hash key

Answer 3

send approx equal amount of hask keys to each of B buckets (uniformly distributed into buckets)

Question 4

not good wehn B has…

Answer 4

common factor with most hash keys, non random distribution

Question 5

choose b to be

Answer 5

prime

Question 6

if hash key string

Answer 6

hash(sum(ascii_code(character in string field))) and do procedure as previously

Question 7

index

Answer 7

data structure that makes it efficient to retrieve objects, given the value of >=1 elements of those objects

Question 8

objects

Answer 8

= records

Question 9

index is build on..

Answer 9

one of fields of record. given v of that field -> retrieves all records having value v in field

Question 10

index implementation=

Answer 10

hash table

Question 11

hash table

Answer 11

hash keys: field/fields on which indexing is done
records placed in buckets determined by hash function
given hash key -> hash it -> find bucket -> search in bucket for records with that value of hash key

Question 12

disk is organized in

Answer 12

blocks

Question 13

main memory is organized in

Answer 13

words

Question 14

want to do computations in

Answer 14

main memory

Question 15

blocks:

Answer 15

minimum uunits that OS moves to/from main memory

Question 16

how much slower is it to read a disk block

Answer 16

it takes 10 ms, at least 5 order of magnitutes (factor of 10^5) slower than time taken to read a word (32 bits, block 64kbytes)

Question 17

Define a hash-function for an index containing objects records with two fields, one of type string, and one of type integer.

Answer 17

hash(record(string_field, integer_field) = hash(string_field) + hash(integer_field)
hash(string_field) = hash(sum(ascii_code(character in string field)))
For both hashing the string field and hashing the integer field the following hash function is used: hash(integer) = integer mod B, where B is prime (this last condition is necessary as we do not know the range of the hash-keys).

Question 18

What is a regular expression? Give examples of at least three regular expression operators.

Answer 18

A regular expression is a special string used to define string patterns. It uses characters and operators as “|”, “*”, “+”, etc., to denote disjunction, repetition, repetition at least one time, etc.