## CSE 373: Exams (Winter 2001)

### Quizzes

One or more short quizzes may be given from time to time for the purpose of assessing student understanding and currency in the course material. Advance notice of these quizzes may or may not be given. Some of these may count towards the course grade.

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

### Midterms

Two midterms are scheduled. Midterm 1 will be on January 26, and Midterm 2 will be on February 26.

#### Midterm Examination 1 will cover the following topics:

1. set notation. cartesian products. element of, subset of. binary relations. reflexive, symmetric, and transitive properties. logical notation with FORALL and THERE EXISTS. AND, OR, NOT, IMPLIES. operations as functions mapping from a space of argument tuples to a range.
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).

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) }

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) }

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?

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

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?

#### Midterm Examination 2 will cover the following topics:

1. equivalence relations and the UNION-FIND abstract data type.  Application of UNION-FIND to finding the common electrical nodes in a circuit, given a wire list.
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.

### Final

The final examination for the course is scheduled for Wednesday, March 14, from 2:30PM to 4:20 PM. Any student anticipating a conflict with this time must immediately notify the instructor and may be required to drop the course.

#### The final exam will cover not only the material listed for midterms 1 and 2 but also the following topics:

1. Priority queues.
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
8
```
3. 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     24
```
Give 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      o

```
9. 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
```