22C:21 Computer Science II: Data Structures
10:30-11:20 MWF, Room 1505 SC
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 9-10 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.
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Lecture Notes,
Sample code,
Online Resources
There are three TAs for the course: Anish Padariya, Michael Edwards, and
Erik Krohn.
They will lead discussion sections according to the following
schedule.
Section Time Location TA
A01 12:30-1:20 Monday 210 MLH Anish Padariya
A02 9:30-10:20 Tuesday 118 MLH Michael Edwards
A03 3:30-4:20 Wednesday 114 MLH Erik Krohn
A04 1:30-2:20 Tuesday 105 MLH Michael Edwards
Contact information for the TAs is as follows.
Anish Padiyara B20J MLH 335-3650 apadiyar@cs.uiowa.edu www.cs.uiowa.edu/~apadiyar
Michael Edwards B20J MLH 335-3650 mcedward@cs.uiowa.edu www.cs.uiowa.edu/~mcedward
Erik Krohn B20J MLH 335-3650 eakrohn@cs.uiowa.edu www.cs.uiowa.edu/~eakrohn
They will hold office hours according to the following schedule.
Anish Padiyara Monday 4:00-5:00, Friday 5-6
Michael Edwards Tuesday 4:00-5:00, Wednesday 5:00-6:00, Thursday 4:00-5:00
Erik Krohn Monday 12:30-1:20, Thursday 1:30-2:20
- 1/16: There will be no meetings of the discussion sections during
the first week of classes (1/16-1/20).
- 1/19: CS machine accounts will be handed out in discussion sections
next week (1/23-1/27).
- 1/19: For an overview of basic java concepts, read Chapter 2 on
arrays.
- 1/22: The CS department provides computing help for students in CS classes in 301 MLH according to this schedule.
- 2/8: Submit Homework 3 electronically, by 5 pm on Friday, 2/10.
Instructions for electronic submission are here.
- 2/9: Starting next week (2/13), we will have two new TAs replacing
Vivek Rane. Anish Padiyara will be responsible for the Monday
discussion section and Erik Krohn will be responsible for the Wednesday
discussion section. More information on the new TAs, including office
hours, will be announced soon.
- 2/26: No class on Wednesday (3/1). Midterm on Friday (3/3).
Midterm is in-class, open notes/book, 50 minutes long, and worth
200 points (20% of your grade).
- 3/27: Midterm Grades. Please
report errors to the Professor or to the TAs.
- 4/14: Homework 10 and Project 2 are both due on Monday (4/17). Homework 10
is due by 5 pm and Project 2 is due at midnight.
- 5/5: Here are pre-final scores.
Please report any errors by Monday, 5/8.
- 5/5: An old final (from fall 2004).
- 5/16: Here are Final scores and grades.
- Week 1 (1/16-1/20): Introduction to data structures and abstract data
types; binary search and basics of running time analysis. Wednesday 1/18 and Friday 1/20.
- Week 2 (1/23-1/27): Examples of running time analysis. Arithmetic series,
logarithms. Analysis of binary search. The "Big-Oh notation."
Monday 1/23, Wednesday 1/25 and Friday 1/27.
- Week 3 (1/30-2/3): Big Theta notation. Multi-dimensional arrays in Java.
- Week 4 (2/6-2/10): An example of a data structures that uses
multi-dimensional arrays: TwoDArray.java;
examples of I/O and parameter passing in Java.
- Week 5 (2/13-2/17): Graphs, adjacency matrix representation,
the Graph class, primitive operations
such as adding a vertex, deleting a vertex, adding an edge, and deleting
an edge; introduction to graph traversal. This material appears in Chapter 13
in the textbook. Read pages 615-623.
- Week 6 (2/29-2/24): Linked lists. This material appears in Chapter 5;
read pages 179-197. An example of linked lists: hashing with chaining. This material
appears in Chapter 11; read pages 519-528 and 552-574.
- Week 7 (2/28-3/3): More on hashing on Monday.
No class on Wednesday. Midterm on Friday.
- Week 8 (3/6-3/10): Adjacency list representation of graphs.
Simple examples of recursion: linear search, binary search, Fibonacci numbers,
and Towers of Hanoi. Read Chapter 6 for recursion.
- Week 9 (3/20-3/24): Divide-and-conquer for efficient sorting: merge sort
and quick sort. Merge sort appears in Chapter 6 and quick sort appears
in Chapter 7.
- Week 10 (3/27-3/31): Improving quick sort: median-of-three rule and randomized
choice of pivot. Implementing "search witht backtracking" using recursion. Example
of the n-Queens problem: code.
- Week 11 (4/3-4/7): The Stack ADT and different implementations. Implementing
function calls using stacks: activation records and the system stack. Translating
recursive functions into non-recursive stack based functions. Examples included the
non-recursive stack based fibonacci function and stack based depth-first search.
- Week 12 (4/10-4/14): More on depth-first search. Building a depth-first traversal
tree. Breadth-first search and the Queue ADT.
- Week 13 (4/17-4/21): Priority queues. Binary heaps.
- Code for the class that maintains records in an ordered array, Record.java and
RecordDB.java.
- Code for generating input for and timing bubble sort,
TimingBubbleSort.java.
- Code for a dynamic version of the class that maintains records in an ordered array, Record.java and
DynamicRecordDB.java.
- Code for a data structure that uses a 2-d array: TwoDArray.java. This code also shows how to read input from the
console.
- Code for the Set ADT (Problem Set 3): Set.java.
- Lafore's linked list class: Link.java and
LinkList.java.
- Code for the Sudoku program (Problem Set 3): Sudoku.java.
- Queue class implementation (Problem Set 4): To be posted.
- Lafore's implementation of hashing with chaining: hashChain.java. It uses a sorted link list; there is no real reason
to use a sorted linked list, so just use a plain linked list in
your implementation for Project 1. Also, Lafore's implementation assumes
that the key is an integer and therefore his hash function is not
interesting.
- Code for processing a text file, replacing all occurances of "red" by "blue" (Problem Set 6): Replace.java
- Code for the versions of quick sort discussed in class: QuickSort.java
- Lafore's doubly linked list class.
- Lafore's quick sort. Version 2 uses the median-of-3 rule to improve the choice
of the pivot and Version 3 uses this rule and call insertion sort to deal with base cases. The implementation of partition
in Lafore's code is different from the implementation discussed in class.
- Code for "search with backtracking" solution of the n-Queens problem: Queens.java.
- Code for the recursive solution to the Towers of Hanoi problem: Towers.java.
- Lafore's code for the Stack class.
- Code for a fast recursive Fibonacci function that remembers answers to earlier subproblems: FibonacciTest.java.
- The myGraph class has been updated with a depth first traversal function.
Please read the comments just before the function. Here is the Stack class defined in the Java collections
framework. This is what I used to implement the function.
- The myGraph class has been updated with a recursive version of the depth first traversal function.
You might want to compare the stack-based implementation with the recursive implementation.
- Code for a stack-based solution to the Towers of Hanoi problem: TowersStack.java. Please
compare with recursive solution posted earlier.
- Code for the recursive solution to the knapsack problem:
knapsack.java.