**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!

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

- 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

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

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

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

- 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

Week | Day | Date | Topics | Slides |
---|---|---|---|---|

13 | Mon | 28-Jan | Lecture 1: Introduction, peak finding | |

Tue | 29-Jan | Lecture 2: O-notation | ||

Remarks: Throughout this course, log(n) denotes the binary logarithm, i.e., log(n) = log _{2}(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 | |

Tue | 05-Feb | Lecture 4: Linear and binary search, proofs by induction | ||

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_{0} 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 | |

Tue | 12-Feb | Lecture 6: Sorting problem, first part of merge sort algorithm | ||

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

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

18 | Reading Week | |||

19 | Mon | 11-Mar | Lecture 11: Runtime of Quicksort | |

Tue | 12-Mar | Lecture 12: Sorting LB, Countingsort, Radixsort | ||

Tue | 12-Mar | In-class Test | In-class Test | |

Solution | ||||

20 | Mon | 18-Mar | Lecture 13: Recurrences (substitution method, recursion-tree method) | |

Tue | 19-Mar | Lecture 14: Recurrences continued (slides of lectures 13 and 14 are combined) | ||

21 | Mon | 25-Mar | Lecture 15: Fibonacci Numbers | |

Tue | 26-Mar | Lecture 16: Dynamic Programming - Pole Cutting | ||

Tue | 26-Mar | Exercise class 3 | Worksheet 3 | |

Solution | ||||

22 | Mon | 01-Apr | Lecture 17: Dynamic Programming - Matrix Chain Parenthesization | |

Tue | 02-Apr | Lecture 18: Elements of Dynamic Programming 1 | ||

Easter Break | ||||

23 | Mon | 29-Apr | ||

Tue | 30-Apr | |||

Tue | 30-Apr | Exercise class 4 | ||

24 | Mon | 06-May | Bank Holiday Monday - no lecture | |

Tue | 07-May |