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.
|
|