CS 473 Algorithms I Spring 2014
Instructor: Ugur Dogrusoz
Office, Hours: EA-522, Tue, Thu AM
Classroom, Hours: EB-101, Mon, Thu PM
TAs: R. Oguz Selvitopu

Announcements
  • Unless otherwise stated, we do not hold the following lecture hour: Mon 16:40-17: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
Huffman Codes Chapter 16
Amortized Analysis Chapter 17
Dynamic Tables Chapter 17
      Note: Some slides have been modified by UD
Grading
Component Weight Date/Due
Attendance 06 -
Classwork 54 every Wed, 17:40-19:40, EE 03
Midterm 20 April 2, 2014, 17:40, EE 03
Final 20 May 24, 2014, 18:30, B-Z08
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.
  • There will be 11 Classworks.
  • In Classworks, books are open but any other resources are forbidden (Books must be clean and unused. Books containing any written text are not allowed).
  • In Classworks, all phones and any other electronic devices must be turned off.
  • Each week we will have a classwork session and each classwork will contain questions about the topics covered in the respective week.
  • Lowest two of each student's CW grades will be omitted for overall grading.
  • All students are strongly encouraged to attend all CW sessions.
  • For students missing CWs due to health problems (all of which are reported officially) there will be makeups at the end of semester.
  • Papers without section IDs will get 15 points penalty.
  • Attendance grade will be computed as follows: If you miss less than or equal to 4 hours in the semester, you will get the full 6% grade. If you miss more than 4 hours, you will lose 0.20% for every extra hour you miss. For example, if you miss 5 hours in the semester, your attendance grade will be 5.80%. If you miss 34 hours or more, you will get 0% attendance grade.