CS 473 Algorithms I Spring 2024
Instructors: Ugur Dogrusoz and Ozgur S. Oguz
Classroom, Hours: Schedule
TAs: Emre Erdal, Gun Kaynar, Kutay Demiray, Salih Deniz Uzel and Serkan Demirci

Announcements

  • Unless otherwise stated, spare hours are as follows: Sections 1: Mon 11:30, 2: Tue 16:30, 3: Mon 8:30.
  • Check here at least once a week!
Description Asymptotic notation. Divide and conquer approach. Solving recurrences: substitution method, master method. Bounding summations. Analysis of randomized quicksort. Medians and order statistics. Heaps: heapsort, priority queues. Sorting in linear time. Dynamic programming. Greedy algorithms. Amortized analysis: aggregate, accounting and potential methods, dynamic tables. Elementary graph algorithms: breadth-/depth-first search, topological sort, strongly connected components. Credit units: 3 ECTS Credit units: 6, Prerequisite: CS 202.
Textbook T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms", MIT Press and McGraw-Hill, 2009. Third Edition
Outline &
Slides
Concepts / Slides Textbook
Introduction to Analysis of Algorithms Chapters 1 & 2
Asymptotic Notation Chapter 3
Solving Recurrences Chapter 4
The Divide-and-Conquer Design Paradigm Chapter 2 & 4
Quicksort Chapter 7
Randomized QuickSort Chapter 7
Randomized QuickSort Cntd Chapter 7
Median and Order Statistics Chapter 9
Heapsort Chapter 6
Sorting in Linear Time Chapter 8
Dynamic Programming Chapter 15
Greedy Algorithms Chapter 16
DP & Greedy Examples Chapter 15 & 16
Amortized Analysis Chapter 17
      Note: Some slides have been modified by UD
Grading
Component Weight Date/Due
Mid-Week Exams (MWE) 40 as announced (see SRS)
Attendance 06 each lecture hour
Midterm 24 March 21, 17:40, EE03,04,05,214,412
Final 30 June ??, ??, EB-??
Fz criteria: In order to be able to take the final exam, a student must collect at least 20pts out of 70pts before the final.
Remarks
  • Copying or communicating during an exam is considered as cheating. Students caught cheating in an exam will be subject to disciplinary action, as explained in the Student Disciplinary Rules and Regulation.
  • The instructor has the right to make changes to any future lecturing or assesment instruments during the semester, especially due to pandemic circumstances.
  • There will be 3 or 4 MWEs. Roughly once every 3-4 weeks we will have a MWE session with questions about the topics covered in the recent weeks. MWEs are open-book; you can bring your clean CLRS textbook. However, the book should be in one piece. No notes, slides, etc. are allowed.
  • All students are strongly encouraged to attend all MWE sessions. During lectures, we will take attendance (40 minutes or longer per lecture). For students missing multiple MWEs due to health problems (all of which are reported officially) there will be makeups at the end of semester.