COMS10007 Algorithms - 2018/2019 (TB2)

News:

August/September Exam Similar to the May/June exam, there won't be questions that explicitly ask for the RAM model, 2D peak finding, maximum subarray, exercise sheet 4, and loop invariants in the August/September exam.
22.05.2019 Possible answers to the mock exam can be found here: mock exam solutions
10.05.2019 A mock exam can be found here: mock exam. As mentioned in the lecture, an exam only tests a subset of the relevant material. Please do not base your preparation solely on this mock exam. I will post solutions at the end of next week. Good luck with your preparations and get in touch (e.g. piazza, email, etc) if you have any questions.
12.04.2019 Solutions to exercise sheet 3 are now online: Solutions sheet 3
18.03.2019 Grades for the in-class test have been released. Solutions can be found below.
11.03.2019 Solutions to Mock In-class test Due to multiple demands, here are possible solutions to the Mock in-class test: Solutions - Mock in-class test
08.03.2019 In-class test on March, 12th - EXTRA TIME. If you are granted extra time during exams, please take the test in MVB3.44. at 3pm (don't be late!). Dr David Bernhard will supervise you during the test.
05.03.2019 In-class test on March, 12th. We will have our in-class test during the exercise class on March, 12th from 3pm-4pm in MVB 1.11. If you are allowed extra time during exams, please get in touch with me as soon as possible.

All material discussed in the lectures up to and including Heapsort or discussed in the two exercise sheets is relevant (Quicksort is not relevant for the in-class test, I also exclude the peak finding problem).

I created a mock in-class test: mock in-class test.

This mock paper is slightly harder than the actual in-class test. The purpose of this mock test is to give you an idea about the difficulty level of the in-class test.
03.03.2019 Loop invariants are a difficult concept. Here are some additional notes that may help you with the material. These notes also contain a few exercises in case you would like to practice more. Note on Loop Invariants
28.02.2019 The solutions to Worksheet 2 are now available. Solutions sheet 2
19.02.2019 Worksheet 2 is now available. Attention: Observe that Exercise 3.2. is wrong and cannot be proved. I updated the worksheet with a counter example.
08.02.2019 Solutions to worksheet 1 are now online. We will discuss the 2D peak finding algorithm at a later stage in class (no solution for this exercise is provided yet). I created two solution sheets: One with additional explanations, and one without. Solutions - long Solutions - short
05.02.2019 Worksheet 1 is now available online. Solutions will be provided soon. Please make use of the Drop-in sessions, Piazza, and my office hours to discuss the exercises and/or get help.
28.01.2019 You can enroll at our discussion board using the link: COMS10007 - Piazza
28.01.2019 Welcome to COMS10007!

Teaching Staff:

Unit Director: Christian Konrad
TAs: Thomas Delaney, Igor Dolecki, Nazaal Ibrahim, David Manda, Perla Jazmin Mayo Diaz de Leon, Matthew Owusu, Theano Xirouchaki

Teaching Units:

Lectures (21x): Mondays 10-11am, Tuesdays 2-3pm, Room PHYS BLDG G42 POWELL, Instructor: Dr. Christian Konrad
Exercise classes/in-class test (5x): Tuesdays 2-3pm (every fortnight), Room MVB 1.11
Drop-in Sessions: Thursdays 5-6pm in 3.44MVB in weeks 13-15, 17, 19-24, and Fridays 1-2pm in 3.44MVB in weeks 13-17, 19-23

Assessment:

Exam: Counts 90% towards your final grade
One in-class test (on March 12th), counts 10% towards your final grade
You pass the course if your final grade is at least 40%

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:

Christian Konrad (MVB 3.06): Tuesdays, 4pm-5pm

Questions?

Consult the excellent recommended textbook
Come to our drop-in sessions
Use the course page on Piazza for asking questions and discussions: https://piazza.com/bristol.ac.uk/spring2019/coms10007
Come to my office hours

Schedule

Week	Day	Date	Topics	Slides
13	Mon	28-Jan	Lecture 1: Introduction, peak finding	PDF
	Tue	29-Jan	Lecture 2: O-notation	PDF
			Remarks: Throughout this course, log(n) denotes the binary logarithm, i.e., log(n) = log₂(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.
14	Mon	04-Feb	Lecture 3: Theta, Omega, RAM Model	PDF
	Tue	05-Feb	Lecture 4: Linear and binary search, proofs by induction	PDF
	Tue	05-Feb	Exercise class 1	Worksheet 1
			Remarks: Exercises on O-notation, Omega, and Theta can all be solved by finding constants c,n₀ 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
15	Mon	11-Feb	Lecture 5: Loop invariants, insertion sort	PDF
	Tue	12-Feb	Lecture 6: Sorting problem, first part of merge sort algorithm	PDF
16	Mon	18-Feb	Lecture 7: Second part of merge sort, maximum subarray problem (slides of lectures 6 and 7 are combined)
	Tue	19-Feb	Lecture 8: Trees, first part of heap-sort	PDF
	Tue	19-Feb	Exercise class 2	Worksheet 2
				Solution
17	Mon	25-Feb	Lecture 9: Second part of heap-sort (slides of lectures 8 and 9 are combined)
	Tue	26-Feb	Lecture 10: Quicksort	PDF
18			Reading Week
19	Mon	11-Mar	Lecture 11: Runtime of Quicksort	PDF
	Tue	12-Mar	Lecture 12: Sorting LB, Countingsort, Radixsort	PDF
	Tue	12-Mar	In-class Test	In-class Test
				Solution
20	Mon	18-Mar	Lecture 13: Recurrences (substitution method, recursion-tree method)	PDF
	Tue	19-Mar	Lecture 14: Recurrences continued (slides of lectures 13 and 14 are combined)
21	Mon	25-Mar	Lecture 15: Fibonacci Numbers	PDF
	Tue	26-Mar	Lecture 16: Dynamic Programming - Pole Cutting	PDF
	Tue	26-Mar	Exercise class 3	Worksheet 3
				Solution
22	Mon	01-Apr	Lecture 17: Dynamic Programming - Matrix Chain Parenthesization	PDF
	Tue	02-Apr	Lecture 18: Elements of Dynamic Programming 1	PDF
			Easter Break
23	Mon	29-Apr	Lecture 19: Elements of Dynamic Programming 2	PDF
	Tue	30-Apr	Lecture 20: Peak Finding in 2D	PDF
	Tue	30-Apr	Exercise class 4	Worksheet 4
24	Mon	06-May	Bank Holiday Monday - no lecture
	Tue	07-May	Lecture 21: Preparing for the Exam	PDF