Subject : Computer Algorithms

Book: Introduction to Algorithms 3rd edition

1)

a) Using Figure 10.1 as a model, illustrate the result of each operation in the sequence PUSH(S,6), PUSH(S,2), PUSH(S,8), POP(S), PUSH(S,5), PUSH(S,3), POP(S), POP(S), and PUSH(S,1), on an initially empty stack S stored in array S[1..6].

b) Using Figure 10.2 as a model, illustrate the result of each operation in the sequence ENQUEUE(Q,6), ENQUEUE(Q,2), ENQUEUE(Q,8), DEQUEUE(Q), ENQUEUE(Q,5), ENQUEUE(Q,3), DEQUEUE(Q), DEQUEUE(Q), and ENQUEUE(Q,1), on an initially empty queue Q stored in array Q[1..6].

2)

a) What is the difference between arrays and lists?

b) What are the pros and cons of storing data in arrays and/or lists?

c) You are given 7 Giga Bytes worth of data that must be loaded in memory in a computer with 8GB of RAM. Which data structure would use: an array or a list? Why?

d) You are given 1 Giga Byte worth of data that must be loaded in memory in a computer with 8GB of RAM and to be used mainly by a binary-search algorithm. Which data structure would use: an array or a list? Why?

e) You are given 1 Giga Byte worth of data that must be loaded in memory in a computer with 8GB of RAM and to be used mainly by a membership keeper algorithm from a nationwide gym. Which data structure would use: an array or a list? Why?

3) Demonstrate what happens when we insert the keys {7,8,29,14,10,31,0,13,12,17,18,20} into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k)=k mod 9.