22C:21 Computer Science II: Data Structures

10:30-11:20 MWF, Room 109 EPB

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11:30 to 12:30 on MW, 9:30 to 10:30 on F

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 courses, 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.

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

Information about TAs

There are three TAs for the course: Alankar Kampoowale, Yan Wang, and Zhihong Wang. They will lead one discussion section each.

Section         Time                    Location                TA
A01             12:30-1:20 Tuesday      C29, PC			Alankar Kampoowale
A02             2:30-3:20 Thursday	71 SH			Zhihong Wang	
A04             3:30-4:20 Thursday    	210 MLH 		Yan Wang

Contact information and office hours for the TAs is as follows.

Name			Office	Phone		e-mail			Office hours
Alankar Kampoowale	B20J	335 3650	akampoow@cs.uiowa.edu	12-1, MW
Zhihong Wang		301 MLH	TBA		zhihwang@cs.uiowa.edu	2-3, WF
Yan Wang		B20J	335 3650	ywang4@cs.uiowa.edu	1:30-2:30 T, 2:30-3:30 Th

Quizzes, Projects, and Exams

Homework 1 posted; due on 9/7 in class.
Solution to Homework 1.
Homework 2 posted; due on 9/23 in class.
Project 1 posted; due at midnight 10/17.
Solution to Homework 2.
Homework 3 posted; due on 10/14 in class.
Solution to Homework 3.
Solution to the midterm exam.
Solution to the Project 1.
Project 2: Part I. Due at midnight, 10/31.
Project 2: Part II. Due back on 11/7, midnight.
Solution to the Project 2.1.
Project 2: Part III. Due back on 11/15, midnight.
Solution to the Project 2.2.
Homework 4. Due on 11/28.
Project 3. Due on 12/14.

Announcements

There will be no meetings of the discussion sections in the first week of classes (8/22-8/26).

Reading for week 1, 8/22-8/26: Chapter 1, Chapter 2 (62-72).

Discussion section topic, week 2, 8/29-9/2: Overview of 1-dimensional arrays, resizing arrays

Reading for week 2, 8/29-9/2: all of Chapter 2.

Discussion section topic, week 3, 9/5-9/9: Multi-dimensional arrays

Homework 1 posted; due on 9/7 in class.
Reading for week 3, 9/5-9/9: Chapter 6 (on recursion).
Solution to Homework 1 posted.
Discussion section topic, week 4, 9/12-9/16: The Vector class from the Java collections
Reading for week 4, 9/12-9/16: Merge Sort (pp 279-294, Chapter 6) and Quick Sort (pp 325-357, Chapter 7)
Homework 2 posted; due on 9/23 in class.
Project 1 posted; due at midnight 10/17.
Reading for week 5, 9/19-9/23: Quick Sort (pp 325-357) and Graphs (Chapter 13, pages 615-623).
Reading for week 6, 9/26-9/30: Graphs (Chapter 13, pages 615-623) and depth first graph traversal (pages 623-636).
Midterm (open notes/book) on 10/14, Friday, in class. Here are more details.
Solution to Homework 2 posted.
Suggestions/Clarifications for Project 1.
Homework 3 posted; due on 10/14 in class.
How to electronically submit your project. You will need to do this from a CS department machine.
This week (10/10-10/14) the TAs will do a midterm exam review in the discussion sections.
There is no class on Monday, 10/17. Project 1 is due by midnight on Monday, 10/17.
Solution to Homework 3 posted.
Solution to the midterm exam posted.
Solution to the Project 1 posted. Feel free to use this code in Project 2.
Project 2: Part I posted. Due back on 10/31, midnight. Part II will be posted this week.
This week (10/24-10/28) the TAs will discuss doubly linked lists in the discussion sections.
Older compilers are having trouble compiling myGraph.java because it uses generics. Here is a version of myGraph.java that does not use generics and should compile fine on older compilers as well. It is the same as myGraph.java except for two lines of code in the depth first traversal function.
The submission folder for project2.1 is now ready. Project2.1 is due on Monday, 10/31, by midnight.
Grades so far. Please report any errors you find.
Project 2: Part II posted. Due back on 11/7, midnight. Part III will be posted this week.
Concerning Project 2.1: there is no way to implement the getNeighbors function in the myGraph class without making further modifications to the LinkList class. What I said in class on Monday (10/31) is incorrect. Please submit the modified LinkList class as well. Due to the confusion caused by this, the deadline for Project 2.1 is extended to Tuesday, 11/1, midnight.
Clarifications for Project 2.2.
Project 2.2 submission directory is now open.
Project1 grades. If you want an explanation, please contact our TA, Yan Wang.
Project 2.1 is due at midnight on Tuesday, 11/8.
Project 2: Part III is posted. Due back on 11/15, midnight.
Clarifications for Project 2.3.
Homework 4 is posted. Due on 11/28.
Project 3 is posted. Due on 12/14.
Final exam details. Final exam is on Thursday, Dec 15th, 7:30am-9:30am, in 107 EPB.

Weekly Topics and Lecture notes

Week 1 (8/22-8/26): Run-time analysis and the "Big Oh" notation. Wednesday 8/24 and Friday 8/26
Week 2 (8/29-9/2): Slow sorting algorithms (bubble sort) and recursion. Monday 8/29, Wednesday 8/31, and Friday 9/2.
Week 3 (9/5-9/9): Recursion and faster sorting algorithms (merge sort). Wednesday 9/7, material covered on Friday, 9/9 appears in the textbook, pages 279-294.
Week 4 (9/12-9/16): Divide and conquer, merge sort (continued), and quick sort, material covered this week appears in the textbook, pages 325-357.
Week 5 (9/19-9/23): Improving the running time of quick sort (median-of-3 rule, randomization), graphs, adjacency matrix representation.
Week 6 (9/26-9/30): The myGraph class, primitive operations such as addVertex, addEdge, deleteVertex, deleteEdge, and getNeighbors. See myGraph.java.
Week 7 (10/3-10/7): Graph traversal, depth-first traversal using the Stack data structure, building a depth first traversal tree, using the depth first traversal tree to answer questions on connectivity and paths between pairs of vertices. See dfs1.java and dfs2.java.
Week 8 (10/10-10/14): A simple array based implementation of the Stack data structure, recursive implementation of depth first traversal, analysis of depth first traversal.
Week 9 (10/17-10/21): Linked lists. See Lafore's Link class and his LinkList class.
Week 10 (10/24-10/28): Applications of linked lists: adjacency list representation, hashing with chaining.
Week 11 (10/31-11/4): More on hashing: using chaining to avoid collisions, some thumb rules for picking good hash functions, efficient implementation of hash functions. Read Chapter 11 (pages 519-528, 552-574).
Week 12 (11/7-11/11): Priority queue ADT, binary heaps. Read Chapter 12.
Week 13 (11/14-11/18): Dijkstra's shortest path algorithm. Read pages 687-707 from Chapter 14. Also, read Project 3 handout.
Week 14 (11/28-12/2): Binary search trees and tree traversals. Read Chapter 8.
Week 15 (12/5-12/9): Balanced binary search trees; red-black trees. Read Chapter 9.

Sample code

Generating permutations (9/7): genPerms.java
Lafore's Merge Sort code and Merge Sort Applet
Lafore's Partition code and Partition Applet
Lafore's Quick Sort code and Quick Sort Applet
The myGraph class and a small testing program for it.
Generating subsets (Homework 2): genSubsets.java
Lafore's depth first traversal. Lafore's graph class and depth first traversal are much more primitive than the what we are developing in class.
Lafore's graph applet.
Version 1 of depth first traversal. It does not construct a depth first traversal tree. It does contain a print statement that outputs vertices, as they are being visited. The function has beenn integrated into the myGraph class, and has been successfully compiled and tested.
Version 2 of depth first traversal. This version contains code for constructing a depth first traversal tree. It also performs depth first traversal on all connected components of the graph. It does contain a print statement that outputs vertices, as they are being visited. The function has beenn integrated into the myGraph class, and has been successfully compiled and tested.
Lafore's Link class and his LinkList class.
Lafore's queue class. Use this to implement breadth first traversal in Project 2.2.
Lafore's HashTable class.
Lafore's Heap class.

Online Resources

Past offerings of the course: Fall 2003 and Fall 2004.
General Unix resources: UNIX Help, Commonly used UNIX commands.
Unix editors: Introduction to vi, Introduction to emacs.
Java Tutorials.