Course info

Short Intro

The objective of this course is to provide a complete introduction to algorithm design and complexity analysis techniques.

Basic concepts recap: tractability, asymptotic order, graphs.
Major algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, network flow.
Computational intractability: \mathcal{NP}, NP-Complete, PSPACE.
Dealing with intractable problems: identification of structured special cases, approximation algorithms, local search heuristics.
Randomized algorithms.

Required：

Recommended：

Knowledge in computer science fundamentals: data structure, operating system, computer architecture, etc.
As much knowledge of mathematics as possible.
Insights in your own specific area of study.

Short survey: background statistics.

Read the textbook on your own, then present the topic during our meetings.

By the end of this course: read through the whole textbook.

Topics beyond the textbook are also welcomed.

It’s a proved best way of learning,
- if you are motivated and disciplined.
- Difficult problems can be discussed during the seminar.
It’s required by the Graduate Training Program.
- You have to demonstrate the skill of independent study.

Attendance & participation: 20%
Understanding of the topic: 40%
- Presenting skill: 20%
  - Questions to the audience.
  - Questions to the presenter.
- Assignments: 20%
Final project: 40%
- Write an two-page essay of any topic related to your research.
Honorable bonus (mutual exclusive options, only admissive if you got at least 90% already): 10%
- Creative solution including analysis to your own research topic.

A short essay about your own research topic.