The final exam will be on Friday, December 14 from 8:00 to 10:30.
This is a course on algorithms and data structures, concentrating on data abstraction and object-oriented programming. See the syllabus.
MW 12:30-2:00, TTh 11:00-12:00, or by appointment.
You can find documentation on Java classes at http://java.sun.com/j2se/1.5.0/docs/api/index.html.
Lab assistants are available during certain hours for assistance. See the following pages. (These pages might not be up to date yet.)
[8/23/07] We went over the syllabus, and began to look at ideas of modular programming, abstract data types and object-oriented programming. The first small assignment, just a warmup, is available.
[8/28/07] We discussed principle components of classes, including instance variables, instance methods, constructors, class variables, class methods, class initializers and finalizers. We wrote a simple string class to illustrate.
[8/30/07] Quiz. We talked about elementary inheritance, including protected visibility. A protected variable or method is visible in the class where it is created and in all of its subclasses.
[9/4/07] We did some review of Java and object-oriented programming, then looked more at inheritance. We saw that a variable of type C, where C is a class, can hold a pointer to an object of class C or any subclass of C. For example, a variable of type Mammal might contain an object of class Giraffe, if Giraffe is a subclass of Mammal.
[9/6/07] We looked at abstract classes and abstract methods. Then we began to examine ideas on grammars and parsing that will be necessary for the first large assignment.
[9/11/07] We began an example solution of a parsing problem using an object-oriented parser.
[9/13/07] We continued to look at a examples of object-oriented parsing.
[9/18/07] We began looking at an example of taking the derivative of an expression symbolically by translating between strings (the surface layer) and trees (the deep layer), and doing processing on the trees.
[9/20/07] Quiz. We went over the quiz, and then looked at the cost of building up strings using concatenation, which can be high.
[9/25/07] We continued the example started in 9/18.
[9/27/07] We looked at principles of discrete event simulation, which the next programming assignment will involve.
[10/2/07] We began looking at algorithmic issues, with an example problem of finding the distance between two strings. We tried some algorithms, but concluded that some disciplined approach to designing the algorithm would be required.
[10/4/07] Quiz. We continued to look at the problem of computing the distance between two strings, and managed to develop a recursive algorithm that is relatively short and solves the problem. The next issue, which we did not do, is whether the algorithm is very efficient.
[10/9/07]
[10/11/07] We briefly went over issues on the quiz, then began looking at the rickety bridge problem. (A group of people are on the West side of a rickety bridge, and need to cross to the East side. Only two people can cross at a time. It is night, and anyone crossing must carry a flashlight. There is only one flashlight. The people walk at different speeds. If two people walk together, they walk at the speed of the slower person. The goal is to cross in the least total amount of time.) Initial attempts at solving it led to incorrect greedy algorithms. Another approach that tries all possible solutions and selects the best one is correct, but very slow when there are a lot of people. (For 8 people, it requires looking at over 8 billion possibilities, and for 10 people it is over 900 trillion possibilities.)