22C:21 Computer Science II: Data Structures
10:3011:20 MWF, Room 106 GILH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 3193532956
Office Hours: 910 Tuesday, 11:3012:30 Wednesday, and 2:303:30 Friday.
This is the second in the sequence of core undergraduate computer science
courses and is required for all computer science majors and minors.
It builds on the first course, Computer Science I: Fundamentals (22C:16) and
and is concerned mainly with the design and implementation of data structures,
algorithms for accessing and manipulating data structures,
and the application and uses of data structures.
Java is the programming language of choice for this course, but the last programming
project will contain pieces that you will have to complete in C.
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Lecture Notes,
Sample code,
Online Resources
There are two TAs for the course: Uday Verma and Saurav Pandit.
They will lead discussion sections according to the following
schedule.
Section Time Location TA
A01 12:301:20 Th N200 LC Uday Verma
A02 8:309:20 Th 132 MH Saurav Pandit
A04 2:303:20 Th 130 SH Saurav Pandit
Note that section A03 has been cancelled due to low enrollment.
Contact information and office hours for the TAs are:
TA: Uday Verma
Office/Phone: B20J MLH, 3353650
email/home page: uverma@cs.uiowa.edu, www.cs.uiowa.edu/~uverma
Office hours: MWF 1:302:30 pm
TA: Saurav Pandit
Office/Phone: 101N MLH, 2252839
email/home page: spandit@cs.uiowa.edu, www.cs.uiowa.edu/~spandit
Office hours: TW 1:303:30 pm
Note that section A03 has been cancelled due to low enrollment.
 Problem Set 1. Problem 1 in this
set is due by 5 pm on Thursday, 1/25. Use electronic
submission.
 Problem Set 2. Problem 1 in this
set is due by 5 pm on Thursday, 2/1.
 Problem Set 3. Problem 1 in this
set is due by 5 pm on Thursday, 2/8.
 Problem Set 4. Problem 1 in this
set is due by 5 pm on Thursday, 2/15.
Some clarifications added to Problem 1 in Problem Set
4. Take a look
 Project 1. Due on 3/12.
 Problem Set 5. Problem 1 in this
set is due by 5 pm on Friday, 3/23.
 Problem Set 6. Problem 1 in this
set is due by 5 pm on Friday, 3/30.
 Problem Set 7. Problem 1 in this
set is due by 5 pm on Friday, 4/6.
 Project 2. Due on 4/27.
Extended deadline: Monday, 4/30.
 Project 1 Solution.
 Problem Set 8. Problem 1 in this
set is due by 5 pm on Friday, 4/27.
Extended deadline: Monday, 4/30.
 Problem Set 9. Problem 1 in this
set is due by noon on Tuesday, 5/8 (at final exam time).
 1/16: There will be no meetings of the discussion sections during
the first week of classes (1/151/19).
 1/18: Here is a guide to electronic
submission.
 1/22: Problem 1 in Problem Set 1
has been slightly changed. Please take another look at the Problem Set.
 1/22: Read page 3 and pages 4445 for material on exponential
functions, logarithms, binary search, and its analysis.
 1/24: Read pages 317320 on definitions related to graphs and
graph representations.
 1/29: Read the code in the myGraph class carefully.
 1/30: Discussion section A04 (which meets at 2:30 pm on Th) has been moved to 71 SH.
 1/30: The computer science department runs a "Help Lab" in 301 MLH.
You can get help on programming/problem solving there.
Go here for more help.
 2/3: The myGraph class has been updated to include
a listTriangles method (see Problem Set 2).
This was tested using graphTest.java.
 2/5: Read the code in the singly linked and doubly linked list
classes: Link.java,
LinkList.java,
and
doublyLinked.java.
 2/7: Read 169177 for material on hashing with chaining. This
shows another application of linked lists.
 2/7: See the dictionary class
for the use of hashing with chaining.
 2/13: Some clarifications added to Problem 1 in Problem Set 4. Take a look
 2/19: There is no homework due this week. Also, there will be no
quiz on Thursday, 2/22. The discussion sessions will on "Getting Started
on Project 1."
 2/19: Study the code in
GenericLink.java,
GenericLinkList.java,
GenericLinkListTester.java,
Point.java, and
PointLinkListTester.java.
Also, read Chapter 3, pages 5781.
 2/23: See my notes on Project 1 for
tips and clarifications.
 2/26: There is no homework due this week. Also, there will be no
quiz on Thursday, 3/1. The discussion sessions will answer questions
on Project 1.
 2/28: Discussion sections this week will be help sessions
for Project 1. The TAs will be available in the computer lab in MLH (301
MLH) to help students with Project 1 coding difficulties.
Attendance is optional, but if you are having trouble with some aspect of
Project 1, please go to 301 MLH during your discussion section time
and get help from your TA.
 2/28: Midterm is scheduled for Friday, March 9th at class time
(10:3011:20) and in our usual classroom (106 GILH).
 3/2: About the midterm.
 3/5: What to submit for Project 1.
 3/6: Here is the midterm review problem set.
 3/8: And here is the midterm review presented by the TAs: midterm review powerpoint.
 3/20: Our TA Saurav Pandit is sick and will not have office hours this week (3/193/23). However, his discussion sections will meet as usual.
 3/21: For the homework problem (Problem Set 5), submit two implementations of the binomial function, one in a file called
binomial.java and the other in a file called
binomialBigInteger.java.
 4/17: No discussion section this week.
 4/23: Here are some notes on
Project 2.
 4/26: Deadlines for Project 2 and Homework 8 have both been extended
to 5 pm on Monday, 4/27.
 4/26:Here is what you need to submit for
Project 2.
 Week 1: 1/151/19 Arrays and classes in Java. Brief intro. to running time. Binary search. See Record.java and
RecordDB.java.
 Week 2: 1/221/27 Twodimensional 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.
 Week 3: 1/292/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.
 Week 4: 2/52/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.
 Week 5: 2/122/16 Designing good hash functions and efficiently
computing hash values; designing flexible and userfriendly 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.
 Week 6: 2/192/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 breadthfirst traversal.
Here is a simple, arraybased 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 breadthfirst traversal, discussed in class:
bfs.
Discussion section notes: On project 1. Here are the
power point slides.
 Week 7: 2/263/2 More about breadthfirst traversal:
constructing a breadthfirst search tree and determining if a graph is
connected.
On recursion. Base cases vs recursive cases;
determining the correctness of recursive functions via proofs by induction.
Simple examples of recursion: fibonacci numbers, decimal to binary conversion.
No discussion section this week.
 Week 8: 3/53/9
Implementing divideandconquer algorithms via recursion. Merge sort
and its implementation. Showing that merge sort runs in O(n log n) rounds.
Midterm exam on 3/9.
Discussion section notes: Midterm review.
 Week 9: 3/193/23
Another divideandconquer sort: Quick sort; the partition procedure,
randomized quick sort. Here is the code for quick sort: QuickSort.java.
Using recursion to implement search with backtracking.
Depthfirst search of a graph via recursion.
Discussion section notes: On speeding up recursion by maintaining an array
of answers. Here are the power point slides.
 Week 10: 3/263/30
More on depthfirst search. Here is code for it: depthFirstSearch.
Solving the nQueens problem using search with backtracking: Queens.java.
The Priority Queue ADT. A sorted array implementation of the
Priority Queue ADT. Introduction to binary heaps.
Discussion section notes: On comparing the running times of bubble sort,
merge sort, quick sort, and randomized quick sort.
Here are the power point slides.
 Week 11: 4/24/6
Implementing a Priority Queue ADT using binary heaps.
Here is a binary heap implementation due to Lafore: heap.java.
Application of the Priority Queue ADT to Dijkstra's shortest path
algorithm.
Discussion section notes: On using an explicit stack to simulate recursion.
Here are the power point slides.
Here is the code to go with this: FibonacciTest.java
and myStack.java.
 Week 12: 4/94/13
More on Dijkstra's shortest path algorithm. Analysis and comparison with
implementation in which distances are maintained in an unordered array.
Introduction to binary search trees.
Discussion section notes: Discussion of Project 2.
Here are the power point slides.
 Week 13: 4/164/20
Implementation of binary search tree operations: INSERT,
DELETE, and SEARCH.
Tree traversals: inorder, preorder, and postorder.
Implementation of an Iterator for the BinarySearchTree class.
Here is Lafore's implementation of the BinarySearchTree class: tree.java.
No Discussion sections this week.
 Week 14: 4/234/27
Implementation of an InOrderTreeItarator class for the BinarySearchTree class.
Discussion of the Iterable and Iterator interface.
Introduction to balanced binary search trees.
AVL Trees, definitions. Insertion into an AVL tree and repairing
imbalance using rotations.
 Week 15: 4/305/4
The two cases for responding to an AVL tree insert and the three cases for
responding to an AVL tree delete.
Skip lists, a probabilistic alternative for balanced binary trees.
 Code for the class that maintains records in an ordered array, Record.java and
RecordDB.java.
 A Graph class, using adjacency matrix representation and allowing primitive operations such
as addVertex, deleteVertex, addEdge, deleteEdge, etc. myGraph.java.
 Here is the DynamicRecordDB class (solution to
a problem on Problem Set 1).
 Here is a simple linked list class (due to Lafore): Link.java
and LinkList.java.
 Here is the sparseMatrix class
and the compress function that
converts a sparse matrix into a compressed representation (see Problem 3
in Problem Set 2).
 Here is a doubly linked list class (also due to Lafore):
doublyLinked.java.
 Here is a program that shows Java I/O: TwoDArray.java
and here is a program that shows Java I/O and basic string processing: Replace.java.
 A dictionary class implemented using
hashing with chaining.
 Illustration of generic classes:
GenericLink.java,
GenericLinkList.java,
GenericLinkListTester.java,
Point.java, and
PointLinkListTester.java.
 Code for implementing and testing the trie data structure:
Node.java, Trie.java, and TestTrie.java.
 Here is a simple, arraybased 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 breadthfirst traversal, discussed in class:
bfs.

Here is the code for the version of quick sort discussed in class:
QuickSort.java.

Here is the code for the solution to the nQueens problem:
Queens.java.

Here is the code for recursive depthfirst search:
depthFirstSearch.

Here is a binary heap implementation due to Lafore: heap.java.

Here is Lafore's implementation of the BinarySearchTree class: tree.java.