22C:21 Computer Science II: Data Structures

10:30-11:20 MWF, Room 106 GILH

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 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.

Syllabus document, Information about TAs, Announcements, Quizzes, Projects, and Exams, Lecture Notes, Sample code, Online Resources

Information about TAs

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:30-1:20 Th		N200 LC			Uday Verma	
A02             8:30-9:20 Th		132 MH			Saurav Pandit	
A04             2:30-3: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, 335-3650
	e-mail/home page: uverma@cs.uiowa.edu, www.cs.uiowa.edu/~uverma
	Office hours: MWF 1:30-2:30 pm

	TA: Saurav Pandit
	Office/Phone: 101N MLH, 225-2839
	e-mail/home page: spandit@cs.uiowa.edu, www.cs.uiowa.edu/~spandit
	Office hours: TW 1:30-3:30 pm

Note that section A03 has been cancelled due to low enrollment.

Quizzes, Projects, and Exams

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).

Announcements

1/16: There will be no meetings of the discussion sections during the first week of classes (1/15-1/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 44-45 for material on exponential functions, logarithms, binary search, and its analysis.
1/24: Read pages 317-320 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 169-177 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 57-81.
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:30-11: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/19-3/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.

Weekly Topics and Some Lecture notes

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.
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.
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.
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.
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.
Week 7: 2/26-3/2 More about breadth-first traversal: constructing a breadth-first 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/5-3/9 Implementing divide-and-conquer 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/19-3/23 Another divide-and-conquer 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. Depth-first 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/26-3/30 More on depth-first search. Here is code for it: depthFirstSearch. Solving the n-Queens 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/2-4/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/9-4/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/16-4/20 Implementation of binary search tree operations: INSERT, DELETE, and SEARCH. Tree traversals: in-order, pre-order, and post-order. 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/23-4/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/30-5/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.

Sample code

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, 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.
Here is the code for the version of quick sort discussed in class: QuickSort.java.
Here is the code for the solution to the n-Queens problem: Queens.java.
Here is the code for recursive depth-first search: depthFirstSearch.
Here is a binary heap implementation due to Lafore: heap.java.
Here is Lafore's implementation of the BinarySearchTree class: tree.java.

Online Resources

Past offerings of the course: Fall 2003, Fall 2004, Fall 2005, and Spring 2006.
General Unix resources: UNIX Help, Commonly used UNIX commands.
Unix editors: Introduction to vi, Introduction to emacs.
Java Tutorials.
Cool animation of different sorting algorithms. Check out bubble sort vs quick sort.