General File Structure Questions

1. For the following file structures, state the conditions under which you would choose each, and provide the average number of disk accesses it would take to locate a record using it:
   • unsorted sequential file
   • sorted sequential file with random access capability
   • regular hashed file
   • table-assisted hashing file
   • dynamic hashing file
   • B-tree
   • B+ tree

Binary Search

1. The (incorrect) binary search algorithm presented in class is provided below:

      binary_search(k)
        top <- 1 
        bot <- number of records in file 
        loop 
   	mid <- floor [(top + bot) / 2]
   	get record(mid) 
   	if key(mid) = key(k) then 
   		FOUND 
   	else if key(mid) > key(k) then  
   		bot <- mid  
   	else  
   		top <- mid  
   	if top > bot then 
   		FAIL 
   	exit when FOUND or FAIL 
        end loop
   

   Correct the algorithm and explain why it might not work otherwise.

Silly

1. What liqueurs are used in the banana flambí recipe from La Perilla in Cancun?

2. How would you address someone you had just met on the beach in Greece?

3. Estimate the distance your front teeth have traveled while eating breakfast during the summer.

4. Hummus is a Lebanese dish whose main ingredient is ground chick peas. Served fresh with pita, it makes a delicious snack. However, if not properly refrigerated after preparation, all sorts of harmful bacteria can develop in the mixture. What does hummus have to do with CSC 228?

5. How would you curse someone who served you hummus that had gone bad?