COMS10007 Algorithms - 2018/2019 (TB2)

News:
Teaching Staff: Teaching Units: Assessment: Textbook/Course Material:
Most of the lectures will be taught using slides. Slides will be made available online (below on this webpage) soon after the lecture. An excellent and more detailed coverage of many of the topics (however not all of them) treated in this course is given in:

"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein, 3rd edition, The MIT press, 2009 .

I highly recommend this textbook. It is the standard textbook for basic algorithms courses and is based on the material taught at MIT. It will be useful for all algorithms courses at the University of Bristol (2nd year Data Structures and Algorithms, 3rd year Advanced Algorithms).

Office Hours: Questions?

Schedule

WeekDayDateTopicsSlides
13Mon28-JanLecture 1: Introduction, peak finding PDF
Tue29-JanLecture 2: O-notationPDF
Remarks: Throughout this course, log(n) denotes the binary logarithm, i.e., log(n) = log2(n). In the slides used in the lecture the derivative of log(n) was wrongly computed with 1/n, while it should of course be 1/(n ln(2)), with ln(n) being the logarithm to base e. I corrected this in the slides.
14Mon04-FebLecture 3: Theta, Omega, RAM ModelPDF
Tue05-FebLecture 4: Linear and binary search, proofs by inductionPDF
Tue05-FebExercise class 1Worksheet 1
Remarks: Exercises on O-notation, Omega, and Theta can all be solved by finding constants c,n0 such that the definition of Big-O (resp. Theta, Omega) is fulfilled. Recall that any constants that fulfill the respective definition are fine, i.e., you do not need to find the smallest ones. Solutions will be provided soon.Sol. - long
Sol. - short
15Mon11-FebLecture 5: Loop invariants, insertion sortPDF
Tue12-FebLecture 6: Sorting problem, first part of merge sort algorithmPDF
16Mon18-FebLecture 7: Second part of merge sort, maximum subarray problem (slides of lectures 6 and 7 are combined)
Tue19-FebLecture 8: Trees, first part of heap-sortPDF
Tue19-FebExercise class 2Worksheet 2
Solution
17Mon25-FebLecture 9: Second part of heap-sort (slides of lectures 8 and 9 are combined)
Tue26-FebLecture 10: QuicksortPDF
18
Reading Week
19Mon11-MarLecture 11: Runtime of QuicksortPDF
Tue12-MarLecture 12: Sorting LB, Countingsort, RadixsortPDF
Tue12-MarIn-class TestIn-class Test
Solution
20Mon18-MarLecture 13: Recurrences (substitution method, recursion-tree method)PDF
Tue19-MarLecture 14: Recurrences continued (slides of lectures 13 and 14 are combined)
21Mon25-MarLecture 15: Fibonacci NumbersPDF
Tue26-MarLecture 16: Dynamic Programming - Pole CuttingPDF
Tue26-MarExercise class 3Worksheet 3
Solution
22Mon01-AprLecture 17: Dynamic Programming - Matrix Chain ParenthesizationPDF
Tue02-AprLecture 18: Elements of Dynamic Programming 1PDF
Easter Break
23Mon29-AprLecture 19: Elements of Dynamic Programming 2PDF
Tue30-AprLecture 20: Peak Finding in 2DPDF
Tue30-AprExercise class 4Worksheet 4
24Mon06-May
Bank Holiday Monday - no lecture
Tue07-MayLecture 21: Preparing for the ExamPDF