Algorithms are procedures or methods that solve problems arising across the full range of computing applications. Algorithmic problems from those areas, however, are rarely mathematically well-formed and they often come with application-specific details, most of which are extraneous.
The goal of this course is to understand how to formulate problems, and from this, how to design efficient algorithms for the resulting problems.
The course starts with an introduction to algorithms. Then we study four essential algorithm design techniques: recursions, backtracking, dynamic programming, greedy algorithms, and network flow.
We will also spend a few weeks on computational intractability and approximation algorithm, a technique for dealing with computational intractable problems.
Name: Heekap Ahn
Homepage: https://tcs.postech.ac.kr/~heekap/
Midterm exam: 30%
Final exam: 30%
Homework: 20%
Problem solving(Assignment): 20%
Algorithms / Jeff Erickson / PDF version available (free) online at http://algorithms.wtf / ISBN 9781792644832
Algorithms / Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani / McGRAW-HILL / ISBN 9780071259750
Algorithm Design by Jon Kleinberg and Éva Tardos, 2006, Addison Wesley.
Week 1: Introduction / Computational efficiency
Week 2: Recursion
Week 3-4: Backtracking
Week 5-6: Dynamic programming
Week 7: Greedy algorithms
Week 8: Midterm exam.
Week 9-10: Graph algorithms
Week 11: Maximum flows and Minimum cuts
Week 12-13: Computational intractability
Week 14: Local search heuristics
Week 15: Approximation algorithms / Randomized algorithms
Week 16: Final exam.