Lecturer: Professor Sriram Pemmaraju
Time & Place: 10:30A - 11:20A MWF 221 Chemistry Building
TA: Zhihong Wang
Time & place for A03: 9:30A - 10:20A T 218 MacLean Hall
Time & place for A02: 10:30A - 11:20A T 118 MacLean Hall
Time: 4:00P - 5:00P Tue, Wed; 3:00-4:00P, Fri
Place: 101K MacLean Hall (353-2542)
-week2.ppt Aug 31,2004. Vector class implementation.
Sample code for new "remove" function: Vector1.java (inefficient solution), Vector2.java (efficient solution), VectorTest.java (testing program). I defined class "Vector1" and "Vector2" as subclass of "Vector". Put them under the same directory as all other Bailey structures.
-week3.ppt Sep 7,2004.Implementation of Matrix Class (Text P60-63)
-week4.ppt. Sep 13, 2004. Explanation of Project 1 on Sparse Matrix Class (I corrected the algorithm for set method on 09/24/2004).
-week5.ppt. Sep 21, 2004. Planning of Project 1 and how to do the testing at each step.
Things might be useful for Project 1:
- Make sure you have downloaded structure package. In this package, the author provides all the java structures in his book. You can find Matrix Class in that package. You can put SparseMatrix in structure package or your own package. Do not forget " import structure.* " or "package structure " at the beginning of your code.
- For set method, I have corrected the algorithm in my slide week4.ppt (I messed up the steps numbering before). When you do your programming, the KEY is : starting from parameter c, try to find the start and end location for column c. Based on this location info, you can check rowIndices of the row indices for the values in column c. Then you can derive what's in column c, where to add the new value (adding is necessary when old value (M[r][c]==0) and new value!=0) or whether you need to remove old value (if old-value (M[r][c]) is non-zero and new value is zero). Try to make the three Vectors consistent while you do the addition or removal. For cases (old value==0 and new value==0) and (old value!=0 and new value!=0), you do less work. You will have to do lots of Integer conversion back and forth in the coding. Keep that in mind all the time.
- (NEW!) I gave my version of SparseMatrix.dump function and SparseMatrix.print function for your reference.
- It is highly recommended you do all the testing mentioned in our discussion. Here is a sample of test program. You can put your testing code in it. I'll also try to update it these days.
- (NEW!) Updated MatrixTest.java testing all methods in SparseMatrix. You can comment unnecessary printing lines when you do your testing.
-week6.ppt. Sep 28. The idea of recursion. Recursion examples: array comparison, power computation, and Fibonacci numbers. Relation between recursion and mathematical induction.
-Week8.ppt. Oct 12. Discuss doubly-linked lists and the implementation.
-Week9.ppt. Oct 19. Java Interfaces and abstract classes. Their syntax and benefits. Examples include Generator and Comparable interfaces. We also learnt how to write a class which "implements" an interface by implementing methods defined in the interface. Through examples, we observed how interfaces help to improve code reusability. Abstract class is a structure "between" interfaces and regular classes to provide implementation of those methods which are independent of classes.-Week10.ppt. Oct 26. Graph structure to be implemented in project 2.
We introduced the class organization: interface MyGraph, abstract class MyAbstractGraph, and the two classes -MyMatrixGraph and MyListGraph. We went over the functionality of methods in MyGraph. Then MyMatrixGraph was discussed with details. We also worked on the implementation of a couple of methods in MyMatrixGraph: addVertex and getIndex.
-Week11.ppt. Nov 2. Implementation of depth-first traversal of a graph.
1. Build depth-first tree (s) during recursive d-f traversal. D-f traversal of graph with multiple connected components
2. Construct Vector returned by d-f traversal. This vector stores d-f trees.
3. Methods related to d-f traversal and where to put these methods (e.g. firstVertex and getIndex)
-Week12.ppt. Nov 09 Three implementing Queue structure using List, Vector and array.
1. Class organization: interface Queue is implemented by abstract class AbstractQueue, which is then extended by regular classes QueueList, QueueVector, and QueueArray
2. Complexity of methods in the three regular classes.
-Week13.ppt. Nov 16 Introduction to C language. Topics include array declaration and usage, pointers, malloc/free functions, singly linked list implementation and passing in/out arguments from functions.
-Week15.ppt. Nov 30 Vector-based implementation of complete binary Heap: VectorHeap. Use heaps in Dijkstra's shortest path algorithm.
-Week16.ppt. Dec 7. Implementation of binary tree and binary search tree.
Return to Zhihong's Homepage
Page Last Updated: 09/01/2005 12:08 AM