G54ALG: ALGORITHM DESIGN
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
Syllabus
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)
Assesment
-
Course Work (50%)
Please see the Coursework
specification
for 2010-2011.
Some sample input files for testing your implementation in
Q6(c):
-
sample1_2010.txt
-
sample2_2010.txt
See the solutions
to the coursework questions 1-6(b).
-NEW-
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.
|
|
