22C:21 Computer Science II: Data Structures
1:302:20 MWF, Room 112 MH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 3193532956
Office Hours: 11:0012:20 Monday and Wednesday
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, Kajari Ghosh Dastidar and
Chris Dibbern, assigned to this course.
Their office hours and contact information are as follows:
Kajari Ghosh Dastidar B1C MLH, 3193315247 1:303:00 Tuesday, Friday kghoshda@cs.uiowa.edu
Chris Dibbern B20J MLH, 3193211442 12:201:40 Tue, 2:303:30 Th, 11:0012:00 Fri chrisdibbern@gmail.com
The TAs are responsible for leading the discussion sections
will hold 3 office hours per week to answer your questions.
 Homework 1. Posted on 8/31. Due on
Wednesday 9/10.
 Quiz1a, Quiz1b, and Quiz1c.
Given on Thursday, 9/11.
 Homework 2. Posted on 9/16. Due by 5 pm on Friday, 9/26 via ICON.
 Project 1. Posted on 10/2. Due by 5 pm on Friday, 10/24 via ICON.
 Quiz2a, Quiz2b, and Quiz2c.
Given on Thursday, 10/2.
 Quiz 3.
Given on Thursday, 10/9.
 Midterm with solutions. Given on 10/17.
Here is the midterm score distribution.
 Quiz4a and Quiz4b. Given on 10/30.
 Homework 3. Posted on 10/31. Due by 5 pm on Friday, 11/10 via ICON.
 Here is Project 1 Grading Guidelines.
 Project 2. To be posted on 11/10.
Due by midnight on Wednesday, 12/3 via ICON.
 Quiz5a and Quiz5b, and Quiz5c. Given on 11/13.
 Project 1 Solution.
 Homework 4. Posted on 12/5.
Due by 5 pm on Monday, 12/15 via ICON.
 Quiz6a and Quiz6b.
 files with sourcedestination pairs for Homework 4. Posted on 12/11.
 8/25: The first discussion sections will meet on Thursday,
8/28. The TAs will present a Java tutorial and help you get started
on Homework 1.
 8/25: On Friday the TAs will run a "help session" on the
Eclipse IDE in the computer lab (301 MLH). Times will be annouced
later. Here is the Eclipse Tutorial
they plan on using.
 8/26: The computer lab in 301 MLH has been reserved for two
"help sessions" on the Eclipse IDE.
Friday, 8/29
1:302:20 3:304:20 and Friday, 8/29 2:303:20 4:305:20.
Hope to see you at one of these.
 9/7: Quiz 1 will be held in the discussion section on 9/11.
This is open notes/books and will last for 20 minutes. Topics are (i) the
RecordDB and DynamicRecordDB classes, (ii) linear search
and binary search and their running times, (iii) adjacency matrix
representation of graphs and the myGraph class.
 9/7: The class has been activated on ICON. Future HWs (after HW1)
will have to be submitted on ICON. Also, check ICON for your grades.
 9/30: Quiz 2 will be held in the discussion section on
10/2. This is open notes/books and will last for 20 minutes. Topics are
(i) linked lists and (ii) adjacency list representation of graphs.
You will be responsible for code in the Link, LinkList,
doublyLinked, and myListGraph classes.
 10/5: Quiz 3 will be held in the discussion section on
10/9. Topics are (i) the trie data structure and (ii) hashing with probing.
 10/13: The midterm exam will be held in class on
Friday, 10/17 at the usual class time (1:302:30).
Here are instructions for the
midterm.
 10/23: You may submit a file called wordPair.java
defining a simple wordPair class as part of your Project 1
solution. This is in addition to the files listed in the Project 1
guidelines.
 10/29: Quiz 4 on Thursday, 10/30. The topics will be the Queue
and Stack ADTs, their implementations using arrays and linked lists,
breadthfirst traversal and depthfirst traversal, finding connected
components and shortest paths.
 11/12: Quiz 5 on Thursday, 11/13. The topic will be
recursion, including the examples of computing fibonacci numbers,
implementations of the "search with backtacking" paradigm in the knapsack
and nqueens problem and the "divide and conquer" paradigm in the merge
sort and quick sort algorithms.
 12/2: Quiz 6 on Thursday, 12/4. The topics are
Priority Queue ADT, binary heaps (min and max), and implementation
of Dijkstra's Shortest Path algorithm using binary heaps.
 12/2: Project 2 is due tomorrow (12/3), by midnight.
Project 2 ICON dropbox is now open.
 12/8: Quiz 7 on Thursday, 12/11. The topics are
binary search trees and operations on these trees.
 12/11: files with sourcedestination pairs for Homework 4.
You could use these input files to get a sense of how fast your program is and also how much of
a difference, your optimizations are making. The "long" files contain sourcedestination pairs that are
many hops away from each other and the "short" files contain sourcedestination pairs that
are only a few hops from each other.
 The final is on Monday, Dec 15th from noon to 2:00 pm in our classroom,
112 MH. Here is a small study guide.
 Week 1: 8/258/29 Classes and objects in Java;
arrays in Java; constructing a collection of records that supports
insert, delete, and search.
Discussion Section: Java tutorial; simple examples
of Java classes and objects, Java arrays, and Java I/O.
Week1 power point.
Links: Eclipse download,
Introduction to Java (read the notes for weeks 14), Lots of Java tutorials, Documentation for the Java Random class,
Documentation for the String class,
Eclipse Tutorial.
Sample code: Record.java,
RecordDB.java.
 Week 2: 9/19/5 Brief introduction to running time analysis;
binary search and linear search; twodimensional arrays;
adjacency matrix representation of graphs.
Discussion section: Making arrays dynamic, timing Java programs. Week2 power point.
Links: Introduction to Java (read the notes for weeks 14),
On multidimensional arrays, Lecture notes on running time of binary search.
Sample code: DynamicRecordDB.java.
 Week 3: 9/89/12 Introduction to graphs; adjacency matrix representation of graphs;
implementation of a Graph class that supports
addVertex, addEdge, deleteVertex, and deleteEdge, etc.
Discussion section: Another example of a 2dimensional data structure: TwoDArray.java.
Week 3 power point.
Quiz 1 will
be held during this discussion section. Here are the quizzes:
Quiz1a,
Quiz1b, and
Quiz1c.
Links: Wikipedia on graphs,
MathWorld on graphs,
Adjacency matrices.
Sample code: myGraph.java,
Ladders.java, TwoDArray.java.
 Week 4: 9/159/19
Introduction to dynamic data structures; linked lists; implementation
of singly linked lists and doubly linked lists;
an application of linked lists: adjacency list representation of graphs.
Discussion section: The Java Collections Framework, examples of the ArrayList and LinkedList class.
Week 4 power point.
Links: Wikipedia on Linked Lists,
Linked Lists tutorial with diagrams and Java code,
Documentation on Java's LinkedList class,
Wikipedia on adjacency list representation, NIST on adjacency lists.
Sample code: Link.java, LinkList.java
(Link.java and LinkList.java implement a singly linked list class),
doublyLinked.java (an implementation of a doublyLinkedList class), myListGraph.java
(an implementation of a graph class using the adjacency list representation).
 Week 5: 9/229/26
More on the adjacency list representation of graphs; running times of
graph class methods using the adjacency matrix representation versus using
the adjacency list representation. Clustering coefficient and how to compute it.
Discussion section: The trie data structure.
Node.java, Trie.java, TestTrie.java.
Week 5 power point.
Links:
Wikipedia on adjacency list representation, NIST on adjacency lists,
Wikipedia on hash tables,
Notes on hashing with chaining from McGill.
Sample code: StringLinkList.java,
myListGraph.java (this is the adjacency
list representation of a graph; uses StringLinkList).
 Week 6: 9/2910/2
Hashing and hash tables; hashing with chaining and hashing with probing. How to design good,
efficiently computable, hash functions. Discussion on running time of the insert, search,
and delete methods for our implementations of hash tables.
Discussion section: Slow sorting algorithms: bubble sort, selection sort, and
insertion sort. TimingSimpleSort.java, code that implements and times these sorting algorithms.
Week 6 power point.
Quiz 2 on linked lists and adjacency list representation of graphs.
Quiz 2a, Quiz 2b,
Quiz 2c.
Links:
Wikipedia on hash tables,
Notes on hashing with chaining from McGill.
Sample code: ChainingHashTable.java (implemention of hashing with chaining),
ChainingHashTableTester.java.
 Week 7: 10/610/10
Abstract Data Types, Interfaces in Java, Implementing and inheriting from interfaces, the Comparable,
Iterable, and Iterator interface, implementing a ListIterator that works with
the StringLinkList class.
Links:
Comparable interface,
Iterator interface,
Iterable interface,
Notes on using the Comparable interface,
Notes on the Comparable and Comparator interface.
Discussion Section: Overview of Project 1. Quiz 3 on (i) the trie data structure and
(ii) hashing with probing.
Week 7 power point.
Sample code: comparableRecordOld.java,
comparableRecord.java, and
comparableRecordTester.java.
 Week 9: 10/2010/24
The Queue ADTs, implementing a Queue ADT, Breadthfirst traversal on graphs and
how to implement this using queues, applications of breadthfirst traversal to shortest paths and
connected components.
Links:
Notes and an example of BFS,
More notes on BFS,
BFS in webcrawling,
BFS animation.
Discussion Section: Implementing the Queue and Stack ADT using arrays and linked lists.
Week 9 power point.
Sample code:
myListGraph.java is updated
with new methods breadthFirstSearch,
isConnected,
connectedComponents,
and shortestPath;
Queue.java, an arraybased implementation of
the Queue ADT;
allConnectedComponents.java, a program that uses the connectedComponents method
in the myListGraph class to compute all connected components of the Ladders graph,
allConnectedComponents.out, the list of
all 853 connected components of the Ladders graph;
playLadders.java, a program that uses the shortestPath method to play
the "Ladders" game; playLadders.out, output from a few runs.
 Week 10: 10/2710/31
The Stack ADT, implementing a Stack ADT, Depthfirst traversal on graphs and
how to implement this using stacks, introduction to recursion, simple examples of recursion: the power
function and fibonacci function, recursive depthfirst traversal, the search with backtracking
approach applied to other problems such as the knapsack problem.
Links:
Notes on recursion,
Wikipedia on recursion in computer science,
Wikipedia on Towers of Hanoi,
Eight Queens Puzzle from Wikipedia (with a nice picture of one possible solution),
A nice animation of recursion with backtracking for 8queens,
Wikipedia on Traveling Salesman Tour problem, Two excellent TSP games.
Discussion Section: A fast implementation of a recursive Fibonacci
function.
Quiz 4: The topics will be the Queue
and Stack ADTs, their implementations using arrays and linked lists,
breadthfirst traversal and depthfirst traversal, finding connected
components and shortest paths.
Week 10 power point.
Sample code:
Fibonacci.java,
FastFibonacci.java,
Recursive depthfirst search,
Towers.java solves the Towers of Hanoi problem,
Queens.java uses recursion
to implement "search with backtracking" to place n queens on an n by n chessboard.
 Week 11: 11/311/7: One more application of the search with backtracking paradigm: the 8queens problem.
Recursion as a means to implement the divideandconquer paradigm, two examples from sorting: merge sort and
quick sort.
Links:
Eight Queens Puzzle from Wikipedia (with a nice picture of one possible solution),
A nice animation of recursion with backtracking for 8queens,
Wikipedia on merge sort, A merge sort applet, Wikipedia on quick sort, Animation of various sorting algorithms.
Discussion Section: Call stacks, activation records, simulating
recursion using an explicit stack.
Week 11 power point.
Sample code: mergeSort.java and
QuickSort.java,
FibonacciPrint.java, and
FibonacciStack.java.
 Week 12: 11/1011/14:
The priority queue ADT; a sortedarray implementation
and an unsortedarray implementation of a priority queue ADT; running time
analysis of these implementations.
A maxheap and a minheap; an implementation of the priority queue
ADT using a maxheap. Heap sort, another sorting algorithm that runs
in O(n log(n)) time.
Links:
Binary Heaps in Wikipedia
Discussion Section: Two more examples of recursion: the Towers of Hanoi problem and the
problem of generating permutations. Quiz 5 on recursion.
Week 12 power point.
Sample code: heap.java, an implementation of a binary heap. Here is the output
from running heap.java. It shows the structure
of the heap changing as insert, delete, and
change operations are performed.
heapSort.java, an implementation of heap sort.
Code to accompany discussion section material:
Towers.java and genPerms.java.
 Week 13: 11/1711/21:
The problem of finding shortest paths in an edgeweighted graph.
Dijkstra's shortest path algorithm for single source shortest paths.
Implementing this algorithm using binary minheaps.
Links:
Dijkstra's Shortest Path Algorithm.
Discussion Section: An overview of Project 2.
Week 13 power point.
Sample code:
myWeightedGraph.java,
VertexHeap.java,
Node.java,
EdgeLinkList.java,
EdgeLink.java.
The class myWeightedGraph implements edgeweighted graphs using
an adjacency list representation.
Each linked list of neighbors is an EdgeLinkList object,
which in turn is a sequence of EdgeLink objects.
The myweightedGraph class contains a binary heap based
implementation of Dijkstra's shortest path algorithm. The corresponding
binary heap implementation is in the classes VertexHeap and
Node.
 Week 14: 12/112/5:
Finishing up the implementation of Dijkstra's shortest path algorithm.
Binary Search Trees: definitions, insert, search, and delete operations.
Running time of binary search tree operations.
Links:
Dijkstra's Shortest Path Algorithm,
Binary Search Trees from Wikipedia, a nice animation of binary search trees.
Discussion Section: Quiz 6 will be given out. Topics:
Priority Queue ADT, binary heaps (min and max), Dijkstra's shortest path
algorithm.
Sample code:
tree.java, a binary search tree class.
 Week 15: 12/812/12:
Balanced Binary Search Trees, AVL Trees, the rotation operations,
preorder, postorder, and inorder traversals.
Links:
Wikipedia on AVL Trees,
AVL Tree
animation,
Slides
on AVL trees.
Discussion Section: Tree traversals: preorder, postorder, and
inorder traversal, recursive functions for testing if a binary tree
has the binary search property, etc. Quiz 7 will be given out. Topic:
Binary Search Trees.
Sample code:
 Record.java,
RecordDB.java,
DynamicRecordDB.java
 myGraph.java,
Ladders.java, TwoDArray.java
 Link.java, LinkList.java, doublyLinked.java

StringLink.java,
StringLinkList.java,
myListGraph.java
 Node.java, Trie.java, TestTrie.java.
 TimingSimpleSort.java
 ChainingHashTable.java, ChainingHashTableTester.java
 comparableRecordOld.java,
comparableRecord.java, and
comparableRecordTester.java.
 StringLinkListIterator.java.
 Queue.java, myListGraph.java, allConnectedComponents.java,
playLadders.java.
 Fibonacci.java,
FastFibonacci.java,
Recursive depthfirst search,
Towers.java,
Queens.java.
 FibonacciPrint.java and
FibonacciStack.java.
 mergeSort.java and
QuickSort.java.
 heap.java and heapSort.java.
 myWeightedGraph.java,
VertexHeap.java,
Node.java,
EdgeLinkList.java,
EdgeLink.java.