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

(maximize page     embedded in blackboard)

Welcome to the Unit webpage of the Algorithms 1 unit!

Teaching Staff

  • Lecturer: Christian Konrad
  • Lead TA: Kheeran Naidu
  • TAs: Imran Zamin Ali, Cezar Alexandru, Elliot Buckingham, Jeremy Colfer, Adithiya Diddapur, Charlotte Dillon, Amos Holland, Ollie Mamuda, Philip Mortimer, Michael Poluektov, Nathalie Alexandra Tcherdakoff, Viet-anh Tran, April Tune

Teaching Sessions

  • Lectures: Mondays 10am (PHYS BLDG G42 POWELL), Thursdays 3pm (QUEENS BLDG 1.40 PUGSLEY)
  • Small group problem classes: Tuesdays
    • Group 1: Tuesday 11-1pm - QUEENS BLDG 1.58
    • Group 2: Tuesday 11-1pm - QUEENS BLDG 1.59 DES
    • Group 3: Tuesday 11-1pm - QUEENS BLDG 1.60 DES
    • Group 4: Tuesday 2-4pm - QUEENS BLDG 1.59 DES
    • Group 5: Tuesday 2-4pm - QUEENS BLDG 1.60 DES
    • Group 6: Tuesday 4-6pm - QUEENS BLDG 1.59 DES
    • Group 7: Tuesday 4-6pm - QUEENS BLDG 1.60 DES
    • Group 8: Tuesday 4-6pm - QUEENS BLDG 1.7

    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: Thursdays 1-2pm - MVB03.44 (staffed by our excellent TAs)
  • OPTIONAL: Office hour: Friday 1-2pm - 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

The following Mock exam illustrates the format of the exam: mock exam, answer sheet, Instructions sheet

The exam is a closed book exam (no cheat sheet allowed) and you will have two hours to complete the exam.

Previous exam papers:

Schedule



Week TopicSlides
W13: 23 - 27 Jan

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

Problem Sheet 2
PDF 		Theta and Omega NotationPDF
Ram Model and Runtime AnalysisPDF
W15: 06 - 10 Feb

Problem Sheet 3
PDF 		Linear and Binary SearchPDF
Recap on InductionPDF
Loop Invariants and Insertion-sortPDF
W16: 13 - 17 Feb

Problem Sheet 4
PDF 		MergesortPDF
Maximum Subarray ProblemPDF
W17: 20 - 24 Feb

Problem Sheet 5
PDF 		TreesPDF
HeapsortPDF
Quicksort - part 1PDF
W18: 27 Feb - 03 Mar
READING WEEK
W19: 06 - 10 Mar

Problem Sheet 6
PDF 		Quicksort - part 2PDF
Lower Bound for SortingPDF
W20: 13 - 17 Mar

Problem Sheet 7
PDF 		Countingsort and RadixsortPDF
Recurrences 1PDF
W21: 20 - 24 Mar

Problem Sheet 8
PDF 		Recurrences 2PDF
Fibonacci NumbersPDF
EV1: 27 - 31 Mar
Easter Week 1
EV2: 03 - 07 Apr
Easter Week 2
EV3: 10 - 14 Apr
Easter Week 3
W22: 17 Apr - 22 Apr

Problem Sheet 9
PDF 		Dynamic Programming - Pole CuttingPDF
W23: 24 - 28 AprMatrix Chain MultiplicationPDF
 
W24: 01 - 05 MayRevision Week, no new material