This is an old revision of the document!

[CSIE 2136] Algorithm Design and Analysis

This is a required course for the undergraduate students in the Department of Computer Science and Information Engineering. In this course, I will cover various algorithm design and analysis techniques.

Course Information

Instructor: Hsin-Mu (Michael) Tsai
Class time: Thursdays 678 (14:20-17:20)
Classroom: CSIE Building 102
Textbook: “Introduction to Algorithms,” Third Edition, Cormen, Leiserson, Rivest and Stein, the MIT Press

Announcements

Group list for the Software Company Game announced.
Midterm Solution for the Midterm.

Teaching Team

	Name	Office hour	Room
Instructor	蔡欣穆 (Michael)	10:00-11:00, Mondays	R316
Teaching Assistant	李廣和	16:30-17:20, Tuesdays	地下室圓柱台
Teaching Assistant	朱鴻敏	16:30-17:20, Tuesdays	地下室圓柱台
Teaching Assistant	張庭維	13:00~14:00, Wednesdays	R217
Teaching Assistant	周儒成	13:00~14:00, Wednesdays	R217
Teaching Assistant	張雅涵	13:00~14:00, Wednesdays	R217
Teaching Assistant	蔡政澔	13:00-14:00, Fridays	R528

Please direct all your questions to ada@csie.ntu.edu.tw and the e-mails will be forwarded to all members of the teaching team.

Tentative Syllabus

Algorithm Design and Analysis
- Divide-and-Conquer
- Probabilistic Analysis & Randomized Algorithms (not sure)
- Dynamic Programming
- Greedy Algorithms
- Amortized Analysis
- NP-Completeness
- Multi-threaded Algorithms (not sure)
- Advanced Graph Algorithms (not sure)
Programming and Software Engineering in the Real World
- Version control
- Bug tracking
- Manage your development schedule
- The software company game
- Functional specifications
- Paper prototyping

Class Schedule & Lecture Notes

Date	Events	Lecture Notes
9/12	First class	Course Information [pptx\|pdf] Divide and Conquer 1 [pptx\|pdf]
9/19	HW1 out. No class on 9/19(中秋節).
9/26		Divide and Conquer 2 [pptx\|pdf] Divide and Conquer 3 [pptx\|pdf]
10/3	HW1 due, HW2 out	Dynamic Programming 1 [pptx]\|pdf]
10/10	Online broadcast	Dynamic Programming 2 [pptx]\|pdf]
10/11	Online broadcast	Dynamic Programming 3 [pptx]\|pdf]
10/17	HW2 due, HW3 out	Greedy Algorithms [pptx\|pdf] Painless Bug Tracking [pptx\|pdf]
10/24		Greedy Algorithms
10/31	HW3 due	Advanced Graph Algorithms [pptx\|pdf] All-pairs shortest path [pptx\|pdf] NP Completeness [pptx\|pdf] [pptx\|pdf]
11/7	Midterm Examination
11/14	HW4 out	Amortized Analysis [pptx\|pdf] Paper Prototype [pptx\|pdf] Software Company [pptx\|pdf]
11/21		NP Completeness 1 (Michael's slides) [pptx\|pdf]
11/28	HW4 due, HW5 out	NP Completeness 2 [pptx\|pdf]
12/5		Software Company Game
12/12	HW5 due, HW6 out	No class
12/19		No class
12/26	HW6 due	NP Completeness
12/31	Make-up class	Multithreaded Algorithms 1 [pptx\|pdf]
1/2		Multithreaded Algorithms 2 [pptx\|pdf] Multithreaded Algorithms 3 [pptx\|pdf]
1/9	Final Examination

Homework

Homework	Due	Problems(Last Modified)	Solution
HW1	2013/10/04 17:00	HW1 2013/09/21	Solution Problem1
HW2	2013/10/17 14:20	HW2 2013/10/03	Solution Problem1
HW3	2013/10/31 14:20	HW3 2013/10/23	Solution
HW4	2013/11/28 14:20	HW4 2013/11/15	Solution
HW5	2013/12/23 14:20	HW5 2013/12/09	Solution

Submit your answers via the SVN server (electronic copy) or to the TA at the beginning of class on the due date (hard copy).
For submitting your programming assignments:JudgeGirl
step-by-step tutorial for SVN and program submitting: SVN-help