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

Announcements

  • [HW6] announced on 12/22/2012, due 1/7/2013(Monday) 11:59.
  • [HW5] are modify a little bit for removing typo and ambiguous descriptions. Also, problem 4-3 is removed(Yeah~!).
  • [HW5] announced on 12/06/2012, due 12/20/2012 14:20.
  • The scores of HW and midterm are now private, and are posted on ceiba website. Please check your ceiba if the scores are correct.
  • HW4 announced on 11/22/2012, due 12/06/2012 14:20
  • this is the scores of HW1 and HW2: score. If you have any question, please email ada@csie.ntu.edu.tw. The score is now private, and is posted on your ceiba.
  • The slides for the Software Company Game have been posted.
  • HW3 announced on 10/19/2012, due 11/01/2012 14:20
  • The second graph course will be held on 10/16, 18:30-21:30 at R101.
  • The first graph course will be held on 10/9, 18:30-21:30 at R101.
  • HW2 announced on 10/4/2012, due 10/18/2012 14:20
  • hw1 due date is postponed to 5pm, Tuesday, October 9, 2012.
  • HW1Hint is available now.
  • In the report of programming assignment, you should : 1.Explain how your program works in detail. 2.Derive the time complexity of your program and briefly explain why. No need for formal proof.
  • HW1 announced on 9/20/2012, due 10/4/2012 14:20
  • You can check this step-by-step tutorial for SVN and program submitting : [SVN-help]

Teaching Team

Name Office hour Room
Instructor Michael Tsai Fridays 16:20-17:20 R316
Teaching Assistant 陳立翔 Tuesdays 15:30-16:30 博理館R314
Teaching Assistant 簡伯宇 Tuesdays 13:00-14:00 R217
Teaching Assistant 許祐程 Mondays 10:20-11:10 R217
Teaching Assistant 陳庭緯 Tuesdays 13:00-14:00 R217
Teaching Assistant 張偉凱 Wednesday13:00-14:00 R217
Teaching Assistant 歐志先 Wednesday13:00-14:00 R217

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/13 First class
9/20 HW1 out
9/27
  • Divide and Conquer 3 [pptx|pdf] (Last updated: 10/04/2012)
10/4 HW1 due, HW2 out
  • Closest Pair of Points Handout [pdf]
  • Dynamic Programming 1 [pptx|pdf]
10/11
10/18 HW2 due, HW3 out
10/25
  • Paper Prototyping [pptx|pdf]
  • The Software Company Game [pptx|pdf]
  • Presentation Template for the Software Company Game [pptx]
11/1 HW3 due
  • Painless Functional Specification [pptx|pdf]
  • Amortized Analysis [pptx|pdf] (Last updated: 2012/11/22)
11/8 Midterm Examination
11/15 No class on 11/15(校慶).
11/22 HW4 out
  • Evidence-based Scheduling [pptx|pdf]
11/29
12/6 HW5 out. Software Company Game Presentation
12/13
12/20 HW5 due, HW6 out
12/27
  • Multithreaded Algorithms 1 [pptx|pdf]
1/3 HW6 due
  • Multithreaded Algorithms 2 [pptx|pdf]
  • Multithreaded Algorithms 3 [pptx|pdf]
1/10 Final Examination

TA Recitation

Topic Lecture Notes
Graph 1 [pptx|pdf]
Graph 2 [pptx|pdf]
Graph 3 [pptx|pdf]

Homework

Homework Due Problems Solution
HW1 10/9 17:00
  • HW1 [pdf] (Last Updated: 09/22/2012)
  • HW1 Hint [pdf]
  • HW1 Solution[pdf]
HW2 10/18 14:20
  • HW2 Solution[pdf]
HW3 11/01 14:20
  • HW3 Solution[pdf]
HW4 12/06 14:20
  • HW4 Solution[pdf]
HW5 12/20 14:20
  • HW4 Solution[pdf]
HW6 1/7 11:59
 
ada_12fall.1357539598.txt.gz · Last modified: 2013/01/07 14:19 by hsinmu · [Old revisions]
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki