22C:21 Midterm Instructions

This is an open notes/book exam. Make sure you bring your class notes, discussion section powerpoints, and printouts of code posted on the course page. The exam is worth 20% of your grade and will be graded out of 200 points.

There will be 5 problems on the exam, each problem worth 40 points. The solutions will involve writing code fragments (4-5 lines maximum) or short answers (2-3 sentences maximum) explaining the behavior of some given algorithm, code fragment, or data structure.

Here is a list of the topics covered by each problem.

1. Arrays, 2-dimensional arrays, various versions of the RecordDB class, linear search and binary search, running time analysis.

2. Graphs, adjacency matrix representation of graphs, the myGraph class, running time analysis of the methods in the myGraph class.

3. Singly linked lists, doubly linked lists, implementations of these in the LinkList class and the doublyLinked class, running time analysis of the methods in these classes.

4. Hashing and hash tables, hashing with chaining, hashing with probing, implementation of hashing with chaining in ChainingHashTable class.

5. The Comparable, Iterable, and the Iterator interface, using these interfaces and building objects that are comparable using the compareTo method and building iterators for data structures.