# 22C:21: Computer Science II: Data Structures

## On the midterm

The midterm is on Friday, March 9th, 10:30-11:20 (usual class time) in 106 GILH (usual classroom). It is open notes/textbook and you are free to bring printouts of code posted on the coursepage or from elsewhere on the internet.

There will be three problems and each problem will have 2-3 parts. 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 topics covered in class and the corresponding material in the textbook and on the course page. You are responsible for reading/knowing all of the material mentioned below.

• Week 1: 1/15-1/19 Arrays and classes in Java. Brief intro. to running time. Binary search. See Record.java and RecordDB.java.

• Week 2: 1/22-1/27 Two-dimensional arrays. Adjacency matrix representation of graphs. Implementation of a graph class. See myGraph.java.
Discussion section notes: on dynamic arrays and amortized analysis: power point slides.
Text book: Pages 317-320 on graphs and representations of graphs.

• Week 3: 1/29-2/2 More on the graph class methods (see myGraph.java). Introduction to linked lists (see Link.java and LinkList.java).
Discussion section notes: on sparse matrices and compressed representations of these. Here are power point slides and code: sparseMatrix class and compress.
Text book: Pages 57-60 the List ADT and implementations of the List ADT.

• Week 4: 2/5-2/9 Singly linked lists, doubly linked lists, and applications to adjacency list representation of graphs and hashing with chaining.
Discussion section notes: on adjacency list representation of graphs. Here are power point slides and code: myListGraph class.
Text book: Section 3.5 on implementation of LinkedLists.

• Week 5: 2/12-2/16 Designing good hash functions and efficiently computing hash values; designing flexible and user-friendly data structures using Java generics.
Discussion section notes: on the trie data structure. Here are the power point slides and here is the code: Node.java, Trie.java, and TestTrie.java.
Text book: Sections 5.1, 5.2, and 5.3 on hashing, hash functions, and hashing with chaining. Sections 1.4 and 1.5 on Java Generics Pre Java 5 and with Java 5.

• Week 6: 2/19-2/23 Some Java features: interfaces, inheritance from interfaces and the Comparable interface. Study the code in GenericLink.java, GenericLinkList.java, GenericLinkListTester.java, Point.java, and PointLinkListTester.java for examples of these concepts. The Queue ADT and its application to breadth-first traversal. Here is a simple, array-based implementation of the Queue ADT: queue.java and here is a generic version of that along with a tester program: GenericQueue.java, GenericQueueTester.java. Here is the code for breadth-first traversal, discussed in class: bfs.
Discussion section notes: On project 1. Here are the power point slides.
Text book: Sections 3.3 and 3.4 on the Java Collections API and the ArrayList implementation the List ADT. Section 3.7 on the Queue ADT.

• Week 7: 2/26-3/2 More about breadth-first traversal: constructing a breadth-first search tree and determining if a graph is connected. The Stack ADT. Introduction to recursion; using induction to verify correctness of recursive functions; simple examples such as Fibonacci numbers and conversion-to-binary.
Discussion section notes: No discussion section meetings this week.
Text book: Sections 3.6 on the Stack ADT. Section 1.3 on recursion