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

2009-2010, Semester 1

Research@NoU-CS          
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

G54AOR: ALGORITHM DESIGN and Operations Research

This is a 20 credits module (see module specification) and consists of two parts: Algorithm Design (taught by Ender Ozcan) and Operations Research (taught by Dario Landa-Silva) This document provides information on the Algorithm Design part. See also the page for the part on Operations Research.

Until this year, the focus of the module has been the principles of program verification and their application to a variety of programming problems. This year, 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 2009-2010):
  • Monday 16:00-18:00 (Algorithm Design part) in JC-EXCHGE-D.LT3+
    Office hours: Thursday 11:00-14:00 (Algorithm Design part) in School of Computer Science C41
    Please book an appointment via email (see left-hand side) before your visit.
  • Thursday 9:00-11:00 (Please check with the timetabling office for the locations from here)

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

Syllabus

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.
IMPORTANT NOTICE: There will be no class on 19th of November. The following week, both sessions will be used for the OR part (23rd and 26th of November)
Lecture 0 - Introduction
Suggested Reading: Jeff Edmond's introduction

Lecture 1 - Proof methods revisited: Direct proof, Strong induction, Weak induction, Proof by contradiction [PDF]

Lecture 2 - Algorithms: Efficiency, Analysis, and Order [PDF]

Lecture 3 - Asymptotic Notations and Recurrence [PDF] - updated 22.10.2009
(AD and OR lectures are swapped: 19th-22nd of October)

Lecture 4 - Methods for solving recurrence equations [PDF]

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

Lecture 6 - Binary multiplication, Matrix multiplication, Quicksort - average case analysis [PDF]

Lecture 7 - Dynamic Programming: Binomeal Coefficient, chained matrix multiplication [PDF]

Lecture 8 - Subset sum problem, Edit distance, Floyd-Warshall Algorithm for shortest paths problem [PDF]

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]

Assesment

  • Course Work (20% for the AD part)
    See the Coursework specification for 2009-2010.

    See the answers to the questions 1-5.

    -NEW-
    Please click here for the final coursework marks.
  • Examination (60%)
    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.