COMS10017 (Object-Oriented Programming and) Algorithms I - 2021/2022 (TB2)

(maximize page     embedded in blackboard)


NEW: Click here to download a note on loop invariants

Teaching Staff

  • Lecturer: Christian Konrad
  • Lead TA: Kheeran Naidu
  • TAs: Robert Gabriel Popescu, Cezar Mihail Alexandru, Charlotte Dillon, George Edward Nechitoaia, Llewellyn Forward, Matt Staveley-Taylor, Michael Polvekrov, Ralph Roberts, Satya Rammolian, Sergiu Aracatitei, Zak Duggan, Alex Carpenter

Teaching Sessions

  • Lectures: online videos
  • Recap/Q & A/discussion sessions: Thursdays 2pm-3pm (clock here to join)
  • Small group problem classes: (your timetable shows which session you have been assigned to!) The problem class in week X will discuss the problem sheet published in week X-1
    1. Monday 9-11am, 1.58QB
    2. Monday 9-11am, 1.59QB
    3. Monday 9-11am, 1.60QB
    4. Tuesday 11-1pm - 1.11MVB
    5. Tuesday 11-1pm - 1.11A MVB
    6. Tuesday 11-1pm - 1.60QB
    7. Tuesday 3-5pm - 1.11MVB
    8. Tuesday 3-5pm - 1.11MVB
    9. Tuesday 11-1pm - Online class (click here to join)
  • OPTIONAL: online office hours: Fridays 1pm-2pm (click here to join)

How The Unit Works - A Typical Teaching Week


Week X
MondayTuesdayWednesdayThursdayFriday
  • Watch and study lecture videos released in week X
  • Work on exercise sheet released in week X
Problem sheet sessions
  • TA-led session discussing sheet released in week X-1
  • Please come prepared with your solutions to the problem sheet
  • Please attend only the session that you've been assigned to - check your calendar for that
  • If you can't attend the in-person session then attend the online session instead (group 9)
2pm-3pm: In-person Recap/Q & A/discussion session (streamed online at same time)
  • Discussion of material presented in video lectures in the current week X
  • Q & A session (bring your questions along!)
  • Discussion of additional exercises etc.
1pm-2pm: OPTIONAL: Online Office Hours
  • Ask me anything related to the unit
  • This session is optional!

Assessment


May/June multiple choice online exam - counts 50% towards your final grade in the joint module COMS10017 Object-Oriented Programming and Algorithms I

Click here to download the exam of 2019 (and here for a solution to question 2.d.). Note, however, that the exam this year will be very different due to it being an online exam. The questions of the 2019 exam are therefore not representative.

Piazza Discussion Board


piazza.com

We will use Piazza as our discussion board (click here to sign up). Feel free to ask any questions - questions can also be asked anonymously. We wish to see active participation.

Course Material


All lectures will be taught using slides. Videos and slides will be made available online (below on this webpage). 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 .

Schedule



Week Learning SessionSlidesRecording
W13: 24 - 28 Jan

Problem Sheet 1
PDF solution
Video 1: Welcome and IntroductionPDFvideo
Video 2: Peak FindingPDF video
Video 3: Why Constants Matter LessPDF video
Video 4: Big-O NotationPDF video
W14: 31 Jan - 04 Feb

Problem Sheet 2
PDF solution
Video 5: Theta and Big-OmegaPDF video
Video 6: RAM Model and Runtime AnalysisPDF video
Video 7: Linear and Binary SearchPDF video
Video 8: Proofs by Induction (Recap)PDF video
W15: 07 - 11 Feb

Problem Sheet 3
PDF solution
Video 9: Loop Invariants and Insertion-sortPDF video
Video 10: Merge-sortPDF video
W16: 14 - 18 Feb

Problem Sheet 4
PDF solution
Video 11: Maximum Subarray ProblemPDF video
Video 12: TreesPDF video
W17: 21 - 25 Feb

Problem Sheet 5
PDF solution
Video 13: Heap-sortPDF video
Video 14: QuicksortPDF video
W18: 28 Feb - 04 Mar
READING WEEK
W19: 07 - 11 Mar

Problem Sheet 6
PDF solution
Video 15: Runtime of QuicksortPDF video
Video 16: Lower Bound for SortingPDF video
W20: 14 - 18 Mar

Problem Sheet 7
PDF solution
Video 17: Countingsort and RadixsortPDF video
Video 18: Recurrences IPDF video
W21: 21 - 25 Apr

Problem Sheet 8
PDF solution
Video 19: Recurrences IIPDF video
Video 20: Fibonacci NumbersPDF video
W22: 28 Mar - 01 Apr

Problem Sheet 9
PDF solution
Video 21: Dynamic Programming - Pole Cutting PDF video
Video 22: Dynamic Programming - Matrix Chain Parenthesization (part 1)PDF video (part 1)
EV1: 04 - 08 Apr
Easter Week 1
EV2: 11 - 15 Apr
Easter Week 2
EV3: 18 - 22 Apr
Easter Week 3
W23: 25 - 29 AprVideo 23: Dynamic Programming - Matrix Chain Parenthesization (part 2) PDF video (part 2)
Video 24: Elements of Dynamic ProgrammingPDF video
W24: 02 - 06 MayRevision Week, no new material