Semester: Summer 2011
Schedule: Monday, Tuesday, Thursday 13:40,
14:40
Classroom: EB 104
Instructor: Melih Onus
Office Hours: Monday, Tuesday, Thursday 15:40 - 17:30, EA 520
E-mail: onus@cs.bilkent.edu.tr
Website: http://www.cs.bilkent.edu.tr/~onus/ogr/yaz2011/cs473/index.html
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.
Text Book: T. H. Cormen, C. E. Leiserson,
R. L. Rivest, and C. Stein. Introduction to
Algorithms, MIT Press and McGraw-Hill, 3. Edition, 2009.
References:
·
Jon Kleinberg, Eva Tardos. Algorithm
Design, Addison Wesley, Pearson Education, 2006.
·
E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer
Science Press 1978.
Grading:
Midterm I (%25): June 17, 2011, 17:40 – 20:40 (Open book, closed notes), EB 101 – EB
102.
Midterm II (%25): July 1, 2011, 17:40 – 20:40 (Open book, closed notes), EB 101 – EB 102.
Midterm III (%25): July 15, 2011, 17:40 – 20:40 (Open book, closed notes), EB 101 – EB
102.
Final (%25): July 28, 2011, 09:00 – 12:00 (Open book, closed notes), EB 103 – EB 104.
Attendance (%5)
Outline:
WEEK 1: Introduction: analysing algorithms, designing
algorithms. Asymptotic notation. Solving
Recurrences. (Chapters 1, 2, 3, 4) (slides 1, slides 2, slides 3)
WEEK 2: Divide and conquer:
Strassen. Randomized quicksort:
analysis. (Chapters 2, 4, 7) (slides 4, slides 5, slides 6, slides 7)
WEEK 3: Medians and order
statistics. Heaps: heapsort, priority queues. Sorting
in linear time. (Chapter 9, 6, 8) (slides 8, slides 9, slides 10)
WEEK 4: Dynamic
programming: matrix-chain multiplication, longest common subsequence, 0/1
Knapsack problem, resource allocation problem. (Chapter 15) (slides 11)
WEEK 5: Greedy algorithms: activity selection problem, Hufmann codes, task scheduling problem. (Chapter 16) (slides 12, slides 13)
WEEK 6: Amortized analysis: aggregate, accounting and
potential methos, dynamic tables. (Chapter 17) (slides 14, slides 15)
WEEK 7: Graphs. Breadth-First Search. Depth-First Search.
Topological Sort. Strongly Connected Components (Chapter 22) (slides 16, slides 17, slides 18, slides 19, slides 20)
Attendance: You will
fail the class if the attendance is below a certain percentage (%80 - %75).
Resources: MIT, Introduction to Algorithms, complete set
of lecture notes and videos:
Academic Integrity
Copying or communicating during an
exam is considered cheating. Students caught cheating in an exam will be
subject to disciplinary action, as explained in the “Student Disciplinary Rules
and Regulation” (www.provost.bilkent.edu.tr/procedures/AcademicHonesty.htm).
Documents