Algorithms and Complexity
2004-2005

Links

• Aims, Objectives and Syllabus
• Timetable

Overview

Following on from Programming Techniques this module looks in detail at different algorithms (recipes) for solving problems with large chunks of data.

The course text is Java Collections: An Introduction to Abstract Data Types, Data Structures and Algorithms by David A. Watt and Deryck Brown. We will cover the material as follows

• Chapters 1 2 3 covered
• Chapters 4 5 6 7 8 10 built upon but not covered here
• Chapters 9 related but not really covered
• Chapters 11 12 13 14 15 17 covered
• Chapters 16 touched on

The lecture notes have indicators as to which chapters are relevant to each section.

Many of the links below here are in PDF format

Lecture Notes

To follow as the course proceeds:

• Lectures 1: Introduction
• Lectures 2: Searching & Sorting
• Lectures 3: Heaps, Hash, Priority & Compression
• Lectures 4: Graphs
• Lectures 5: Games, Knapsack, NP-C
  •    Notes on Knapsack solutions (from Patrick Prosser)

Additions

• Newsgroup: strath.cis.teaching.ug.ac
•  
• Amorphous guide to Big-Oh Notation
•  
• PhoneDirectory Map example  (server folder with readme, browsable folders and compressed folder (zip-archive) for downloading)

Exercises

Laboratories for A&C will, in general, not be formally scripted. The labs will be staffed by demonstrators and it is up to students to make good use of the lab to help learn the material and complete both the assessed exercises and non-assessed exercises. See the lab allocation for which lab to attend.

Assessed Exercises

There will be three assessed exercises on this course:

1. Assessment 1: Sorting - due at start of your first lab after 3 March - worth 6% max
   • AlgBasicDriver.java
   • sortingfiles.zip
2. Assessment 2: Congestion Charging - due at start of your first lab after 16 March - worth 7% max
   • spotted.txt
   • paid.txt
3. Assessment 3: Mobile Phone Text Entry - group project - various deadlines - worth 7% max
   • Deadlines (all absolute and all required):
     • 11 March - notify Mark Dunlop of your groups;
     • 1 April - submit a one page design document;
     • week of 25 April - demonstrate your solution in the lab;
     • 4 May - submit an individual assessment form.
   • Resources:
     • 8k.txt
     • 77k.txt
4. Outstanding Coursework - individual assessment for those needing to clear OC - deadline 1 August (passing = 8/20)

Non-assessed practicals exercises:

In addition a series of non-assessed practical exercises will be set: while not assessed these will help understanding of the course and will not have deadlines.

• Practical 1: Introduction to algorithm analysis
  • try from week 2
• Practical 2: Hash Tables
  • try from mid week 5
• Practical 3: General
  • try from week 11

Past Exam Papers

The exam format will change for 2005 as the exam will be open book for the first time. This will change the nature of questions a little but will not change the overall style or topics being examined. The exam paper starts: "This is an open book exam – the course text and any written notes are permitted. No electronic devices (inc calculators and phones) are permitted on desks. Attempt THREE questions" [from four]. The printed course notes are also permitted.
 

• Summer 2005 - Autumn 2005
• Summer 2004 - Autumn 2004
• Summer 2003 - Autumn 2003
• Summer 2002 - Autumn 2002
• Summer 2001 - Autumn 2001

Prior to 2001 the course was called Algorithms and Data Structures and was a combined course with Programming Techniques - course material is very similar but exam style is different. If you do these two past papers and the three practicals above and have understood the course notes you should be in a very good position for the exam.

Some Links to stuff that might be useful

• Excellent AVL tree animation by Arsen Gogeshvili (not needed for A&C but handy and good for prog techniques)
• General Animated Algorithms by Woi Ang (mostly)