# 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