CS202
Download as PDF
Design and Analysis of Algorithms
Course (UG/PG)
Undergraduate
Offering Unit/Department
Course Description
This course builds on students’ earlier programming experiences, mathematical knowledge (discrete math and linear algebra), and knowledge of data structures, to the question of how to solve problems by designing algorithms for efficiency. The materials as well as the assignments rely on proficiency with Python programming language.
Students will learn:
· The different paradigms of algorithm design such as greedy, divide and conquer, and dynamic programming.
· Limits of algorithm design via a study of intractability including reductions of given problem to known problems. This includes knowledge of NP/co-NP. The approach will not be via the more rigorous Turing machine/Formal language approach as the students do not have that prerequisite knowledge.
· More modern algorithm design concept such as randomization and approximation to achieve more effective problem solving and more efficient solutions.
This course will go into the theoretical underpinnings of efficiency, algorithm correctness, and how algorithm design has a basis in identifying mathematical properties of the problem.
Students will learn:
· The different paradigms of algorithm design such as greedy, divide and conquer, and dynamic programming.
· Limits of algorithm design via a study of intractability including reductions of given problem to known problems. This includes knowledge of NP/co-NP. The approach will not be via the more rigorous Turing machine/Formal language approach as the students do not have that prerequisite knowledge.
· More modern algorithm design concept such as randomization and approximation to achieve more effective problem solving and more efficient solutions.
This course will go into the theoretical underpinnings of efficiency, algorithm correctness, and how algorithm design has a basis in identifying mathematical properties of the problem.
Course Learning Outcomes
- Understand the efficiency notations of functions, e.g., Big O, Omega, Theta
- Analyze the correctness and the complexity of an algorithm
- Design and develop algorithms to solve computational problems within the scope of this course
- Understand intractability and the scopes of NP completeness and NP hardness
Discipline-Specific Competencies
Algorithm Analysis, Combinatorial Decision-making, Problem-solving & analysis, Algorithmic thinking, Source Code Optimisation
SMU Graduate Learning Outcomes
Disciplinary Knowledge, Critical thinking & problem solving, Collaboration and leadership, Self-directed learning
Grading Basis
GRD - Graded
Course Units
1