CENG 310 - Algorithms
Semester: Spring 2012
Schedule: Section 1: Monday 09:40-10:40 Amfi 2, Tuesday 14:40 HA 05
Section 2: Wednesday 11:40-12:40 MB06, Thursday 13:40 L112
Instructor: Melih Onus
Office Hours: Tuesday 12:30 – 14:30, Thursday 10:30 - 12:30, L221
E-mail: melih@cankaya.edu.tr
Website: http://ceng310.cankaya.edu.tr
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.
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:
Homework (%15)
Quiz (%15)
Midterm (%30) (Open book, closed notes) 19 Nisan 2012, 17:40 NA01(MÜH 3 binası)
Final (%40) (Open book, closed notes)
Outline:
WEEK 1: Introduction: analysing algorithms, designing algorithms. (Chapters 1) slide1
WEEK 2: Asymptotic notation. Solving Recurrences. (Chapters 2, 3, 4) slide2 slide3
WEEK 3: Divide and conquer: Strassen. (Chapters 2, 4) slide4
WEEK 4: Randomized quicksort: analysis. (Chapter 7) slide5 slide6 slide7
WEEK 5: Medians and order statistics. (Chapter 9) slide8
WEEK 6: Heaps: heapsort, priority queues. (Chapter 6) slide9
WEEK 7: Sorting in linear time. (Chapter 8) slide10
WEEK 8: Dynamic programming: matrix-chain multiplication, longest common subsequence. (Chapter 15) slide11
WEEK 9: Dynamic programming: 0/1 Knapsack problem, resource allocation problem. (Chapter 15)
WEEK 10: Greedy algorithms: activity selection problem. Hufmann codes (Chapter 16) slide12
WEEK 11: Greedy algorithms: task scheduling problem. (Chapter 16)
WEEK 12: Amortized analysis: aggregate, accounting and potential methos, dynamic tables. (Chapter 17) slide13
WEEK 13: Graphs. Breadth-First Search. Depth-First Search (Chapter 22) slide14 slide15 slide16 slide17
WEEK 14: Topological Sort. Strongly Connected Components (Chapter 22) slide18
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: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
Documents