52.219 Home Page

Techniques and Functional Interpretation of Programs

The course is taught by Patrick Prosser. Please feel free to email or phone me on extension 4303.

Although the course title may sound rather (well, I don't know) it is in fact about algorithms and abstract data types.

Submitting Course Work

All course work should be emailed to cs219

Lecture Notes

The lecture notes will be released as the course progresses. So this page will be added to as we go along. You can get the notes (and overheads) below.

Notes 0: overhead transparencies are in postscript and can be viewed with ghostscript or gs (or just by left clicking). The lecture was on algorithms; that is "what is an algorithm, what does it look like, is it interesting?".
Notes 1: Intro to abstract data types, lists, stacks, queues, etc., also the overheads and
Notes 2: Getting started with scheme in 52.219
Notes 3: on complexity
Notes 4: on sorting
Notes 5: on hashing
Notes 6: on the travelling salesman problem (tsp)
Notes 7: on the knapsack problem
Notes 8: on trees
Notes 9: on binary trees
Notes 10: on graphs and Dijkstra's algorithm
Notes 11: on all pairs shortest path (APSP)
Notes 12: on depth first search (dfs)
Notes 13: on being connected
Notes 14: on the minimum spanning tree (mst)

Exercises and Answers

Exercises (and in time answers) are below. All course work should be emailed to cs219

Exercise 0. Due Thursday 16th October at 13.00 hours and its Answer 0.

Exercise 1. Due Friday 24th October at 12 o'clock and its Answer 1.

Exercise 2. Due Friday 7th November at 12 o'clock. and its Answer 2.

Exercise 3. The tsp challenge. Due Friday 12th December at 12 o'clock. Current best solution due to Stephen Murtagh at 2/12/97

Exercise 4. Due Friday 21st November at 12 o'clock and its Answer 4.

Marks for the labs

The marks for the labs are here.