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.