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.