CS 473 Algorithms I Spring 2012 Instructor: Ugur Dogrusoz Office, Hours: EA-429, Wed, Thu PM Classroom, Hours: EB-103, Mon, Thu PM Main Course Page: Web page

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.
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 05 - Classwork 45 every Thu, 17:40-19:30, EE 317 Midterm 25 March 22, 2012, 17:40, EE 317 Final 25 May 21, 2012, 15:30, EB 101