Winter 2017 / CSC 340 Algorithms

Concepts For Weeks 1 and 2

Regardless of what is in these notes, you as the student are responsible for everything covered in lecture. The main learning goals of weeks 1 and 2:

- Understand the definition of algorithmic problem an an input-output relation, and the concepts of algorithm and basic step or basic operation. The notions of correctness and efficiency; the different types of program invariants (loop invariant, class invariant, precondition and postcondition) and their role in proving correctness.
- Be able to provide a proof of correctness for an algorithm using the concept of invariants.
- Understand time and space as measures of efficiency. The size of an instance of a problem. How to determine the number of basic steps executed by an algorithm; Worst-case and average-case complexity of an algorithm.
- Comparing algorithms through the complexity classes. Big O, Big Omega, and Big Theta. Proofs involving Big O, Big Omega and Big Theta; the hierarchy of complexity classes.
- The concepts of polynomial-time complexity and tractability; exponential time and intractability. Optimality of algorithms.