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