COMS10007 Algorithms - 2019/2020 (TB2)

News:

17.04.2020 Solutions to the in-class test are here. Please check blackboard for your grade.
22.02.2020 Our in-class test will take place on Tuesday, March 10th, at Ivy Gate G.01 and Ivy Gate 1.01. Your timetables were updated and show which room you should go to. All material from the lectures and exercise classes up to and including lecture 9 and exercise sheet 4 will be relevant (peak finding is excluded though). To give you an idea of what this test could look like, here is an example in-class with potential solutions:

example in-class test and potential solutions
28.01.2020 There was a slight confusion regarding the assignment of students to exercise classes. Please come to the exercise class that appears in your timetable and forget about the assignment based on your sir name.
27.01.2020 Welcome to COMS10007! Please register to use the unit discussion board at Piazza using your University of Bristol email address: https://piazza.com/bristol.ac.uk/spring2020/coms10007

Teaching Staff:

Unit Director: Christian Konrad
TAs: Lidiya Binti Khalil, Emil Centiu, Igor Dolecki, Daniel Jones, Joseph MacManus, Mutalib Mohammed, Yuhang Ming, Kar Hor Yap

Teaching Units:

Lectures (20x): Mondays 2-3pm, Wednesdays 10-11am, Room QUEENS BLDG 1.40 PUGSLEY, Instructor: Dr. Christian Konrad
Exercise classes (8x): Tuesdays 1-2pm and 2-3pm (please come to the exercise class that you have been assigned to in your timetable), Room MVB 1.11
Drop-in Sessions (optional): Thursdays 10-11am in MVB 4.01

Assessment:

Exam: Counts 90% towards your final grade
One in-class test on March 10th, 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): Wednesdays, 1pm-2pm

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/spring2020/coms10007
Come to my office hours

Schedule

Week	Day	Date	Topics	Slides
13	Mon	27-Jan	Lecture 1: Introduction, Peak Finding	PDF
	Wed	29-Jan	Lecture 2: O-notation	PDF
14	Mon	03-Feb	Lecture 3: Theta, Omega, RAM Model	PDF
	Tue	04-Feb	Exercise Class 1	Worksheet 1
				Solution
	Wed	05-Feb	Lecture 4: Linear Search, Binary Search, Proofs by Induction	PDF
15	Mon	10-Feb	Lecture 5: Loop Invariants and Insertion-sort	PDF
	Tue	11-Feb	Exercise Class 2	Worksheet 2
				Solution
	Wed	12-Feb	Lecture 6: Mergesort and Maximum Subarray Problem	PDF
16	Mon	17-Feb	Lecture 7: Mergesort and Maximum Subarray Problem (slides of lectures 6,7 are combined)
	Tue	18-Feb	Exercise Class 3	Worksheet 3
				Solution
	Wed	19-Feb	Lecture 8: Trees and Heapsort	PDF
17	Mon	24-Feb	Lecture 9: Heapsort (slides of lectures 8 and 9 are combined)
	Tue	25-Feb	Exercise Class 4	Worksheet 4
				Solution
	Wed	26-Feb	Lecture 10: Quicksort	PDF
18			Reading Week
19	Mon	09-Mar	Lecture 11: Runtime of Quicksort (Lecturer: Raphael Clifford)	PDF
	Tue	10-Mar	In-class Test	In-class Test
				Solution
	Wed	11-Mar	Lecture 12: Sorting Lower Bound, Countingsort, Radixsort (Lecturer: Raphael Clifford)	PDF
20	Mon	16-Mar	Lecture 13: Recurrences I (Lecturer: John Lapinskas)	PDF
	Tue	17-Mar	~~Exercise Class 5 (canceled)~~
	Wed	18-Mar	Lecture 14: Recurrences II (Lecturer: John Lapinskas) video lecture - see files on blackboard for recording	PDF
			Easter Break
22	Mon	20-Apr	Lecture 15: Fibonacci Numbers - video lecture - see blackboard for recording	PDF
	Tue	21-Apr	Exercise Class 5	Worksheet 5
				Solution
	Wed	22-Apr	Lecture 16: Pole Cutting (Dynamic Programming) - video lecture - see blackboard for recording	PDF
23	Mon	27-Apr	Lecture 17: Matrix Chain Parenthesization (Dynamic Programming)- video lecture - see blackboard for recording	PDF
	Tue	28-Apr	Exercise Class 6	Worksheet 6
				Solution
	Wed	29-Apr	Lecture 18: Elements of Dynamic Programming, Maximum Subarray Problem - video lecture - see blackboard for recording	PDF
24	Mon	04-May	Lecture 19: Peak Finding in 2D - video lecture - see blackboard for recording	PDF
	Tue	05-May	Exercise Class 7	Worksheet 7
				Solution
	Wed	06-May	Lecture 20: Summary and Outlook - video lecture - see blackboard for recording	PDF
25	Mon	11-May	~~Lecture 21~~
	Wed	13-May	~~Lecture 22~~