22C:21 Computer Science II: Data Structures
10:30-11:20 MWF, Room 112 MH
Sriram V. Pemmaraju
101G MLH, firstname.lastname@example.org, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 2:30-3: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.
Information about TAs,
Quizzes, Projects, and Exams,
There are two TAs, Fang Yang and
D. Ezra Sidran, assigned to this course.
Their office hours and contact information is as follows:
101N MLH, 335-2839
Wednesday 2:00-3:30PM, Thursday 10:00-11:30AM
D. Ezra Sidran
101 N MacLean Hall, 335-2839
Tuesdays 2:30-4:30, Thursdays 2:30-3:30
The TAs are responsible for leading the discussion sections
will hold 3 office hours per week to answer your questions.
- Homework 1. Due by lab time on 9/6. Solution: TwoRolls.java, twoRolls.pdf
- Quiz 1. 8/30. Solution: ImprovedRandomTest.java
- Homework 2. Due by lab time on 9/13.
- Quiz 2 (12:30 section), Quiz 2 (3:30 section) 9/6.
- Homework 3. Due by lab time on 9/20. Solution: CRS.java,
CRSTester.java, and CRS.pdf.
- Quiz 3 (12:30 section), Quiz 3 (3:30 section) 9/13,
updated CRS.java with solutions to Quiz 3.
- Homework 4. Due by lab time on 9/27. Solution: connectedComponents.java.
- Quiz 4 (12:30 section), Quiz 4 (3:30 section) 9/20, updated
myGraph.java and Ladders.java with solutions
to Quiz 4.
- Project 1. Due by lab time on 10/18. Project 1 Solution.
- Homework 5. Due by lab time on 10/4. City.java contains the solution.
- Quiz 5 (12:30 section), Quiz 5 (3:30 section), updated
LinkList.java with solutions to Quiz 5.
- Quiz 6 (12:30 section), Quiz 6 (3:30 section).
- Homework 6. Due by lab time on 10/18. myListGraph.java has been updated with solution;
also see playLadders.java and playLadders.out.
- Quiz 7 (12:30 section and 3:30 section): hash.java contains the solution.
- Homework 7. Due by lab time on 10/25.
- Quiz 8 (12:30 section) and Quiz 8 (3:30 section). myListStack.java contains the solution.
- Midterm Exam with solution.
- Homework 8. Due by lab time on 11/1. Here is output from my solution to this homework.
This reads mileage lines from miles.dat correctly.
- Project 2. Due on 11/15. MST for the 128 cities in miles.dat. Solution.
- Quiz 9 (12:30 section and 3:30 section).
- Homework 9. Due by lab time on 11/8. Solution: MST.java.
- Quiz 10 (12:30 section and 3:30 section).
- Quiz 11 (12:30 section and 3:30 section).
- Homework 10. Due by lab time on 11/29. Partial Solution: VertexHeap.java, Node.java, HeapApp.java, HeapApp.out.
- Project 3. Due on 12/13.
- Homework 11. Due by lab time on 12/6.
- Week 1: 8/27-8/31 Classes and objects in Java;
arrays in Java; constructing a collection of records that supports
insert, delete, and search.
Lab topic: Introduction to the Eclipse IDE; simple examples
of Java classes and objects, Java arrays, and Java I/O. Lab 1 Document.
Quiz and Homework: Quiz 1,
Homework 1 (due by lab time on 9/6).
Links: Eclipse download,
Introduction to Java (read the notes for weeks 1-4), Lots of Java tutorials, Documentation for the Java Random class,
Documentation for the String class.
Sample code: Record.java,
- Week 2: 9/3-9/7 Brief introduction to running time analysis;
binary search and linear search; two-dimensional arrays.
Lab topic: Making arrays dynamic. Lab 2 Document, Lab 2 Powerpoint slides.
Quiz and Homework: Quiz 2 (12:30 section), Quiz 2 (3:30 section),
Homework 2 (due by lab time on 9/13).
Links: Introduction to Java (read the notes for weeks 1-4),
On multi-dimensional arrays.
Sample code: DynamicRecordDB.java,
CRS.java (solution to Lab 3 and Quiz 3 problems).
- Week 3: 9/10-9/14 Introduction to graphs; adjacency matrix representation of graphs;
implementation of a Graph class that supports
addVertex, addEdge, deleteVertex, and deleteEdge, etc.
Lab topic: Compressing 2-dimensional arrays. Lab 3 Document,
CRS.java (solution to Lab 3 problem),
Lab 3 powerpoint.
Quiz and Homework: Quiz 3 (12:30 section), Quiz 3 (3:30 section),
Homework 3 (due by lab time on 9/20).
Links: Wikipedia on graphs,
MathWorld on graphs,
Sample code: myGraph.java,
- Week 4: 9/17-9/21 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.
Lab topic: Computing the clustering oefficient. Lab 4 Document,
Updated myGraph.java with clustering coefficient computation,
Ladders.java (run Ladders and look at the output).
Quiz and Homework: Quiz 4 (12:30 section), Quiz 4 (3:30 section),
Homework 4 (due by lab time on 9/27).
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),
Updated myGraph.java with clustering coefficient computation.
- Week 5: 9/24-9/28
More on the adjacency list representation of graphs;
another application of linked lists: hashing with chaining.
designing good hash functions and efficiently
Lab topic: Making a more sophisticated LinkedList class. Lab 5 Document. Link.java, LinkList.java have been updated for Lab 5.
Quiz and Homework: Quiz 5 (12:30 section), Quiz 5 (3:30 section),
Homework 5 (due by lab time on 10/4).
Wikipedia on adjacency list representation, NIST on adjacency lists,
Wikipedia on hash tables,
Notes on hashing with chaining from McGill.
Sample code: Link.java, LinkList.java, StringLink.java,
myListGraph.java (this is the adjacency
list representation of a graph; uses StringLinkList).
- Week 6: 10/1-10/5
Designing good hash functions and efficiently computing hash values.
Abstract data types (ADTs); the queue and stack ADTs;
Lab topic: Comparing the simple sorting algorithms: Lab 6 Document. TimingSimpleSort.java implements
bubble sort, selection sort, and insertion sort and times these.
Quiz and Homework: Quiz 6 (12:30 section), Quiz 6 (3:30 section), Homework 6.
Wikipedia on hash tables,
Notes on hashing with chaining from McGill.
Sample code: TimingSimpleSort.java implements
bubble sort, selection sort, and insertion sort and times these;
hashing with chaining;
Queue.java is an array-based implementation of the Queue ADT;
myStack.java is an array-based implementation of the Stack ADT.
- Week 7: 10/8-10/12
Graph traversals, algorithm for breadth-first search (BFS),
implementing BFS using a queue; constructing BFS trees; applications of BFS;
Lab topic: Implementing hashing with chaining: Lab 7 Document, Dictionary.java implements
hashing with chaining, Dictionary.out,
showing the distribution of linked list sizes.
Quiz and Homework: Quiz 7 (12:30 and 3:30 section),
no homework this week.
Notes and an example of BFS,
More notes on BFS,
BFS in web-crawling,
Sample code: myListGraph.java is updated
with new methods breadthFirstSearch,
Queue.java, an array-based 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 8: 10/15-10/19
Introduction to recursion. Simple examples (fibonacci numbers, power function,
Lab topic: Implementing the Stack ADT: Lab 8 Document, myStack.java implements
a Stack ADT.
Quiz and Homework: Quiz 8 (12:30 section), Quiz 8 (3:30 section), Homework 6.
Notes on recursion,
Wikipedia on recursion in computer science,
Wikipedia on Towers of
Recursive depth-first search,
Towers.java solves the Towers of Hanoi problem.
- Week 9: 10/22-10/26
Using recursion to implement search with backtracking;
solving the 8-queens problem; solving the traveling salesman problem.
Lab topic: Implementing a fast, recursive, Fibonacci function: Lab 9 Document, Fibonacci.java implements
the standard, slow, Fibonacci function and FastFibonacci.java implements a modified version of this
that runs at lightning speed, despite being recursive. Output of FastFibonacci may convince you.
Quiz and Homework: Quiz 9 (12:30 and 3:30 sections), Homework 7.
Links: Eight Queens Puzzle from Wikipedia (with a nice picture of one possible solution),
A nice animation of recursion with backtracking for 8-queens,
Wikipedia on Traveling Salesman Tour problem, Two excellent TSP games.
Sample code: Queens.java uses recursion
to implement "search with backtracking" to place n queens on an n by n chessboard.
- Week 10: 10/29-11/2
Recursive implementation of divide-and-conquer algorithms:
Merge sort and Quick sort.
Running time analysis of these algorithms, randomized Quick sort.
Implementing weighted graph class: Lab 10 Document,
implement a linked list that can keep track of neighbors as well as the weights
of edges to the neighbors.
Quiz and Homework: Quiz 10 (12:30 and 3:30 sections), Homework 8.
Links: Wikipedia on merge sort, A merge sort applet, Wikipedia on quick sort, Animation of various sorting algorithms.
Sample code: mergeSort.java and
- Week 11: 10/29-11/2
More on quick sort;
activation records, activation stacks, and implementing recursion using
an explicit stack.
The priority queue ADT; a sorted-array implementation
and an unsorted-array implementation of a priority queue ADT; running time
analysis of these implementations.
Activation records, activation stack, and implementing recursion using an explicit stack.
Lab 11 Document,
Quiz and Homework: Quiz 11 (12:30 and 3:30 sections), Homework 9.
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.
- Week 12: 11/5-11/9
A max-heap and a min-heap; an implemntation of the priority queue
ADT using a max-heap.
Heap sort, Lab 12 Document, heapSort.java.
Sample code: An enhanced min-heap implementation that can be used in Prim's Algorithm and in
Dijkstra's Algorithm: Node.java, VertexHeap.java,
- Week 13: 11/12-11/16
Implementing Prim's MST algorithm and Dijkstra's shortest path algorithm using
- Week 14: 11/26-11/30
Binary search trees;
implementation of binary search tree operations: search, insert,
Tree traversals: in-order, pre-order, and post-order.
Implementation of a binary search tree iterator.
Binary Search Trees, Lab 13 Document, tree.java.
- Week 15: 12/3-12/7
Introduction to balanced binary search trees;
AVL Trees: definitions; insertion into an AVL tree and repairing
imbalance using rotations;
the two cases for responding to an AVL tree insert and the three cases for
responding to an AVL tree delete.
AVL Trees, Lab 14 Document, AVLNode.java, AVLTree.java,