Course Home: http://www.cs.uiowa.edu/~sriram/21/fall05
TA: Zhihong Wang
Email: zhihwang@cs.uiowa.edu
Office Hours: 2-3, WF
Office: 311 MLH, 301 MLH (* office hours only)
- (9/1/05) Textbook example highArray.java is an array structure with high-level user interfaces: find, insert, delete. ResizableArray.java is an expandable array, that is, it can increase its capacity when it gets full.
- sep08.ppt. Running time of ResizableArray.java. Amortized running time. Multi-dimensional arrays. Quiz 1. Sample code: TriangleNumbers.java
- Quiz 1 solution.
- sep15.ppt. Java class Vector. Sample code: VectorTest.java.
- Sep22.ppt. Java Collection Framework. Sample code for practice problem: Company.java.
- Sep29.ppt. Overview of Project 1.
- Quiz 2 solution: myVectorGraph.java, graphTest.java.
- Oct20.ppt. Discussion of exam 1. Sample code: genKsubsets.java, myNewGraph.java.
- Oct27.ppt. Doubly linked list implementation. Sample code: DoublyLink.java, doubleLinkList.java.
- Nov3.ppt. Queue structures and implementation. Breath-first traversal of a graph. Breath-first traversal tree construction. The implementation in Project2.2.
- Nov10.ppt. Iterator structure and implementation. Quiz 3. Sample code: testIterator.java, which uses Lafore's class Link, LinkList and ListIterator (Textbook P.235 ~241). Project2.3.
Note: In GPSR, you may want to test if current vertex "cur " is equal to the destination "t" by using (curVertex != t), which can cause problem though. Since both "cur" and "t" are String references, operator != is comparing the two references values, instead of the contents of the two strings. To compare the strings, use function String.equals(String s). For instance,
Replace code like while(cur != t) with while (!cur.equals(t))
- Nov17. More clarification on GPSR. You can complete it in your project 3.
- Perimeter mode routing. If previous mode is greedy, then start from line(cur, t) to apply right-hand rule to select a neighbor with minimum counter-colockwise angle. If previous mode is also perimeter, then start from line( vertex in path before cur, cur) to apply right-hand rule.
- Counter-clockwise(CCW) angle calculation.
- If you are using cosine() in solution, make sure the arguments are consistent. Note that cosine(String cur, String t, String next) put the middle vertex as the first argument. But the angle function in my slides use arguments in (t, cur, next) order.
- Note that the CCW angle for vertex ( a, b, a) should regarded as 2π. instead of 0.0. Or you can treat it separately. Otherwise, GPSR may got stuck.
- Dec1.ppt Heap sort. Project 3 discussion. Min-heap, DSP implementation.
- Dec8.ppt Red-black tree. Examples.
Project 3, in GPSR, you can use the formula in this link to calculate the intersection of two line segments.
Download textbook examples, there are
Source and executable code for the example programs in the text.
The applets that graphically demonstrate common data structures and algorithms.
Sun Java 2 platform Standard Edition (J2SE)
Download Java Software Development Kit (SDK) - J2SEv1.4.2_09 SDK
Some free Java IDE and Editors
Page Last Updated: 12/08/2005 03:11 PM