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

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 WangContact 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

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

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

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

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

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