IIIS, Tsinghua University

Algorithms 2017 Fall

Instructor: Jian Li ( lapordge@gmail.com )

TA: Shichuan Deng (dsc3189959@163.com), Jiezhong Qiu (xptree@gmail.com)

Time: Every Monday Morning (9:50-12:15)

Classroom: Xuetang 117

Overivew:

This is a first course in design and analysis of algorithms

for undergraduate students. The main focus is about

some fundamental algorithmic techniques, such as greedy,

divide and conquer, dynamic programming and so on,

some fundamental combinatorial objects, such as graphs,

network flows, strings and so on,

and various mathematical tools to analyze them.

In the later part of the course, I will touch some

more advanced topics such as approximation algorithms

for NP-hard problems, randomized algorithms and so on.

The course forms a foundation for all areas of computer science.

We will discuss algorithmic problems from a variety of areas

such as AI, computational biology, networking and so on.

I will teach basic algorithmic concepts and techniques

in class, followed by some simple applications.

More advanced applications will be delivered in the

homeworks which form an important part of the course

and contribute to 30% of the final grade. We will also

have both the mid-term exam and the final exam, contributing

30% and 40% to the final grade, respectively.

Textbook£ºAlgorithm Design, by Jon Kleinberg and Eva Tardos. (You should be able to find it in Taobao also.)

We will use some homework problems from this book.

Other
Refs£º

[1] Introduction to Algorithms, 3rd edition (CLRS)

By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

[2] Approximation Algorithms

By Vijay V. Vazirani

[3] Randomized Algorithms

Rajeev Motwani, Prabhakar Raghavan

¡¡

Schedule

9.18 | Stable Matching Problem, Coupon
Collector Problem, Basic concepts about
graphs, Strongly connected components, DAG and
Topological ordering£¬Greedy Algorithm for Interval Scheduling average case analysis: http://sarielhp.org/teach/2002/a/notes/06_collector.pdf (the notes also contains a high probability bound for coupon collector.) |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡ | ¡¡ |

¡¡

Link: