MA407: Algorithms and Computation

Course materials

Homework (further below on this webpage)

Setting the PATH variable when installing Java on Windows XP

Overview of topics covered, additional links, and handouts.
Please note: weeks numbered 1,2,3,4,5 are taught in weeks 1,3,5,6,9 of MT,
weeks 6,7,8,9,10 in weeks 1,3,5,7,9 of LT.

week	topic and additional links	suggested reading
1	Binary system. ASCII and Unicode. Number systems: octal and hexadecimal, scientific notation. Integer representation, signed integers, floating point arithmetic. Basic computer operation. Computer architecture: for the preceding links, and further information, see An Assembly Language Introduction to Computer Architecture by Karen Miller, Oxford University Press (1999), and its online summaries (detailed links above).	The IEEE standard for floating point arithmetic Using Java at the LSE.
2	Structure of a Java program. Example of a Java program ( SomeNumbers.java ), compiling and running it. Class definition, method definition, parameter lists. Statements: declarations, assignments, if/else and while. Arithmetic and Boolean expressions. Grouping { } of statements. The for( ; ; ) statement (iterative loop). Special operators like +=. Indenting program text.	Java syntax (slides).
	Arrays. Arrays in Java. The new command.	pages 65-67 of D. Flanagan (1999), Java in a Nutshell, 3rd edition.
3	Sorting by Insertion.	SortTest.java Slides sort.pdf See Introduction to Algorithms by Cormen/Leiserson/Rivest [CLR] (references to CLR are to the first edition, 1990), Chapter 1, "Introduction".
	O-notation.	CLR, Chapter 2, "Growth of functions".
	Merge sort. Recursive call to "mergesort", the merge function. output of MergeSort with indentation according to level of recursive call	MergeSort.java Slides merge.pdf (first page blank) merge with auxiliary variables L, U, upperempty
4	Analysis of Mergesort.	CLR, Chapter 1, "Introduction".
	Implementation of recursive calls: parameters and local variables on system stack.	More examples of recursion (summary notes).
	Animation of the sorting algorithms
	Lower bound for sorting: Theta(n log n) binary comparisons need to sort n elements, considering the depth of a binary decision tree with n! leaves, which is proportional to n log n.	Slides lbsort.pdf See CLR, "Sorting in Linear Time", pages 172-174.
	History: Data records, dot-notation for accessing fields. Instance fields and instance methods in Java, defined by absence of static modifier. Class fields and class methods in Java, defined by presence of static modifier.	"Classes and Objects", pages 61-64, Chapter 2, and "Object-Oriented Programming in Java", pages 82-89, Chapter 3, of D. Flanagan (1999), Java in a Nutshell, 3rd edition.
5	Linked Lists.	CLR, Section 11.2, pages 204-208 List.java Slides list.pdf
	Binary search trees. Animation of tree insertion/deletion.	CLR, Chapter 13, pages 244-262 Tree.java Slides tree.pdf
	Successors in binary search trees. Deletion of nodes in binary search trees.	TreeDel.java CLR, Section 13.3, pages 250-254
6	Average node depth of randomly built binary search trees.	CLR, Chapter 13, pages 260-261 Evaluating the recursive formula for the average internal path length of a binary tree
	Balanced trees: 2-3 trees, where each node has 2 or 3 children and stores, correspondingly, 1 or 2 values. All leaves have the same depth, and each leaf may contain 1 or 2 data items. Insertion of a new item occurs at a leaf, and when a leaf is full, the middle of the three items is `pushed upwards', possibly all the way up to the root. See 2-3 Trees by AIhorizon	2-3 Trees by Samuel L. Marateck, 1998. 2-3 tree insertions (slides). CLR only explains the more general and more complicated B-trees (Chapter 19).
7	Hash tables: direct addressing, collision resolution by chaining, open addressing with probe sequence. Successful and unsuccessful search times.	CLR, Chapter 12, pages 219-243 Hash functions - slides. Deleting an entry from an open-address hash table.
8	Directed and undirected graphs. Trees, paths. Degree of a node. Adjacency tables and adjacency lists. Implicitly defined graphs. Breadth First Search (BFS), Depth First Search (DFS).	Slides BFS / DFS. DFS visit times. CLR, pages 465-485 Graph Algorithms. DFS statements about graphs.
9	Minimum spanning trees. Generic MST, Kruskal's algorithm. Prim's algorithm	some graphs Slides on Minimum Spanning Trees and on Dijkstra's algorithm. CLR, Chapter 24, pages 498-513
	Union/find problem.	CLR, Section 22.3, pages 446-450
	Dijkstra's algorithm for single-source shortest paths.	CLR, Sections 25.2 and 25.2, pages 514-532
10	Garbage collection: reference count, mark-sweep, Cheney's copying collector as use of breadth-first search.	Uniprocessor Garbage Collection Techniques (pages 15-20 not handed out) by Paul R. Wilson, Proc. 1992 Int. Workshop on Memory Management, Lecture Notes in Computer Science, Springer-Verlag.
	Universal family of hash functions. Constructing a perfect hash table in linear expected time.	Construction of a perfect hash table with linear space in linear expected time. See also the new Section 1.5 in Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms, Second Edition (not in the first edition), pp. 245ff.

Homework

Week	Date	due	Exercise	Model Answers