

Contents


Week 1: 
Background Information: Discrete mathematics; Data structures. Introduction to Algorithms: What is an algorithm; Various problems. Analysis of Algorithms: Complexity of algorithms; Asymptotic notations. 
Week 2: 
Recursive Functions and Their Solutions: Substitution method; Characteristic equation method, Master’s theorem. 
Week 3: 
Brute Force Method: Sorting Algorithms; Searching algorithms; String matching problem; Closest pair problem; ConvexHull problem; Exhaustive search. 
Week 4: 
DivideandConquer: Sorting Algorithms; Searching algorithms; Closest pair problem; ConvexHull problem. 
Week 5: 
DecreaseandConquer: Sorting algorithms; Graph algorithms, DepthFirst Search, BreadthFirst Search, and topological sorting; Algorithms for generating combinatorial objects; Fake coin problem; Selection problem. 
Week 6: 
TransformandConquer: Presorting; Gaussian elimination; Balanced searched trees; Heaps and heapsort; Horner’s rule and binary exponentiation; Problem reduction. 
Week 7: 
Midterm exam I 
Week 8: 
Dynamic Programming: Knapsack problem; All pairs shortest paths; Optimal binary search tree; String editing; Matrix chain product. 
Week 9: 
Dynamic Programming: Fundamentals of dynamic programming, dynamic programming for knapsack problem etc. 
Week 10: 
Dynamic programming: More examples on dynamic programming. 
Week 11: 
Greedy Technique: Knapsack Problem; Minimum spanning tree; Single source shortest paths; Job sequencing with deadlines; Activity selection problem. 
Week 12: 
Greedy Technique: More examples using greedy techniques. 
Week 13: 
Iterative Improvement; The simplex method; Maximum flow problem; Maximum matching in bipartite graphs. 
Week 14: 
Complexity Classes: Basic definitions; P, NP ve NPComplete classes; NPComplete problems. 
Week 15*: 
Complexity Classes: Basic definitions; P, NP ve NPComplete classes; NPComplete problems. 
Week 16*: 
Final exam 
Textbooks and materials: 
Anany Levitin, "Introduction to The Design and Analysis of Algorithms", Addison Wesley Jon Kleinberg, Eva Tardos, "Algorithm Design", Pearson.

Recommended readings: 
Cormen, Leiserton, Rivest, Introduction to Algorithms, MIT Press, 2001. Horowitz, Sahni, Rajasekaran, Computer Algorithms, Computer Science Press, 1998. Sahni, Data Structures, Algorithms, and Applications in C++, McGrawHill, 1998. Weiss, Data Structures and algorithm and Algorithm Analysis in C, Addison Wesley, 1997. 

* Between 15th and 16th weeks is there a free week for students to prepare for final exam.

