22C:21 Computer Science II: Data Structures

1:30-2:20 MWF, Room 112 MH

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11:00-12:20 Monday and Wednesday

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, Kajari Ghosh Dastidar and Chris Dibbern, assigned to this course. Their office hours and contact information are as follows:

Kajari Ghosh Dastidar   B1C MLH, 319-331-5247   1:30-3:00 Tuesday, Friday                            kghoshda@cs.uiowa.edu 
Chris Dibbern           B20J MLH, 319-321-1442  12:20-1:40 Tue, 2:30-3:30 Th, 11:00-12:00 Fri        chrisdibbern@gmail.com

The TAs are responsible for leading the discussion sections will hold 3 office hours per week to answer your questions.

Quizzes, Projects, and Exams

Homework 1. Posted on 8/31. Due on Wednesday 9/10.
Quiz1a, Quiz1b, and Quiz1c. Given on Thursday, 9/11.
Homework 2. Posted on 9/16. Due by 5 pm on Friday, 9/26 via ICON.
Project 1. Posted on 10/2. Due by 5 pm on Friday, 10/24 via ICON.
Quiz2a, Quiz2b, and Quiz2c. Given on Thursday, 10/2.
Quiz 3. Given on Thursday, 10/9.
Midterm with solutions. Given on 10/17. Here is the midterm score distribution.
Quiz4a and Quiz4b. Given on 10/30.
Homework 3. Posted on 10/31. Due by 5 pm on Friday, 11/10 via ICON.
Here is Project 1 Grading Guidelines.
Project 2. To be posted on 11/10. Due by midnight on Wednesday, 12/3 via ICON.
Quiz5a and Quiz5b, and Quiz5c. Given on 11/13.
Project 1 Solution.
Homework 4. Posted on 12/5. Due by 5 pm on Monday, 12/15 via ICON.
Quiz6a and Quiz6b.
files with source-destination pairs for Homework 4. Posted on 12/11.

Announcements

8/25: The first discussion sections will meet on Thursday, 8/28. The TAs will present a Java tutorial and help you get started on Homework 1.

8/25: On Friday the TAs will run a "help session" on the Eclipse IDE in the computer lab (301 MLH). Times will be annouced later. Here is the Eclipse Tutorial they plan on using.
8/26: The computer lab in 301 MLH has been reserved for two "help sessions" on the Eclipse IDE. Friday, 8/29 ~~1:30-2:20~~ 3:30-4:20 and Friday, 8/29 ~~2:30-3:20~~ 4:30-5:20. Hope to see you at one of these.
9/7: Quiz 1 will be held in the discussion section on 9/11. This is open notes/books and will last for 20 minutes. Topics are (i) the RecordDB and DynamicRecordDB classes, (ii) linear search and binary search and their running times, (iii) adjacency matrix representation of graphs and the myGraph class.
9/7: The class has been activated on ICON. Future HWs (after HW1) will have to be submitted on ICON. Also, check ICON for your grades.
9/30: Quiz 2 will be held in the discussion section on 10/2. This is open notes/books and will last for 20 minutes. Topics are (i) linked lists and (ii) adjacency list representation of graphs. You will be responsible for code in the Link, LinkList, doublyLinked, and myListGraph classes.
10/5: Quiz 3 will be held in the discussion section on 10/9. Topics are (i) the trie data structure and (ii) hashing with probing.
10/13: The midterm exam will be held in class on Friday, 10/17 at the usual class time (1:30-2:30). Here are instructions for the midterm.
10/23: You may submit a file called wordPair.java defining a simple wordPair class as part of your Project 1 solution. This is in addition to the files listed in the Project 1 guidelines.
10/29: Quiz 4 on Thursday, 10/30. The topics will be the Queue and Stack ADTs, their implementations using arrays and linked lists, breadth-first traversal and depth-first traversal, finding connected components and shortest paths.
11/12: Quiz 5 on Thursday, 11/13. The topic will be recursion, including the examples of computing fibonacci numbers, implementations of the "search with backtacking" paradigm in the knapsack and n-queens problem and the "divide and conquer" paradigm in the merge sort and quick sort algorithms.
12/2: Quiz 6 on Thursday, 12/4. The topics are Priority Queue ADT, binary heaps (min and max), and implementation of Dijkstra's Shortest Path algorithm using binary heaps.
12/2: Project 2 is due tomorrow (12/3), by midnight. Project 2 ICON dropbox is now open.
12/8: Quiz 7 on Thursday, 12/11. The topics are binary search trees and operations on these trees.
12/11: files with source-destination pairs for Homework 4. You could use these input files to get a sense of how fast your program is and also how much of a difference, your optimizations are making. The "long" files contain source-destination pairs that are many hops away from each other and the "short" files contain source-destination pairs that are only a few hops from each other.
The final is on Monday, Dec 15th from noon to 2:00 pm in our classroom, 112 MH. Here is a small study guide.

Weekly Topics and Links

Week 1: 8/25-8/29 Classes and objects in Java; arrays in Java; constructing a collection of records that supports insert, delete, and search.
Discussion Section: Java tutorial; simple examples of Java classes and objects, Java arrays, and Java I/O. Week1 power point.
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, Eclipse Tutorial.
Sample code: Record.java, RecordDB.java.
Week 2: 9/1-9/5 Brief introduction to running time analysis; binary search and linear search; two-dimensional arrays; adjacency matrix representation of graphs.
Discussion section: Making arrays dynamic, timing Java programs. Week2 power point.
Links: Introduction to Java (read the notes for weeks 1-4), On multi-dimensional arrays, Lecture notes on running time of binary search.
Sample code: DynamicRecordDB.java.
Week 3: 9/8-9/12 Introduction to graphs; adjacency matrix representation of graphs; implementation of a Graph class that supports addVertex, addEdge, deleteVertex, and deleteEdge, etc.
Discussion section: Another example of a 2-dimensional data structure: TwoDArray.java. Week 3 power point.
Quiz 1 will be held during this discussion section. Here are the quizzes: Quiz1a, Quiz1b, and Quiz1c.
Links: Wikipedia on graphs, MathWorld on graphs, Adjacency matrices.
Sample code: myGraph.java, Ladders.java, TwoDArray.java.
Week 4: 9/15-9/19 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.
Discussion section: The Java Collections Framework, examples of the ArrayList and LinkedList class. Week 4 power point.
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), myListGraph.java (an implementation of a graph class using the adjacency list representation).
Week 5: 9/22-9/26 More on the adjacency list representation of graphs; running times of graph class methods using the adjacency matrix representation versus using the adjacency list representation. Clustering coefficient and how to compute it.
Discussion section: The trie data structure. Node.java, Trie.java, TestTrie.java. Week 5 power point.
Links: Wikipedia on adjacency list representation, NIST on adjacency lists, Wikipedia on hash tables, Notes on hashing with chaining from McGill.
Sample code: StringLinkList.java, myListGraph.java (this is the adjacency list representation of a graph; uses StringLinkList).
Week 6: 9/29-10/2 Hashing and hash tables; hashing with chaining and hashing with probing. How to design good, efficiently computable, hash functions. Discussion on running time of the insert, search, and delete methods for our implementations of hash tables.
Discussion section: Slow sorting algorithms: bubble sort, selection sort, and insertion sort. TimingSimpleSort.java, code that implements and times these sorting algorithms. Week 6 power point. Quiz 2 on linked lists and adjacency list representation of graphs. Quiz 2a, Quiz 2b, Quiz 2c.
Links: Wikipedia on hash tables, Notes on hashing with chaining from McGill.
Sample code: ChainingHashTable.java (implemention of hashing with chaining), ChainingHashTableTester.java.
Week 7: 10/6-10/10 Abstract Data Types, Interfaces in Java, Implementing and inheriting from interfaces, the Comparable, Iterable, and Iterator interface, implementing a ListIterator that works with the StringLinkList class.
Links: Comparable interface, Iterator interface, Iterable interface, Notes on using the Comparable interface, Notes on the Comparable and Comparator interface.
Discussion Section: Overview of Project 1. Quiz 3 on (i) the trie data structure and (ii) hashing with probing. Week 7 power point.
Sample code: comparableRecordOld.java, comparableRecord.java, and comparableRecordTester.java.
Week 9: 10/20-10/24 The Queue ADTs, implementing a Queue ADT, Breadth-first traversal on graphs and how to implement this using queues, applications of breadth-first traversal to shortest paths and connected components.
Links: Notes and an example of BFS, More notes on BFS, BFS in web-crawling, BFS animation.
Discussion Section: Implementing the Queue and Stack ADT using arrays and linked lists. Week 9 power point.
Sample code: myListGraph.java is updated with new methods breadthFirstSearch, isConnected, connectedComponents, and shortestPath; 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 10: 10/27-10/31 The Stack ADT, implementing a Stack ADT, Depth-first traversal on graphs and how to implement this using stacks, introduction to recursion, simple examples of recursion: the power function and fibonacci function, recursive depth-first traversal, the search with backtracking approach applied to other problems such as the knapsack problem.
Links: Notes on recursion, Wikipedia on recursion in computer science, Wikipedia on Towers of Hanoi, 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.
Discussion Section: A fast implementation of a recursive Fibonacci function. Quiz 4: The topics will be the Queue and Stack ADTs, their implementations using arrays and linked lists, breadth-first traversal and depth-first traversal, finding connected components and shortest paths. Week 10 power point.
Sample code: Fibonacci.java, FastFibonacci.java, Recursive depth-first search, Towers.java solves the Towers of Hanoi problem, Queens.java uses recursion to implement "search with backtracking" to place n queens on an n by n chessboard.
Week 11: 11/3-11/7: One more application of the search with backtracking paradigm: the 8-queens problem. Recursion as a means to implement the divide-and-conquer paradigm, two examples from sorting: merge sort and quick sort.
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 merge sort, A merge sort applet, Wikipedia on quick sort, Animation of various sorting algorithms.
Discussion Section: Call stacks, activation records, simulating recursion using an explicit stack. Week 11 power point.
Sample code: mergeSort.java and QuickSort.java, FibonacciPrint.java, and FibonacciStack.java.
Week 12: 11/10-11/14: The priority queue ADT; a sorted-array implementation and an unsorted-array implementation of a priority queue ADT; running time analysis of these implementations. A max-heap and a min-heap; an implementation of the priority queue ADT using a max-heap. Heap sort, another sorting algorithm that runs in O(n log(n)) time.
Links: Binary Heaps in Wikipedia
Discussion Section: Two more examples of recursion: the Towers of Hanoi problem and the problem of generating permutations. Quiz 5 on recursion. Week 12 power point.
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. heapSort.java, an implementation of heap sort. Code to accompany discussion section material: Towers.java and genPerms.java.
Week 13: 11/17-11/21: The problem of finding shortest paths in an edge-weighted graph. Dijkstra's shortest path algorithm for single source shortest paths. Implementing this algorithm using binary min-heaps.
Links: Dijkstra's Shortest Path Algorithm.
Discussion Section: An overview of Project 2. Week 13 power point.
Sample code: myWeightedGraph.java, VertexHeap.java, Node.java, EdgeLinkList.java, EdgeLink.java. The class myWeightedGraph implements edge-weighted graphs using an adjacency list representation. Each linked list of neighbors is an EdgeLinkList object, which in turn is a sequence of EdgeLink objects. The myweightedGraph class contains a binary heap based implementation of Dijkstra's shortest path algorithm. The corresponding binary heap implementation is in the classes VertexHeap and Node.
Week 14: 12/1-12/5: Finishing up the implementation of Dijkstra's shortest path algorithm. Binary Search Trees: definitions, insert, search, and delete operations. Running time of binary search tree operations.
Links: Dijkstra's Shortest Path Algorithm, Binary Search Trees from Wikipedia, a nice animation of binary search trees. Discussion Section: Quiz 6 will be given out. Topics: Priority Queue ADT, binary heaps (min and max), Dijkstra's shortest path algorithm.
Sample code: tree.java, a binary search tree class.
Week 15: 12/8-12/12: Balanced Binary Search Trees, AVL Trees, the rotation operations, preorder, postorder, and inorder traversals.
Links: Wikipedia on AVL Trees, AVL Tree animation, Slides on AVL trees.
Discussion Section: Tree traversals: pre-order, post-order, and in-order traversal, recursive functions for testing if a binary tree has the binary search property, etc. Quiz 7 will be given out. Topic: Binary Search Trees.
Sample code:

Sample code

Online Resources

Past offerings of the course: Fall 2003, Fall 2004, Fall 2005, Spring 2006, Spring 2007, and Fall 2007.
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.