Spring 2009: Computer Science II, Data Structures, 22C:021

Coordinates

The course meets 10.30--11.20 pm Monday, Wednesday, and Friday at 427 EPB. Each student is also registered for and will attend a weekly discussion section conducted by one of our TAs.

Content

The second course required for computer science majors and minors emphasizes the design, implementation, and analysis of common data structures and algorithms. The goal is to teach how data structures provide the necessary data abstraction for the development of large software systems and their central role in software engineering. Data structures covered include sets, linked lists, stacks, queues, hash tables, trees, heaps, and graphs. Students are introduced to algorithms for searching, sorting, and data structure manipulation and learn the techniques to analyze program efficiency. Programming using recursion and dynamic data structures are covered. The programming language is Java.

For our textbook, we will use "Data Structures and Algorithm Analysis in Java 2/E" by Weiss, ISBN 0321370139.

Prerequisites

Computer Science I (22C:016). Discrete Structures (22C:019) is a corequisite if not taken as a prerequisite.

Grading

The grading will be based on several homeworks (50 percent), of which there will be essentially one each week, one midterm (20 points) and one final (30 points). Most of the homeworks will involve Java programming.

Exam Dates

The midterm will be in class on Monday, March 9. The final Exam will be on Tuesday, May 12, from 12.00 noon to 2.00 pm, in our regular classroom 427 EPB.

Teaching Assistants and Discussion Sections

Each of the students in the class is registered for a discussion section that he/she is expected to attend. The TAs for the class are Kajari Ghosh Dastidar and Greg Nichols . They will lead discussions according to the following schedule.

Section         Time                    Location                TA
A01             1:30-2:20 Th            113 MLH                 Kajari 
A03             3:30-4:20 Th            118 MLH                 Kajari 
A04             10:30-11:20 Th          214 MLH                 Greg

Office Hours

Kasturi        1.00-2.00 Tue, 2.30-3.30 Wed, 2.00-3.00 Fri   101E MLH
Kajari         10.30-12.00 Tue and Thu                       B1C MLH
Greg           1.00-2.30 Wed

Handouts and Notes

First Day Handout
Paranth.java , the program we develop during the first week. A modification so that the stack consists of general objects. I have not modified the last if statement the way it needs to be (as discussed in class).
The linked list illustration we studied on Monday, Jan 26.
A stack implementation using linked lists we studied on Wednesday, Jan 28.
The program we used on Monday, Feb 2, to illustrate instance and static methods (and variables).
On Wednesday, Feb 4, we talked about recursion following the discussion in Section 1.3 of the textbook.
On Friday, Feb 6, we developed a general purpose method to find the maximum of an array of objects, and showed how to use it.
An example of a generic class and a generic version of our stack class that we develop on Monday, Feb 9.
A generic implementation of the method to find the maximum of an array of objects
The slides used for our discussion on generic classes, methods, and so on , and for our discussion on lists and iterators .
Code used on Feb 16 to discuss lists and iterators. Another piece.
Slides for the Feb 23 lectures on binary search trees.
Slides for the Feb 25 lecture on the generic binary search tree implementation from the textbook.
The java programs in the textbook are available at the author's site.
Slides for Kajari's Mar 13 lecture.
Slides on priority queue code used on March 25.
Slides on hashing used on March 27/30.
Slides on sorting used on April 8.
Slides on Graph Representation used on April 15.
The final Exam will be on Tuesday, May 12, from 12.00 noon to 2.00 pm, in our regular classroom 427 EPB.
Kajari's Solutons to Homework 6

Homeworks

Homework 1: Implement the Queue data structure using arrays as discussed in the lectures by providing the code for the outlined MyQueue class . I will later add a main method that will use this class. Meanwhile, please test your code using your own main method. The deadline for finishing this homework is Monday, Feb 2, 11.59 pm. Please submit into the desginated folder in icon (which I will create shortly). Update: I've added a main method you can use, but at the moment it is commented out.
Homework 2: Implement the Queue data structure using doubly linked lists by providing the code for the outlined MyQueue class . We discuss doubly linked lists in class on Wednesday, Feb 4. You can also find a brief discussion in Section 3.2 of the book. The deadline is Wednesday, Feb 11, 11.59 pm. You may find it useful to study our stack implementation using (singly) linked lists.
Homework 3: due 11.59 pm on Monday, Feb 23. Part 1: Explain why the two print statements in this program behave differently. That is, why don't they both print "true"? Part 2: Write the code for the method as specified here . We discussed the spec in class on Feb 16. Submit a text file for the first part and the program for the second part into the specified folder in icon.
Homework 4: due 11.59 pm on Wednesday, Mar 4. In this homework, you have to enhance the binary search tree class we developed on Monday, Feb 23. Part 1: Add a size variable to the class BinaryTreeNode, as shown. Ensure that for such a node x in the binary search tree, x.size is always equal to the number of elements in the subtree rooted at x. You will have to modify the insert method of class BinarySearchTree for this. Part 2: Add a delete method to the class BinarySearchTree as specified here. The implementation should also take part 1 into account.
Homework 5: due 11.59 pm on friday, March 27. Part 1: You need to build on the code from homework 4. Add a method numGreaterThan(int x), to the binary search tree class. This should return the number of integers stored in the tree that are strictly greater than x. For example, if the tree stores 10, 20, 30, 40, and 50, then numGreaterThan(11) should return 4. In the week before the spring break, one of the TAs will indicate how to use the size field that we added in homework 4 to implement this method so that its cost is proportional to the height of the tree. Part 2: Compile and run the attached program and give your explanation for the observed running times. You may have to wait a minute or two for the program to complete. Submit your explanation into icon itself, don't turn in a hard copy.
Someone in class asked for a solved version of Homework 4 so that it can be used to test Part 1 of Homework 5. Here is a binary search tree class with the size field incorporated. It only allows insertion and not deletion, but this is sufficient to allow testing for the code you develop for Part 1 of Homework 5.
Homework 6: due 11.59 pm on Monday, April 6. The goal here is to modify the priority queue implementation of the textbook's author to allow one more operation, delete(AnyType x). This operation deletes the object x from the priority queue. (It should return false if x is not in the priority queue, and true otherwise.) The modified priority queue class should be as outlined here. To perform delete(x) efficiently, we need to quickly find out where x is stored in the array representing the binary heap! We will remember this information in a hash table so that it can be efficiently accessed and modified. You can use the author's hash table implementation . Although this assignment is not a lot of work once we know what exactly needs to be done, it has some subtle aspects that we will discuss in class. Update: You can submit by 11.59 pm on Tuesday, April 7. I will take it, but with a small penalty if it is after the original deadline. This deal is good only for this assignment !!
Homework 7: due 11.59 pm on Monday, April 20. Write a static method that takes as input an array and returns the number of inversions in the array. Recall that a pair of array entries form an inversion if they are wrongly ordered. See Section 7.3 if you need more input on what an inversion is. The method outline can be:
```
       public static int inversionCount( int [] a){} 
```
If you prefer to make the input an array of Comparables like the sorting algos in the textbook, thats fine too. The main requirement is that your method should implement an O(N log N) algorithm. Note: A response to a common question about this homework.
Homework 8: due 11.59 pm on Wednesday, April 29. Add methods for topological sorting and breadth first search to this Graph class that I wrote and we discussed in class. The method outline for topological sort should be
```
        void topsort() 
```
It should topologically sort the graph as described in pseudocode in Figure 9.7 of the text. You will have to modify the Vertex class to include the fields indegree and topNum. (Instead of throwing the CycleFoundException, you can print a complaint.) The LinkedList class has methods that allow us to work with it as a queue. The outline for breadth-first-search should be
```
        void unweighted(String s) 
```
Here, s is a string that identifies the start vertex for the breadth first search, which should work along the lines of the pseudocode in Figure 9.18 of the text. Again, you have to add some fields to the vertex class. To test your methods, you can create graphs as outlined in the main method.
Homework 9: due 11.59 pm on Wednesday, May 6. Add a method to this Undirected Graph Class that prints the names of all the articulation points. The method outline should be
```
 void printArtPoints() 
```
This should work using depth first search, roughly following the pseudocode in Figures 9.65 and 9.66 of the text. (The test for the forward edge in Figure 9.66 is not quite accurate, and you should modify it.) You should take into account the root, which is not considered in that pseudocode. As in the previous assignment, feel free to modify the class to add fields to the Vertex class, etc.