======Algorithms, Fall 2024======
This course provides an introduction to the design and analysis of computer
algorithms, with a particular emphasis on the use of **principles of mathematical induction** in designing algorithms.
Its goal is to acquaint the students with basic computer
algorithms and their design principles and to cultivate the students' ability
in designing and analyzing algorithms independently.

=====Announcements=====
  * 2025/01/06: grade report revised.
  * 12/29: {{courses:alg2024:alg2024grade.pdf|grade report}} available; please send inquiries/requests, if any, to the instructor by 5PM 12/31 (Tue.).
  * 12/10: slides from TA sessions: {{courses:alg2024:alg2024hw8_s.pdf|HW#8}}, {{courses:alg2024:alg2024hw9_s.pdf|HW#9}} (revised 12/15).
  * 12/03: notes/slides for NP-Completeness available.
  * 12/03: notes/slides for Reduction available.
  * 12/02: {{courses:alg2024:hw10.pdf|HW#10}} due on 12/10 by 1:20PM (because of the TA session).
  * 11/26: slides from TA sessions: {{courses:alg2024:alg2024hw7_s.pdf|HW#7}}.
  * 11/26: {{courses:alg2024:hw9.pdf|HW#9}} due on 12/03.
  * 11/26: notes/slides for Dynamic Programming available.
  * 11/18: {{courses:alg2024:hw8.pdf|HW#8}} due on 11/26 by 1:20PM (because of the TA session).
  * 11/12: slides from TA sessions: {{courses:alg2024:alg2024hw6_s.pdf|HW#6}} (revised 11/20).
  * 11/11: notes/slides for Advanced Graph Algorithms available.
  * 11/05: {{courses:alg2024:hw7.pdf|HW#7}} due on 11/19.
  * 11/04: notes/slides for Basic Graph Algorithms available (revised 12/12).
  * 11/04: {{courses:alg2024:alg2024mid_s.pdf|Suggested Solutions to Midterm Problems}} available (revised 11/11).
  * 10/22: slides from TA sessions: {{courses:alg2024:alg2024hw3_s.pdf|HW#3}} (revised), {{courses:alg2024:alg2024hw4_s.pdf|HW#4}}.
  * 10/15: {{courses:alg2024:hw6.pdf|HW#6}} due on 11/05.
  * 10/13: notes/slides for String Processing available.
  * 10/08: slides from TA sessions: {{courses:alg2024:alg2024hw2_s.pdf|HW#2}}, HW#3 (removed).
  * 10/06: {{courses:alg2024:hw5.pdf|HW#5}} due on 10/15.
  * 10/03: notes/slides for Searching and Sorting available (revised 10/25).
  * 10/03: notes/slides for A Supplement to Data Structures available (revised 10/15).
  * 10/01: {{courses:alg2024:hw4.pdf|HW#4}} due on 10/08 by 1:20PM (because of the TA session).
  * 09/30: notes/slides for Design by Induction available (revised 10/02).
  * 09/24: slides from TA sessions: {{courses:alg2024:alg2024hw1_s.pdf|HW#1}}.
  * 09/24: {{courses:alg2024:hw3.pdf|HW#3}} due on 10/01.
  * 09/22: {{courses:alg:old_exams.zip|old exams}}.
  * 09/22: notes/slides for Analysis of Algorithms available (revised 10/15).
  * 09/10: {{courses:alg2024:hw2.pdf|HW#2}} due on 09/24 by 1:20PM (because of the TA session).
  * 09/09: classroom changed to Room 305, Management Building 2 for the entire semester.
  * 09/02: {{courses:alg2024:hw1.pdf|HW#1}} due on 09/10.
  * 09/02: notes/slides for Introduction and for Mathematical Induction available (revised 09/24).
  * 08/26: this wiki site created to complement the NTU COOL site for this course.

=====Instructor=====
[[http://im.ntu.edu.tw/~tsay/|Yih-Kuen Tsay (蔡益坤)]], NTU IM Dept.,
3366-1189, ''Xtsay@ntu.edu.twX'' (between the enclosing pair of X's).

=====Lectures=====
Tuesday 2:20~5:20PM, Room 305, Management Building 2. \\ TA
sessions will be scheduled prior to some of the class meetings between 1:20
and 2:10PM; see the course schedule below.

=====Office Hours=====
Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108,
Management Building 2.

=====TAs=====
Yu Hsiao (蕭瑀), Xb08705059@ntu.edu.twX (between the enclosing pair of X's).\\
Yu-Hsuan Wu (吳宇璇), Xb09705045@ntu.edu.twX (between the enclosing pair of X's)


=====Textbooks=====
  * [M] //[[http://www.amazon.com/Introduction-Algorithms-Creative-Udi-Manber/dp/0201120372/ref=sr_1_1?s=books&ie=UTF8&qid=1329702126&sr=1-1|Introduction to Algorithms - A Creative Approach]]//, U. Manber, Addison-Wesley, 1989. (Four copies of this book have been put on reserve at NTU Library in the 3F-Course Reserves area 教師指定參考書區 under 演算法(BM-4). Additionally, ten copies are available for loan; please contact one of the TAs.)
  * [C] //[[https://www.amazon.com/-/zh_TW/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X/ref=pd_vtp_h_pd_vtp_h_sccl_5/145-5889579-1108519?pd_rd_w=lVaBE&content-id=amzn1.sym.a5610dee-0db9-4ad9-a7a9-14285a430f83&pf_rd_p=a5610dee-0db9-4ad9-a7a9-14285a430f83&pf_rd_r=BNMB7X78PXC5PPY75C40&pd_rd_wg=XdiKJ&pd_rd_r=b403a0e6-d87d-478c-9665-e79ffba4607a&pd_rd_i=026204630X&psc=1|Introduction to Algorithms, Fourth Edition]]//, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2022. (開發圖書代理; one copy of this book has been put on reserve at NTU Library in the 3F-Course Reserves area 教師指定參考書區 under (FF-9).)

=====Syllabus/Schedule (with links to notes/slides)=====
We will try to cover most
of Manber's book plus supplementary material, including a few chapters of the
book by Cormen //et al.// (Note: a TA session will precede a class meeting
whose date is marked with an *. There are six TA sessions on 09/24, 10/08,
10/22, 11/12, 11/26, and 12/10.)
  *Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 09/03a) [{{courses:alg2024:ch1_notes.pdf|notes}}, {{courses:alg2024:ch1_slides.pdf|slides}}]
  *Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 09/03b, 09/10) [{{courses:alg2024:ch2_notes.pdf|notes}}, {{courses:alg2024:ch2_slides.pdf|slides}}]
  *Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 09/24*) [{{courses:alg2024:ch3_notes.pdf|notes}}, {{courses:alg2024:ch3_slides.pdf|slides}}]
  *Design by Induction [M: Ch. 5] (1 week: 10/01) [{{courses:alg2024:ch5_notes.pdf|notes}}, {{courses:alg2024:ch5_slides.pdf|slides}}]
  *Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,19] (.5 week: 10/08a*) [{{courses:alg2024:ch4_notes.pdf|notes}}, {{courses:alg2024:ch4_slides.pdf|slides}}, {{courses:alg2024:ch4_slides_avl.pptx|Building an AVL Tree (Illustration)}}]
  *Searching and Sorting [M: Ch. 6;  C: Ch. 6,7,8,9] (1.5 weeks: 10/08b, 10/15) [{{courses:alg2024:ch6_notes_a.pdf|notes}}, {{courses:alg2024:ch6_slides_a.pdf|slides}}, {{courses:alg2024:ch6_slides_heapsort.pptx|Heapsort (Illustration)}}, {{courses:alg2024:ch6_slides_heapbottomup.pptx|Bottom-Up Heap Building (Illustration)}}]
  *String Processing [M: Ch. 6;  C: Ch. 32] (1 week: 10/22*) [{{courses:alg2024:ch6_notes_b.pdf|notes}}, {{courses:alg2024:ch6_slides_b.pdf|slides}}, {{courses:alg2024:ch6_slides_huffman.pptx|Construction of a Huffman Tree (Illustration)}}]
  * **Midterm** (**2024/10/29**)
  *Graph Algorithms: Basic [M: Ch. 7;  C: Ch. 20,21,22,23] (1.5 weeks: 11/05, 11/12a*) [{{courses:alg2024:ch7_notes_a.pdf|notes}}, {{courses:alg2024:ch7_slides_a.pdf|slides}}, {{courses:alg2024:ch7_slides_dijkstras.pptx|Dijkstra's Algorithm (Illustration)}}, {{courses:alg2024:ch7_slides_mst.pptx|Prim's Algorithm (Illustration)}}]
  *Graph Algorithms: Advanced [M: Ch. 7;  C: Ch. 20,24,25] (1.5 weeks: 11/12b, 11/19) [{{courses:alg2024:ch7_notes_b.pdf|notes}}, {{courses:alg2024:ch7_slides_b.pdf|slides}}, {{courses:alg2024:ch7_slides_scc.pptx|Computing SCCs (Illustration)}}]
  *Dynamic Programming [C: Ch.14] (1 week: 11/26*) [{{courses:alg2024:dynamic_prog_notes.pdf|notes}}, {{courses:alg2024:dynamic_prog_slides.pdf|slides}}]
  *Reduction [M: Ch. 10; C: Ch. 29] (.5 week: 12/03a) [{{courses:alg2024:ch10_notes.pdf|notes}}, {{courses:alg2024:ch10_slides.pdf|slides}}]
  *NP-Completeness [M: Ch. 11; C: Ch. 34] (1.5 weeks: 12/03b, 12/10*) [{{courses:alg2024:ch11_notes.pdf|notes}}, {{courses:alg2024:ch11_slides.pdf|slides}}]
  * **Final** (**2024/12/17**)

=====Grading=====
Homework/Quizzes 20%, Participation 10%, Midterm 35%, Final 35%.

=====References=====
  * [[http://en.wikipedia.org/wiki/Mathematical_induction|Mathematical Induction]] (a Wikipedia page)
  * [[http://en.wikipedia.org/wiki/Structural_induction|Structural Induction]] (a Wikipedia page)
  * MIT OpenCourseWare: [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/|Introduction to Algorithms]]
  * Stanford Coursera: [[https://www.coursera.org/specializations/algorithms|Algorithms]]
  * [[http://dl.acm.org/citation.cfm?id=2093549&CFID=70582427&CFTOKEN=84470362|What is an Algorithm?]] (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
  * [[https://www.toptal.com/developers/sorting-algorithms|Sorting Algorithms Animations]]
  * [[http://www.cs.sunysb.edu/~skiena/combinatorica/animations/|Graph Animations with Combinatorica]]
  * [[http://www.claymath.org/sites/default/files/pvsnp.pdf|The P versus NP Problem]] (Stephen Cook)
  * The website of [[https://icpc.global|ICPC]] (International Collegiate Programming Contest)