22C:21 Midterm Instructions
Date: Friday, 10/17 1:30-2:20 in class
This is an open notes/book exam. Make sure you bring your class notes,
discussion section powerpoints, and printouts of code posted on the
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.
- Arrays, 2-dimensional arrays, various versions of the
RecordDB class, linear search and binary search,
running time analysis.
- Graphs, adjacency matrix representation of graphs, the
myGraph class, running time analysis of the methods
in the myGraph class.
- 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.
- Hashing and hash tables, hashing with chaining, hashing with
probing, implementation of hashing with chaining in
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.