Design and analysis of algorithms; Turing machines; NP-complete theory; algorithmic techniques: divide-and-conquer, greedy, dynamic programming, graph traversal, backtracking, and branch-and-bound; applications include sorting and searching, graph algorithms, and optimization. Students are expected to know data structures and possess general programming skills in one or more procedural/OOP language such as C/C++/Java, and to have a good mathematical background such as discrete math and some calculus, prior to registration.
1. Design and synthesize algorithms for given problems using standard algorithm design techniques and their combinations
2. Analyze algorithms and programs (in pseudocode) to compute the time complexity
3. Apply basic concepts in mathematics to evaluate algorithms and software programs and prove their correctness