Sign-in Links
CMPE 365 Algorithms I Units: 4.00
Principles of design, analysis and implementation of efficient algorithms. Case studies from a variety of areas illustrate divide and conquer methods, the greedy approach, branch and bound algorithms and dynamic programming.
(Lec: 3, Lab: 1, Tut: 0)
(Lec: 3, Lab: 1, Tut: 0)
Requirements: Prerequisites: ELEC 278 or MREN 178, ELEC 270 or any discrete mathematics course
Corequisites:
Exclusions:
Offering Term: F
CEAB Units:
Mathematics 0
Natural Sciences 0
Complementary Studies 0
Engineering Science 24
Engineering Design 24
Offering Faculty: Faculty of Arts and Science
Course Learning Outcomes:
- Possess a strong understanding of computational complexity, up to and including: Polynomial time Reducibility; classes P and NP; NP-Completeness; Proofs of NP-Completeness.
- Be able to recognize classical NP-Complete problems.
- Be able to prove that new problems are NP-Complete using polynomial time reductions from known NP-Complete problems.
- Apply key algorithm paradigms, both in the abstract and through concrete examples: Divide and Conquer; Greedy Algorithms; Dynamic Programming; Branch and Bound.
- Have some understanding of an advanced topic, which varies from year to yearRecent choices have included: Linear Programming; Computational Geometry; String Matching.