What follows is an schedule for the above course, giving a list of lectures and labs. This is an outline and may be subject to change.

W1 Intro to algs, classification of algorithms, example of algorithms TUESDAY 30/9 Intro to ADT's, coding conventions used throughout course (do, records, simple syntax). Describe "warm up" exercise LECTURE THURSDAY 2/10 W2 Lists, Stacks, Queues Linked lists (llist), and vector lists (vlist) Cursor implementation of linked lists (alist). LECTURE TUESDAY 7/10 Stack, as a llist and as a vector. Example of calculator using stack. Queues, as a linked list and as a circular list within a vector LECTURE THURSDAY 9/10 W3 A quick intro to Complexity, estimating run times t(n). Big-oh. The tyranny of growth, some examples, typical problems LECTURE TUESDAY 14/10 Sorting and Searching Sorting: insertion sort, bubble sort, merge sort as examples. Complexity. Lab examples to show relative performance of these algorithms as data set size increases LECTURE THURSDAY 16/10 W4 Searching ... look back over lists. Binary chop. The algorithm and its complexity. Description of exercise on sorting and searching LECTURE TUESDAY 21/10 Hashing ... open hashing. Exercise on Hashing Hashing ... closed. Collision avoidance/resolution LECTURE THURSDAY 23/10 W5 52.219 Lectures Cancelled W6 Permutations and Combinations The TSP and related problems. Scheduling. Complexity of (hopless but not serious:). Branch and bound. The use/value of lower bounds. Greedy algorithms, 2-opt for TSP, ... how good are they? A study of the TSP, from a naive solution onwards (a) all permutations, (b) pre-computation of cost matrix, (c) selection of next city, (d) cut-off lower bound, (e) 2-opt, (f) reducing cost of evaluating new tour when 2-opting LECTURE TUESDAY 4/11 Combinations. Complexity (again, hopless but not serious). Typical problems, selection, the power set. Backtracking search. Example, 0/1 knapsack problem. Complete versus greedy techniques. LECTURE THURSDAY 6/11 Introduction to 52.219 Challenge: an optimisation problem. W7 Trees, n-ary and binary Trees. What is a tree, typical instances/uses of trees. Implementing ADT's for trees. Insertion into a tree, traversal of trees and what those traversals correspond to. LECTURE TUESDAY 11/11 Binary trees. Two implementations, using records and arrays. Expressions in binary trees, binary tree implementation of sorted list, access time. Traversals, interpretation of those traversals, LECTURE THURSDAY 13/11 W8 Example of traversal using stack rather than recursion. Deletion from a binary tree. Arrays as a binary tree ie. left is (modulus i 2) LECTURE TUESDAY 18/11 Graphs, directed and undirected Directed graphs. Applications of graphs to real world problems (telecommunications, design of transportation systems (roads, power, water, sewage, etc), dependencies between objects) Typical questions to be answered of a graph Representation of directed graphs, as adjacency matrix, or correspondence list. Graph Algorithms I: Single Source Shortest Paths (Dijkstra's algorithm) LECTURE THURSDAY 20/11 W9 Graph Algorithms II: All Pairs Shortest Paths (Floyd's algorithm), Transitive Closure (Warshall's algorithm), Centre of a digraph ... LECTURE TUESDAY 25/11 Graph Algorithms III: Traversal of a Digraph depth first search (dfs), Strong Component (connected?) LECTURE THURSDAY 27/11 W10 Graph Algorithms IV: Undirected graphs, typical applications, typical questions to ask: Minimum cost Spanning Tree (Prim's alg), and Kruskal's, LECTURE TUESDAY 2/12 Graph Algorithms V: dfs again, articulation points, graph matching LECTURE THURSDAY 4/12 W11 Graph Algorithms VI LECTURE TUESDAY 9/12 52.219 Lecture cancelled LECTURE THURSDAY 11/12 cancelled W12 Revision Lectures LECTURE TUESDAY 16/12 Revision Lecture LECTURE THURSDAY 18/12

Do at least 50% of labs (marked with a *) for credit

The labs are a mix of coding and experimentation. That is, in some of the labs students take an empirical approach, investigating the behaviours of algorithms. Students will use tools to measure performance and display results, and develop those tools. There is one sizeable piece of work, the purpose is to encourage students to explore different techniques for a given problem, and investigate just how appropriate those techniques are. There is a prize for this piece of work.

When coding, students will be encouraged or forced to reuse code. Generally, students will be given pieces of code to modify. The lab work is detailed below

- 1. Warm up exercise to get reacquaintance with scm/emacs/unix/etc Students generally will have not used scm/emacs/unix for 5 months or more.
- *2. Implement ADT for circular queue or a stack. Write functions to add, remove, test for full and empty, and print contents. WEEK 3 & 4
- *3. The 52.219 Challenge. See below for details WEEK 6 to 11
- *4. Sorting, experiments on given algorithms and data sets. Investigate performance of algorithms as data set size increases. Algorithms and code (mostly) given. WEEK 5
- *5. Searching. Encode and test linear search and binary search. Perform trial over data set of 25,000 words from a dictioanry. Also compare with open and closed hashing (system and code given for open and closed hashing) WEEK 6 & 7
- *6. Height of a binary tree. Encode function to find height of a binary tree. Using random data generate binary trees and empirically estimate height of binary tree for a given data set size, and discuss implication for access time. Data generation will be given, along with code for creating and viewing (graphically) binary tree. WEEK 8 & 9
- *7. Connected? Given a graph, is it connected. Encode depth first search and use to determine connectivity. Code will be given for generation of random graphs. Perform experiments, such that probability of an edge is increased, relationship to connectivity (observation of a phase transition) WEEK 10 & 11

An optimisation problem will be given. In previous years this has been a 100 city travelling salesman problem (tsp), and the best solution delivered by the cut off date won a prize (typically a bottle of something that looks and tastes like Champagne). The challenge will amount to a sizeable software development for a non-trivial problem.