COMS10017 (Object-Oriented Programming and) Algorithms I - 2023/2024 (TB2)



Welcome to the Unit webpage of the Algorithms 1 unit!

Teaching Staff

  • Lecturer: Christian Konrad
  • Lead TA: Adithya Diddapur
  • TAs: Cezar Alexandru, Alexander Bell, Michael Degamo, Amos Holland, Piotr Kozicki, Philip Mortimer, Conor O'Sullivan, Thomas Parr, Robert Popescu, Jaehyun Roh, Thammadol Tansrivorarat, Archie Walton, Eric Wang

Teaching Sessions

  • Lectures: Mondays 3pm (PHYS BLDG 1.11), Thursdays 11am (PHYS BLDG 1.11)
  • Small group problem classes: Tuesdays
    • Group 1: Tuesday 9-11am - QUEENS BLDG 1.58
    • Group 2: Tuesday 9-11am - QUEENS BLDG 1.59 DES
    • Group 3: Tuesday 9-11am - QUEENS BLDG 1.06
    • Group 4: Tuesday 9-11am - QUEENS BLDG 1.68
    • Group 5: Tuesday 11-1pm - QUEENS BLDG 1.59 DES
    • Group 6: Tuesday 11-1pm - QUEENS BLDG 1.58
    • Group 7: Tuesday 3-5pm - QUEENS BLDG 1.59 DES
    • Group 8: Tuesday 3-5pm - QUEENS BLDG 1.60 DES
    • Group 9: Tuesday 3-5pm - QUEENS BLDG 1.06
    • Group 10: Tuesday 3-5pm - QUEENS BLDG 1.69

    Please only attend the problem class that you were assigned to (check your timetable for this)! The problem class in week X will discuss the problem sheet published in week X-1.
  • OPTIONAL: Drop-in session: Mondays 10-11am - 1.60QB starting in week 15 (staffed by our excellent TAs)
  • OPTIONAL: Office hour: Mondays 4-5pm - MVB03.06 (with Christian Konrad)

Course Material

All lectures will be taught using slides. 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 .

Discussion Board

We will use the Microsoft Teams group for this unit as our discussion board. We wish to see active participation!

Assessment

May/June in-person exam - counts 50% towards your final grade in the joint unit COMS10017 Object-Oriented Programming and Algorithms I

Exam preparation questions: Click here for a collection of relevant sample exam questions (and here for the solutions). To access the documents, you must be logged in on blackboard. Alternatively, you can access the files via the unit page on blackboard and the submenu item "Exam preparation questions".

Short mock exam illustration the exam format: Click here for a short sample Mock exam that illustrates the format of the exam. This sample exam is much shorter than the actual exam as its purpose is only to illustrate the exam format. You will have to answer the questions on separate answer sheets, click here for the answer sheets for the mock exam. Click here for instructions regarding how to complete the answer sheets.

Schedule



Week TopicSlides
W13: 22 - 26 Jan

Problem Sheet 1
PDF solution		Welcome and IntroductionPDF
Peak FindingPDF
Why Constants Matter LessPDF
Big-O NotationPDF
W14: 29 Jan - 02 Feb

Problem Sheet 2
PDF solution		Theta and Omega NotationPDF
RAM Model and Runtime AnalysisPDF
W15: 05 - 09 Feb

Problem Sheet 3
PDF solution		Linear and Binary SearchPDF
Recap: Proofs by InductionPDF
Loop Invariants and InsertionsortPDF
W16: 12 - 16 Feb

Problem Sheet 4
PDF solution		MergesortPDF
Maximum Subarray ProblemPDF
W17: 19 - 23 Feb

Problem Sheet 5
PDF solution		TreesPDF
HeapsortPDF
W18: 26 Feb - 01 Mar
READING WEEK
W19: 04 - 08 Mar

Problem Sheet 6
PDF solution		Quicksort - part 1PDF
Quicksort - part 2PDF
Lower Bound for SortingPDF
W20: 11 - 15 Mar

Problem Sheet 7
PDF solution		Countingsort and RadixsortPDF
Recurrences 1PDF
W21: 18 - 22 Mar

Problem Sheet 8
PDF solution		Recurrences 2PDF
Fibonacci NumbersPDF
EV1: 25 - 29 Mar
Easter Week 1
EV2: 01 - 05 Apr
Easter Week 2
EV3: 08 - 12 Apr
Easter Week 3
W22: 15 Apr - 19 Apr

Problem Sheet 9
PDF solution		The Pole Cutting ProblemPDF
The Matrix Chain Parenthesization ProblemPDF
W23: 22 - 26 AprElements of Dynamic ProgrammingPDF
W24: 29 - 03 MayRevision Week, no new material