22C:21 Computer Science II: Data Structures
22C:21 Computer Science II: Data Structures 10:30-11:20 MWF, Room 112 MH 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, Fang Yang and D. Ezra Sidran, assigned to this course. Their office hours and contact information is as follows:
Fang Yang
101N MLH, 335-2839
fayang@cs.uiowa.edu
Wednesday 2:00-3:30PM, Thursday 10:00-11:30AM
D. Ezra Sidran
101 N MacLean Hall, 335-2839
dsidran@cs.uiowa.edu
Tuesdays 2:30-4:30, Thursdays 2:30-3:30
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. Due by lab time on 9/6. Solution: TwoRolls.java, twoRolls.pdf Quiz 1. 8/30. Solution: ImprovedRandomTest.java Homework 2. Due by lab time on 9/13. Quiz 2 (12:30 section), Quiz 2 (3:30 section) 9/6. Homework 3. Due by lab time on 9/20. Solution: CRS.java, CRSTester.java, and CRS.pdf. Quiz 3 (12:30 section), Quiz 3 (3:30 section) 9/13, updated CRS.java with solutions to Quiz 3. Homework 4. Due by lab time on 9/27. Solution: connectedComponents.java. Quiz 4 (12:30 section), Quiz 4 (3:30 section) 9/20, updated myGraph.java and Ladders.java with solutions to Quiz 4. Project 1. Due by lab time on 10/18. Project 1 Solution. Homework 5. Due by lab time on 10/4. City.java contains the solution. Quiz 5 (12:30 section), Quiz 5 (3:30 section), updated LinkList.java with solutions to Quiz 5. Quiz 6 (12:30 section), Quiz 6 (3:30 section). Homework 6. Due by lab time on 10/18. myListGraph.java has been updated with solution; also see playLadders.java and playLadders.out. Quiz 7 (12:30 section and 3:30 section): hash.java contains the solution. Homework 7. Due by lab time on 10/25. Quiz 8 (12:30 section) and Quiz 8 (3:30 section). myListStack.java contains the solution. Midterm Exam with solution. Homework 8. Due by lab time on 11/1. Here is output from my solution to this homework. This reads mileage lines from miles.dat correctly. Project 2. Due on 11/15. MST for the 128 cities in miles.dat. Solution. Quiz 9 (12:30 section and 3:30 section). Homework 9. Due by lab time on 11/8. Solution: MST.java. Quiz 10 (12:30 section and 3:30 section). Quiz 11 (12:30 section and 3:30 section). Homework 10. Due by lab time on 11/29. Partial Solution: VertexHeap.java, Node.java, HeapApp.java, HeapApp.out. Project 3. Due on 12/13. Homework 11. Due by lab time on 12/6. Announcements 8/13: The first discussion sections will meet on Thursday, 8/30 in the Computer Lab in 301, MLH. Section A01 will meet during 12:30-1:20 pm and Sections A02 and A03 will meet simultaneously during 3:30-4:20 pm. 8/27: Effective starting on Wednesday, 8/29 the class will meet in W207 PBB (Papajohn Building). 8/29: To get ready for the first lab meeting (Thursday, 8/30) read the Lab 1 Document and the links therein, make sure you have an account on a CS machine and make sure you have a HawkID and password to access ICON. You will use an ICON dropbox for submitting your quiz; here are instructions. 9/11: To get ready for Lab 3 (Thursday, 9/11) read the Lab 3 Document and the links therein, read CRS.java (solution to Lab 3 problem), and read Lab 3 powerpoint. Download CRS.java into an Eclipse project called CRS. Quiz 3 asks you to add some methods to the CRS class. 10/3: Our TA Fang Yang has changed her office hours, so as to be able to meet more students. Her new office hours are:
Wednesday, 2:00-3:30PM
Thursday, 10:00-11:30AM
10/6: There is no Homework 6. This should give you more time to focus on Project 1. 10/6: Starting this week (10/7) my Friday office hour will move to Thursdays, 9 am to 10 am. 10/15: The midterm is on Friday, 10/19 in class during 10:30-11:20. Feel free to bring books and notes, but leave your laptops at home. Here is a note on the midterm format from Spring 2007 (the exam format will be the same), here are practice problems, and here are solutions to practice problems. 11/12: Use the function header myWeightedGraph MSTGraph() instead of myWeightedGraph MST() in Project 2. 12/6: Caught up in the spirit of the upcoming holidays, I have decided to extend the due date on HW 11 to Friday, 12/7, 5:00 pm and the due date of Project 3 to Monday, 12/17. 5:00 pm. 12/7: The final exam is on Thursday, Dec 20th from 7:30 am to 9:30 am in our classroom, W207 PBB. Here is some information about the final. 12/21: The final scores and letter grades are here. You can look at your scores on ICON also. Weekly Topics and Links Week 1: 8/27-8/31 Classes and objects in Java; arrays in Java; constructing a collection of records that supports insert, delete, and search. Lab topic: Introduction to the Eclipse IDE; simple examples of Java classes and objects, Java arrays, and Java I/O. Lab 1 Document. Quiz and Homework: Quiz 1, Homework 1 (due by lab time on 9/6). 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. Sample code: Record.java, RecordDB.java. Week 2: 9/3-9/7 Brief introduction to running time analysis; binary search and linear search; two-dimensional arrays. Lab topic: Making arrays dynamic. Lab 2 Document, Lab 2 Powerpoint slides. Quiz and Homework: Quiz 2 (12:30 section), Quiz 2 (3:30 section), Homework 2 (due by lab time on 9/13). Links: Introduction to Java (read the notes for weeks 1-4), On multi-dimensional arrays. Sample code: DynamicRecordDB.java, CRS.java (solution to Lab 3 and Quiz 3 problems). Week 3: 9/10-9/14 Introduction to graphs; adjacency matrix representation of graphs; implementation of a Graph class that supports addVertex, addEdge, deleteVertex, and deleteEdge, etc. Lab topic: Compressing 2-dimensional arrays. Lab 3 Document, CRS.java (solution to Lab 3 problem), Lab 3 powerpoint. Quiz and Homework: Quiz 3 (12:30 section), Quiz 3 (3:30 section), Homework 3 (due by lab time on 9/20). Links: Wikipedia on graphs, MathWorld on graphs, Adjacency matrices. Sample code: myGraph.java, Ladders.java. Week 4: 9/17-9/21 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. Lab topic: Computing the clustering oefficient. Lab 4 Document, Updated myGraph.java with clustering coefficient computation, Ladders.java (run Ladders and look at the output). Quiz and Homework: Quiz 4 (12:30 section), Quiz 4 (3:30 section), Homework 4 (due by lab time on 9/27). 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), Updated myGraph.java with clustering coefficient computation. Week 5: 9/24-9/28 More on the adjacency list representation of graphs; another application of linked lists: hashing with chaining. designing good hash functions and efficiently Lab topic: Making a more sophisticated LinkedList class. Lab 5 Document. Link.java, LinkList.java have been updated for Lab 5. Quiz and Homework: Quiz 5 (12:30 section), Quiz 5 (3:30 section), Homework 5 (due by lab time on 10/4). Links: Wikipedia on adjacency list representation, NIST on adjacency lists, Wikipedia on hash tables, Notes on hashing with chaining from McGill. Sample code: Link.java, LinkList.java, StringLink.java, StringLinkList.java, myListGraph.java (this is the adjacency list representation of a graph; uses StringLinkList). Week 6: 10/1-10/5 Designing good hash functions and efficiently computing hash values. Abstract data types (ADTs); the queue and stack ADTs; Lab topic: Comparing the simple sorting algorithms: Lab 6 Document. TimingSimpleSort.java implements bubble sort, selection sort, and insertion sort and times these. Quiz and Homework: Quiz 6 (12:30 section), Quiz 6 (3:30 section), Homework 6. Links: Wikipedia on hash tables, Notes on hashing with chaining from McGill. Sample code: TimingSimpleSort.java implements bubble sort, selection sort, and insertion sort and times these; Dictionary.java implements hashing with chaining; Queue.java is an array-based implementation of the Queue ADT; myStack.java is an array-based implementation of the Stack ADT. Week 7: 10/8-10/12 Graph traversals, algorithm for breadth-first search (BFS), implementing BFS using a queue; constructing BFS trees; applications of BFS; Lab topic: Implementing hashing with chaining: Lab 7 Document, Dictionary.java implements hashing with chaining, Dictionary.out, showing the distribution of linked list sizes. Quiz and Homework: Quiz 7 (12:30 and 3:30 section), no homework this week. Links: Notes and an example of BFS, More notes on BFS, BFS in web-crawling, BFS animation. 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 8: 10/15-10/19 Introduction to recursion. Simple examples (fibonacci numbers, power function, binary-to-decimal, etc.) Lab topic: Implementing the Stack ADT: Lab 8 Document, myStack.java implements a Stack ADT. Quiz and Homework: Quiz 8 (12:30 section), Quiz 8 (3:30 section), Homework 6. Links: Notes on recursion, Wikipedia on recursion in computer science, and Wikipedia on Towers of Hanoi. Sample code: Fibonacci.java, FastFibonacci.java, Recursive depth-first search, Towers.java solves the Towers of Hanoi problem. Week 9: 10/22-10/26 Using recursion to implement search with backtracking; solving the 8-queens problem; solving the traveling salesman problem. Lab topic: Implementing a fast, recursive, Fibonacci function: Lab 9 Document, Fibonacci.java implements the standard, slow, Fibonacci function and FastFibonacci.java implements a modified version of this that runs at lightning speed, despite being recursive. Output of FastFibonacci may convince you. Quiz and Homework: Quiz 9 (12:30 and 3:30 sections), Homework 7. 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 Traveling Salesman Tour problem, Two excellent TSP games. Sample code: Queens.java uses recursion to implement "search with backtracking" to place n queens on an n by n chessboard. Week 10: 10/29-11/2 Recursive implementation of divide-and-conquer algorithms: Merge sort and Quick sort. Running time analysis of these algorithms, randomized Quick sort. Lab topic: Implementing weighted graph class: Lab 10 Document, EdgeLink.java and EdgeLinkList.java implement a linked list that can keep track of neighbors as well as the weights of edges to the neighbors. Quiz and Homework: Quiz 10 (12:30 and 3:30 sections), Homework 8. Links: Wikipedia on merge sort, A merge sort applet, Wikipedia on quick sort, Animation of various sorting algorithms. Sample code: mergeSort.java and QuickSort.java. Week 11: 10/29-11/2 More on quick sort; activation records, activation stacks, and implementing recursion using an explicit stack. The priority queue ADT; a sorted-array implementation and an unsorted-array implementation of a priority queue ADT; running time analysis of these implementations. Lab topic: Activation records, activation stack, and implementing recursion using an explicit stack. Lab 11 Document, FibonacciPrint.java, FibonacciStack.java, FibonacciStack.out. Quiz and Homework: Quiz 11 (12:30 and 3:30 sections), Homework 9. 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. Week 12: 11/5-11/9 A max-heap and a min-heap; an implemntation of the priority queue ADT using a max-heap. Lab topic: Heap sort, Lab 12 Document, heapSort.java. Sample code: An enhanced min-heap implementation that can be used in Prim's Algorithm and in Dijkstra's Algorithm: Node.java, VertexHeap.java, HeapApp.java, HeapApp.out. Week 13: 11/12-11/16 Implementing Prim's MST algorithm and Dijkstra's shortest path algorithm using binary heaps. Week 14: 11/26-11/30 Binary search trees; implementation of binary search tree operations: search, insert, and delete; Tree traversals: in-order, pre-order, and post-order. Implementation of a binary search tree iterator. Lab topic: Binary Search Trees, Lab 13 Document, tree.java. Week 15: 12/3-12/7 Introduction to balanced binary search trees; AVL Trees: definitions; insertion into an AVL tree and repairing imbalance using rotations; the two cases for responding to an AVL tree insert and the three cases for responding to an AVL tree delete. Lab topic: AVL Trees, Lab 14 Document, AVLNode.java, AVLTree.java, AVLTreeTester.java, AVLTreeTester.out. Sample code None yet. Online Resources Past offerings of the course: Fall 2003, Fall 2004, Fall 2005, Spring 2006, and Spring 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.
