To complete Quiz 1, fill out this form after 12:20 on Friday, Jan 5 and before 6:00PM Sunday, Jan 7.

2. Java classes, interfaces, and instances. Static vs instance methods and data members. Java vectors and enumerations. Java strings

3. Performance of data structures and algorithms: instance characteristics. operation counts. step counts.

4. Asymptotic analysis. basics of Big O, Big omega, and Big theta.

Sample questions. These are intended to be suggestive, but they
are not a comprehensive representation of the style or content of the exam.

None of them is guaranteed to appear on the exam.

Note : n^2 means n squared. Omega means the greek letter capital omega, etc.

1. Which of the following is impossible for a function f(n) to
be ?

[A] O(n^2) and Omega(n^3) [B] O(n) and O(1),
[C] Theta(3n) and Theta(4n), [D] Omega(n) and Omega(n^2).

Answer: A.

2. Let A = {a, b} and D = {d, e}. Then A X D = ?

[A] {a, b, d, e}, [B] the empty set, [C] { (a, d), (b,
e) }, [D] { (a, d), (a, e), (b, d), (b, e) }, [E] { (a, a), (b, b), (d,
d), (e, e) }

Answer: D.

3. Let S = {a, b, c}. Then which relation is reflexive on S?

[A] {}, [B] { (a, a) }, [C] { (a, b), (b, a) }, [D] { (a, b),
(a, c), (a, c) }, [E] { (a, a), (a, b), (a, c), (b, b), (c, c) }

Answer: E.

4. Let S be the same set as in the previous question and let R = { (a,
b), (b, c), (a, c) }. Consider the statement ( $x
in S ) (x, x) in R

Is this true or false?

Answer: false.

5. Write a Java function that takes a String as input and returns a
Vector of the words occuring in that string.

(Answer not given here)

6. If a set is implemented using a linked list, then what should be
the asymptotic time complexity (in terms of n, the number of elements in
the set) for worst-case behavior, for inserting a new element into the
set?

Answer: Theta(n).

2. linear lists: array and linked representations.

3. bin sort, radix sort, their time and space requirements, as well as assumptions about the data.

4. stacks.

5. sparse arrays (a.k.a. spare matrices).

6. depth-first search using a stack.

7. hashing, hash functions, collisions, linear probing, quadratic probing, rehashing, random probing.

8. trees, binary trees, binary search trees. Properties of trees: full, complete. Height and depth of nodes. Traversals and orderings of nodes.

9. AVL trees. Insertion and deletion. Single and double rotations, LR and RL rotations. Balance factors.

10. B-trees. Insertion and deletion for B-trees.

11. Graphs, directed and undirected. Degree, indegree, outdegree, paths, Euler paths.

12. Depth-first search algorithm for graphs. Breadth-first search algorithm for graphs.

Sample questions:

1. In the UNION-FIND ADT it is common to use representative elements

a. to be the keys for hashing the sets;

b. to identify the set to which some given element belongs.

Ans: b.

2. Let B be a binary relation on a set S. If B is an equivalence
relation then it must be

a. reflexive but not necessarily symmetric

b. symmetric but not necessarily symmetric.

c. reflexive, symmetric, and transitive.

d. transitive and symmetric, but not necessarily reflexive.

Ans: c.

3. Show the sequence of AVL trees obtained by inserting the following
sequence of elements into an empty tree,

with each insertion being followed by any rebalancing that might be
necessary. 17, 20, 5, 13, 2, 6, 15, 14.

4. Suppose that a B-tree of order 5 contains a root and two other internal
nodes. The maximum number of keys

it can contain is therefore....

Ans 9 (1 in the root and 4 in each child of the root).

5. In the puzzle the Seven Bridges of Konigsberg, interpreted as a multigraph,
the number of Euler paths is

Ans. 0.

6. Describe the important properties of a hash function.

Ans. It should map any of the keys in its domain to an integer
index into the hash table; it should tend to scatter the keys uniformly
into the table; it should be fast to compute.

Note: Bring a standard answer sheet and some number 2 pencils to the
second midterm.

2. Implementation of priority queues using binary heaps.

3. Heapsort.

4. Use of up-trees to implement the UNION-FIND ADT. Height rule, weight rule, path compression.

5. Minimum spanning trees for graphs.

6. Computing minimum spanning trees using Kruskal's algorithm.

7. Dynamic programming solution to the 0/1 Knapsack problem.

Sample questions:

1. Which of the following methods is part of the
Priority Queue ADT?

a. Delete-min

b. Dequeue

Ans: a.

2. Beginning with the 8 values 8,7,6,5,4,3,2,1 in elements
A[0] to A[7] of an array, create a binary heap. Assume that
A[0] is used to hold the root of the heap, the left child of
A[i] is at A[2i+1] and the right child of A[i] is at A[2i+2].

Initial tree: 8 7 6 5 4 3 2 1 Ans: 1 4 2 7 5 3 6 83. Suppose that an instance of the UNION-FIND ADT is created with n singleton subsets containing integers: {1}, {2}, ..., {n}. Suppose the implementation uses up-trees, but the UNION(x,y) operation always makes the root of the tree for x be a child of the root of the tree for y, regardless of the weights or heights of the trees. What is the maximum height that any tree can have after a sequence of UNION operations has been performed?

Ans: n-1.

4. Suppose that the height rule is used during UNION operations. Then the answer to the previous question would be...

Ans: floor( log base 2 of n). Call this function h(n), then some pairs (n, h(n)) are (1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 2), (7, 2), (8, 3), etc.

5. In an up-tree of height k, it takes O(k) time to perform a FIND without path compression. To perform the FIND with path compression takes

Ans: also O(k).

6. Given an undirected, weighted graph G with n vertices and m edges, what can we say about a minimum spanning tree for G? (Multiple choice)

a. It must exist.

b. If it exists, it must have m/2 edges.

c. If it exists, it must have n-1 edges.

d. It cannot exist.

Ans. c.

7. Kruskal's algorithm for constructing a minimum spanning tree considers the edges of G in some depth-first order starting from some arbitrary vertex of G.... true or false?

Ans. false. Kruskal's algorithm considers the edges of G in ascending order of their costs (weights).

8. Consider the following graph.

1 2 3 o------o------o------o | | | | 4| 5| 6| 7| | | | | | 8 | 9 | 10 | o------o------o------o | | | | 11| 12| 13| 14| | | | | | 15 | 16 | 17 | o------o------o------o | | | | 18| 19| 20| 21| | | | | | | | | o------o------o------o 22 23 24Give a minimum spanning tree for this graph.

Ans.

1 2 3 o------o------o------o | | | | 4| 5| 6| 7| | | | | | | | | o o o o | | | | 11| 12| 13| 14| | | | | | | | | o o o o | | | | 18| 19| 20| 21| | | | | | | | | o o o o9. Consider the 0/1 Knapsack problem with a knapsack of capacity 4 and the following available items: (A) PC with value $800 and size 2, (B) stereo with value $500 and size 1, and (C) violin with value $1200 and size 3. Show the table of maximum values that would be created by the dynamic programming method for solving this problem.

Ans:

Capacity 1 2 3 4 ________________________ Allowing A | 0 800 800 800 Allowing A,B | 500 800 1300 1300 Allowing A,B,C | 500 800 1300 1700