Lecture Related Material  for 308-250A                     Autumn 1999

last update: Dec 6, 1999                                         return to: course home page

Java related material is found at http://www.cs.mcgill.ca/~jacob/cs250

Text
        Data Structures and Problem Solving Using Java,    M. A. Weiss

Dec 3: Review of the course: see the topics list gone over in class. This isn't a substitute for the exam information page which contains the "official" list of topics-recently revised to include Ch. 6 (except 6.7, 6.8).  Assignment 6 deadline extended to Monday Dec 6, noon.

Dec 1: Guest Lecture by Prakash Panangaden on Concurrent Programming, lecture notes are here. (Not covered on final exam)

Nov 29: Guest lecture by Claude Crepeau on Quantum Cryptography. (Not covered on final exam)

Nov 26: Computability: what can't we compute? First precise formalisms of computation in the '30s. Turing's model: the Turing machine. Turing's sad story. Example of a function which, provably, no algorithm can compute: the Halting Problem. Example of a procedure which may or may not halt (?): the 3n+1 Problem. 

Nov 24: Primality testing using two necessary conditions for primality: a^(p-1)=1 mod p , and x^2=1 mod p has only trivial solutions x=1,p-1 for p prime. Efficient randomized primality test using these facts and the fast exponentiation algorithm. Read pp.190-191 and pp.269-275. Code from class: power.html and prime.html
 Nov 22: Random and pseudorandom numbers: what are they and how to generate them. Uses in cryptography, simulation, test data generation, numerical analysis and randomized algorithms. Linear congruential random number generator. Read pp. 259-265.

Nov 19: O(nlogn) convex hull algorithm by sorting and linear scan. Diameter by rotating parallel supporting lines. Geometric primitives for left and right turns. See handout for Nov 17.

Nov 17: Introduction to Computational Geometry. The diameter problem and the convex hull. Naive algorithms for both. Discrete Geometry and Paul Erdos. Start to read the Convex Hull handout (text, figures) - also available at COPI-EUS.

Nov 15: Binary search tree algorithms for insertion and deletion. Java implementations. Read pp. 494-499 and study the code. Also read 18.3, pp 504-508.

Nov 12: Expression trees and relation to prefix, infix, postfix notation. Binary search trees: insertion and find. Definition of balanced tree and related complexity issues. Read pp. 489-495.
Footnote: The number of distinct binary search trees that can be built from n distinct keys is not n! For example the sequences  3 1 4 2 and 3 4 1 2 give the same tree. The number of binary search trees is the same as the number of binary trees on n nodes, which is the Catalan number binomial(2n,n)/(n+1).

Nov 10: Binary trees and operations size, height, print{Post,In,Pre}order, duplicate. Complexity analysis to show O(n) running time. Read pp 463-472. Skip implementation by iterator classes.

Nov 8: Trees. General trees and their representation by binary trees. Preorder and Postorder list algorithms. Read Sections 6.5 and 17.1

Nov 5: The intuitions behind stacks and queues. Simple data structures with O(1) (fast!) insert/delete, but no choice about what to delete. Stack = LILO = pile. Queue = FIFO = buffer. Stacks often easier to implement, but don't fairly preserve ordering like queues. Local memory. Cassettes. Rotting apples. A very simple (list-based) Java implementation: Stack.java. 

Nov 3: Object-oriented design: why? (Becomes useful when writing/designing large programs.) Types (= sets). Subtypes (= subsets). A lame Socratic analogy. Subclasses (= subtypes). Type relationships: Button and Label are subclasses of Component, which is a subclass of Object. 

Nov 1: Parsing. Postfix evaluation. Infix to Postfix conversion. Section 11.2.1 and 11.2.2. You are not responsible for the details of the code in 11.2.3 but should at least look at Fig 11.18 which is the heart of the postfix evaluator. Also note the methods in Fig. 11.14 which are another  way to hide the type casting needed when using generic stacks.

Oct 29: More on Stacks. Balanced parenthesis checking. Code presented in class: IsBalanced.java. Read Weiss Section 11.1 and take a look at his code. This is more sophisticated, since it handles quotes and parentheses and gives the location of an unbalanced parenthesis. You are not responsible for all of the details of Weiss' code.

Oct 27: Introduction to data structures as Abstract Data Types and Java interfaces. Definition of stack with small sample program, Weiss pp. 143-148.

Oct 25: Problems with just using cells: insertions/deletions at the front. Packaging Cells in a separate List object. In Java: UnorderedList.java. The null keyword. How to insert, delete, check for membership. Printing out a list. OrderedList.java. (See A Little Book on Java.) 

Oct 22: What is a data structure. Arrays, pros and cons. Linked lists. Cells: Cell.java. How we combine cells to form lists. Thinking of a cell as a list. Sorted vs unsorted lists. 

Oct 20: Good Code. Some fundamental criteria. Code should be: Correct. Efficient. Comprehensible (critical, underrated): Make it readable so people can use and change it. (Concise. Consistent.) Reusable (critical, underrated): Make it general. Write it once. Modifiable: Should be easy and safe to update. (Nonredundant.) Extensible: Should be useful when we want to do other, similar things. More about this later (inheritance). 

Oct 18: Recursion and abstraction. How recursion is useful: the parallel with induction proofs. How to write a recursive procedure: Eights.java. Pros and cons of tracing recursions. Abstraction: forgetting how a procedure works when you call it. 

Oct 8: Analysis of the equation T(n)=2T(n/2)+n, T(1)=1 obtaining the solution T(n)=O(n log n) (see Weiss, 201-4). Code for
merge and mergesort. Introduction to Quicksort.

Oct 6: Code for Insertion sort and Selection sort. Analysis as O(n^2) algorithms in the worst case. Divide and Conquer and Merge
sort. Weiss: sections 8.1,8.2,8.3.8.5.

Oct 4: More Big-O notation. Examples from handout: inequality and limit method. Meaning of constants, limitations and short-cuts.

Oct 1: Big-O notation. Definitions and examples. Handout at ftp://mutt.cs.mcgill.ca/pub/courses/250/bigO.ps or COPI-EUS.

Sept 29: Material from chapter 5, especially cubic, quadratic and linear algorithms for the maximum subsequence problem. Complete code for all of these with a driver is available at ftp://mutt.cs.mcgill.ca/pub/courses/250/weiss/Software/Chapter05/MaxSumTest.java

Sept 27: Primitive types (int, boolean) vs reference (object) types (String, Point1). Variables (references) vs objects: Point1.java, Point1Test.java. Objects as packages containing data (fields) and operations (methods). Non-static methods. Constructors: Point2.java, Point2Test.java. The . (dot) operator. The this keyword. 

Sept 24: Objects, classes, and non-static methods. Calling a static method in another class: Factorial.java. Access modifiers (public, private). Classes as units for organizing code. Classes as type definitions. Non-static (instance) methods (charAt()): Strings.java. 

Sept 22: More Java without objects. Debugging with System.out.println(). Array declaration and initialization: Arrays.java. Exceptions (try, catch, throws): Doubler.java. How objects are used, intuitively: Strings.java. 

Sept 20: Basic Java syntax. Compiling and running Java programs: First.java. Why "the industry" is so excited about Java. Iteration constructs (while, for) and recursion in Java: Factorial.java. (All covered in A Little Book on Java) 

Sept 17:  Trace of Towers of Hanoi. Fibonacci numbers as a bad application of recursion. Trace of Fibonacci code(java code for this will be posted on the java site above). Growth rate of running time: exponential growth rate vs polynomial. Fibonacci numbers as the worst case example for Euclid's gcd algorithm.

Sept 15:   Code for Tower of Hanoi (java version at http://www.CS.McGill.CA/~jacob/cs250/java/Towers.java). Analysis of
                  number of moves, T(n) for a n ring game. Derivation of the recurrence equation T(n)=2T(n-1)+1, T(1) =1
                   which has solution T(n)=2^n   - 1. Proof that this is the minimum number of moves.

Sept 13:     Material on recursion including the jeep problem(see Sept 10), showing T(1)=300, T(2)=600, T(3)=700, T(4)=800, T(6)=880. The simple recursive solution give T(n)=300+300/(2n-3), but is not optimum. Introduction to Towers of Hanoi.

Sept 10            Introduction to recursion: Section 7.1 -7.3.  Tracing recursive programs.
Jeep Problem: A jeep has an empty gas tank and is stranded in the desert. The driver has n cans of gasoline, and one can fills the gas tank. The jeep can carry one can of gas in addition to whatever is in the tank. Find T(n), the distance that the jeep can go with n cans of gas, given that it can go 300km on one full tank.


Sept 8     Weiss Section 7.4, introduction to numerical algorithms  and RSA cryptography

Sept 3     Mersenne Primes.