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
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.