Fall 2016 Tutorials Exam Info Course Policies Announcements

Topics (Order is tentative)		Notes	References*	Updates** Revision Date
Introduction	Introduction	pdf	1, 2.1, 2.2	6/9/16


Divide-and-Conquer	Merge sort	pdf	2.3, KT 5.3	7/9/16
	Inversion Counting Example	pdf		14/09/16
	The maximum subarray problem	pdf	4.1	12/9/16
	Integer and matrix multiplication¹	pdfL1 pdfL2	4.2, 4.4, 4.5, KT 5.5	15/09/2016b
	Randomized algorithms	pdf	5, Appendix C.1-C.4	19/09/2016


Quicksort and linear-time selection²	Lecture 1 Lecture 2 Slides with Revised Analysis	pdfL1 pdfL2 pdf	7, 9.2	22/09/2016b 22/09/2016 25/09/2016
	Quicksort Example	ppt
	Selection Example	ppt


Other Sorting	Heaps and heapsort	pdf	6
	Sorting in linear time	pdf	8


Greedy Algorithms	Greedy algorithms	pdf	16.1, 16.2	04/10/2016b
	Huffman coding	pdf	16.3	06/10/2016
	Website generating HC	link


Dynamic Programming	1D dynamic programming	pdf	15.1, KT 6.1	10/10/2016
	2D dynamic programming	pdf	15.3, 15.4
	DP over intervals	pdf	15.5, KT 6.5
	Extra DP (L1) Extra DP (L2)	pdf pdf	Extra DP examples Not all taught in class


Graph Algorithms	Introduction to graphs	pdf	Appendix B.4, B.5, 22.1	25/10/16
	Basic graph algorithms BFS Worked Example DFS Worked Example Topological Sorting	pdf pptx pptx pdf	22.2-22.5
	Minimum spanning trees Kruskal Worked Example Prim Worked Example	pdf pptx pptx	23, 21.1-21.3	01/11/16 29/10/16
	Shortest paths Bellman-Ford Example Dijkstra Example	pdf pptx pptx	24.1-24.3, 24.5, 25.1, 25.2	11/11/16
	Maximum flow Bipartite Matchings Matching Examples Stable Matchings	pdf pdf pdf pdf	26.1-26.3, KT 7.12 Joy of Matching³ Try St Matchings	14/11/16 23/11/16d

Review Session	Review Since Midterm	pdf

** Please see Revision log for documentation of any changes made to notes after original posting.

¹ The first few slides used by L1 and L2 differed slightly in presentation. For completeness, we provide copies of both.
² For Quicksort, L1 and L2 presented slightly different analyses; the slides reflect this. The final "revised analysis" slides were written after the class to provide clarification of questions posed by students. The "revised analysis" slides should be referenced as the definitive version.
³ Link is valid for all within the HKUST domain. Outside the HKUST domain, might only work for IEEE members.

Most references are to the CLRS textbook
* KT refers to the reference book by Jon Kleinberg and Éva Tardos.

Mathematical background: pdf