52.219 Schedule

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.

Lectures

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

Compulsory Exercises/Labs

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

Labs/Exercises

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

52.219 Challenge

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.

Demo Software

Almost all of the course is supported by demo software. For example, there's software for to show graphically sorting, the graph algorithms, binary trees. There's also software for searching , etc. You are expected to run those demos as part of the course.

Course Material

All course material is made available electronically in /home/s7/pat/scheme/pub See file README