CPSC 413 Design & Analysis of Algorithms I

CPSC 413 is the primary course on algorithmics. Algorithmics is what defines computer science. Without algorithms, there would be no computer science discipline. An algorithm is to take some input, manipulate the input data, and produce some output. A good algorithm has three properties: (1) it works correctly, (2) it works efficiently, and (3) it is easy to understand. We would like to avoid algorithms that are wrong, slow, or overly complicated.

In the course, we discuss three powerful techniques for designing such algorithms: greedy heuristics, divide & conquer, and dynamic programming. These techniques help us design algorithms that satisfy our three properties: correctness, efficiency, and simplicity. We use mathematical arguments to guide us when designing and analyzing our algorithms. We discuss how to generate algorithmic ideas, how to systematically analyze our ideas, and how to verify that our algorithms work correctly.

Some computational problems are so difficult that we do not know any efficient algorithms for solving them. We discuss how to recognize and understand such difficult problems. We use NP, reducibility and complexity classes to help us understand computational hard problems.

We will develop our skills in thinking recursively and in fluidly shifting between recursive and iterative thinking. We show how mathematical analysis, algorithmic development and practical testing are all parts of designing powerful algorithms. We discuss how to communicate computer science and algorithmic ideas.

The course has several prerequisites on mathematical arguments, familiarity with algorithms, and logical argumentation. Read more at the official CPSC 413 calendar entry.

https://www.cpsc.ucalgary.ca/~hoyer/