Assignemnt

1. Running time and asymptotic notations.

(a) If an algorithm's running time can be expressed as a function f (n) = √n+log nⁿ, then which one of the following is NOT a correct bound for the running time?
a. O(n²)
b. O(√n)
c. O(log nⁿ)
d. ?(n)

(b) Assume an algorithm runs in Θ(n²), then which one of the following asymptotic notations do not apply?

a. O(n³)
b. O(n²)
c. O(n)
d. ?(n²)

(c) Sort the following functions based on their growth rates, from the least to the greatest. Underline those functions that have the same asymptotic bound.

2^n/2, loge n, n log n, n!, 2ⁿ, log₂ n², √n

2. Basic Data Structures.

(a) Which one of the following statements are true for linked lists, assuming there is only one entry point to the list (i.e. Head)?
a. It takes linear time to insert an element in the front of a list.
b. It takes linear time to insert an element in the end of a singly circular list.
c. It takes linear time to insert an element in the end of a doubly non-circular list.
d. It takes linear time to insert an element in the end of a doubly circular list.

(b) If we read a sequence of items < A, B, C, D, E, F > from a file and some of the items are pushed and popped, which one of the following stacks is possible? Assume that each item can only be pushed into the stack once.

a. top < D, E, F > bottom
b. top < F, C, A > bottom
c. top < C, D, E > bottom
d. top < E, D, F > bottom

(c) When using open-addressing in hash tables, we need to decide the table size m and some parameters so that the table can be fully utilized. What does that actually mean?
a. Allocate a table with size m equal to the number of elements stored.
b. Decide m and other parameters so that for any element, the initial m probe positions are distinct.
c. Decide m and other parameters to reduce the probability of collisions.
d. Decide m and other parameters so that no collision could happen.

(d) If a sequence of keys arrives in this order: < 22, 38, 7, 70, 46 >, suc- cessively insert each of them into the following tables, using all three of the open- addressing methods. Assume the primary hash function is h1(k) = k mod 8, the secondary hash function

and the constants for quadratic probing are c₁ = c₂ = 1/2.

(a) What are the sequence of AVL trees created after inserting each character in the list < j, i, h, g, f, e, d, c, b, a > to an initially empty AVL tree? Note: please draw only one tree after each insertion.

(b) From the AVL tree you have built in part (b), what are the sequence of trees after deleting each character in the list (i.e., delete j , delete i, ...)? Note: please draw only one tree after each deletion.

4. Priority Queues. Using a Max-Heap to implement a Priority Queue requires a procedure to decide the relative order of events in queue. An event a has a higher priority than another event b if a's priority value > b's priority value. If both a and b have the same priority, then the event with earlier arrival time has a higher priority. Two events cannot arrive at the same time. Write a pseudo-code procedure called Compare to decide the relative order of two events.

Compare(a, b) // both a and b are events
// a.priority, b.priority: their priority values.
// a.time, b.time: arrival time (earlier time has a smaller numeric value)
// return 1 if a has a higher priority than b; Otherwise, return -1

5. Recursion in Tree Structures. Given a binary tree, write a pseudo-code procedure to calculate the weight of the tree (sum of the weights of all edges in the tree). Let w(u, v) denote the weight of the edge (u, v), where u is the parent of another node v.

Tree-Weight(x) // x is the root of the tree

6. Graph Algorithms. Given the directed graph below:

(a) find the sequence of vertices visited in a BFS search if 6 is the source vertex.

(b) find the sequence of vertices visited in a DFS search if 6 is the source vertex.