Algorithm Analysis and Design

Student Learning Outcomes, Goals, Objectives:

Students successfully completing this course will be able to:

• understand how recursion works;
• know how to design divide-and-conquer algorithms using three steps and apply to merge sort, quick sort, Strassen’s matrix multiplication;
• understand asymptotic notation, and analyze common algorithms using them;
• Apply graph algorithms, including graph traversal, shortest paths, minimum spanning trees, and graph search techniques.
• Understand the fundamentals of algorithmic game theory and analyze basic game-theoretic algorithms and solution concepts.
• use a greedy strategy to solve some problems such as minimum spanning tree and shortest path;
• apply dynamic programming to problems such as matrix chain product, longest common subsequence, and graph algorithms;
• understand NP-completeness and why it is important;

Course Grading Information:

Activity/Performance Measure	Percentage/Points
Quiz 1–12 (lowest two dropped)	100%

Grading Scale:

Percentage	Letter Grade
93–100%	A
90–92%	A-
87–89%	B+
83–86%	B
80–82%	B-
76–79%	C+
70–75%	C
Below 75%	F

Attendance/Participation:

Attendance is encouraged but will not be counted toward the final course grade.

Course Materials Purchased by the Students:

No purchase is required. The primary reference is: Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms (4th Edition, MIT Press, 2022).