The University of Nottingham Homepage The University of Nottingham Homepage School of Computer Science Homepage
Computer Science Home  

2010-2011, Semester 1

The LANCS Initiative
ASAP Research Group

Ender Özcan
Office: C41
T:+44(0) 115 84 66569
F:+44(0) 115 9514254

exo At cs-nott-ac-uk (replace all - with dot)

Home Research Publications Activities Teaching


Algorithm Design (taught by Ender Ozcan) is a 10 credits module (see module specification).

The focus of the lectures will be to provide a sound foundation in mathematical methods and develop the skills needed to construct/design algorithms. Basic methodologies for designing efficient algorithms to solve a variety of problems and the theoretical foundations required for analysis of algorithms will be covered.

Two lectures per week (See the timetable for 2010-2011):
  • Wednesday 11:00-13:00 in JC-EXCHGE-C3+
    Office hours: Wednesday 13:30-15:30 in School of Computer Science C41
    Please book an appointment for a meeting via email (see left-hand side).

Text for reading:
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms
  • L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics
  • R. Neapolitan, and K. Naimipour, Foundations of Algorithms
  • Jeff Edmonds, How to Think about Algorithms


The relevant chapter from the first text book for each lecture is provided below. Lectures cover more (or less) than what is provided in the "Introduction to Algorithms" chapters. Lecture notes will be provided in here as a PDF file. Attendance is strongly suggested, as the lecture notes will be in the form of "skeletons" with blanks, which you will have a chance to fill out during the lectures. Hence, if you miss a lecture, ask a colleague for the lecture notes. Do not rely on the notes being posted here.
Lecture 0 - Introduction
Suggested Reading: Jeff Edmond's introduction

Lecture 1 - Proof methods revisited - Direct proof, Inductive proof: Strong and weak induction, Proof by contradiction, Counter examples, Pigeon hole principle, Mathematical foundations - Floors and ceilings, polynomials, monotonicity, exponentials, logarithms, summation, counting (Ch 2.2, 3, 6) [PDF]

Lecture 2 - Algorithms: Efficiency, Analysis, and Order (Ch 1) [PDF]

Lecture 3 - Asymptotic Notations and Recurrence (Ch 2.1) [PDF]
- Tower of Hanoi applet (MazeWorks)

Lecture 4 - Methods for solving recurrence equations: substitution, changing variables, recursion trees, master theorem, using characteristic equation (Ch 4) [PDF] (updated on 3rd Dec: page 4)

Lecture 5 - Divide and Conquer: Binary Search, Mergesort, Maximum subsequence sum problem [PDF] (Ch 1.3)

Lecture 6 - Binary multiplication, Matrix multiplication, Quicksort - average case analysis [PDF] (Ch 31.2, Ch 8)

Sorting applets:

Lecture 7 - Dynamic Programming: Binomeal Coefficient, chained matrix multiplication [PDF] (Ch 16)

Matrix Chain Multiplier by Brian S. Borowski

Lecture 8 - Subset sum problem, Edit distance, Shortest paths problems, Floyd-Warshall Algorithm for shortest paths problem (Ch 16, 26) [PDF] (updated on 3rd Dec: Edit Distance subsection)

Lecture 9 Greedy Approach: Change problem, Minimum Spanning Trees - Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm for single source shortest paths, Knapsack Problems [PDF] (Ch 17)


  • Course Work (50%)
    Please see the Coursework specification for 2010-2011.

    Some sample input files for testing your implementation in Q6(c):
    1. sample1_2010.txt
    2. sample2_2010.txt

    See the solutions to the coursework questions 1-6(b).

    Please click [here] for the provisional coursework marks and feedback. If you have any objections or if you do not see your name in the list please contact me as soon as possible.
  • Examination (50%)
    Please have a look at the helpsheet that will be provided during the exam. [PDF]

    See the sample examination questions.
  • Resit Assessment
    Resit assessment will be conducted by 100% written examination. Following the rules in the CS staff handbook, the resit exam paper will mirror the normal sit exam paper. The exam will have a duration of 3 hours. There are 2 sections with 3 questions in each section. Each question is worth 25 marks. Students have to answer 2 questions in each section.