Course Objectives: To make students understand the importance of algorithms in the field of computers and master basic ideas and methods of the design and analysis of algorithms, so that they are able to better understand and write computer programs and enhance the ability of solving problems.

Course Requirements: The course study should be organized in the way of lecturing as well as discussion by groups. And students need to attend class and finish homework on time.

Course Contents:

1. Prologue: introduce the performance and the asymptotic analysis of algorithms.

2. Algorithms with numbers: introduce the basic arithmetic algorithms and modular arithmetic and hashing.

3. Divide-and-conquer algorithms: introduce the recurrence relations and the applications of divide-and-conquer algorithms in merge sort and medians.

4. Graph algorithms: introduce the basic search algorithms on graphs and the application of graph algorithms in shortest path problems.

5. Greedy algorithms: introduce the ideas of greedy algorithms and their applications in the problems of minimum spanning trees and set cover.

6. Dynamic programming: introduce the ideas of dynamic programming and its application in knapsack and shortest path problems.

7. Linear programming and reductions: introduce to linear program and its application in flows in networks and bipartite matching.

8. NP-complete problems: introduce the features of NP-complete problems and their solving methods.

Credits: 3