Analysis of Algorithms
Ideally, most of the material included in Lectures 2–5 is a
review of material introduced in CPSC 331. A set of
readings on the analysis of algorithsm
is also available. This introduces this topic just as it will be covered
in this section of CPSC 413, but includes different examples and
exercises.
Lecture #2: Proving the Correctness of a Simple Recursive Algorithm
Tutorial Exercise #2: Proving the Correctness of a Simple
Recursive Algorithm
Lecture #3: Proving the Correctness of a Simple Algorithm with a While Loop
Reading Exercise #2: Proving the Correctness of Somewhat More Complicated
Algorithms
Tutorial Exercise #3: Proving the Correctness of a Simple Algorithm with
a Loop
-
Problems To Be Solved
-
Fibonacci1a.java:
Another Java implementation of the algorithm discussed in Lecture #2, with
changes made to ensure that much larger integers can be represented exactly
-
Fibonacci1.py:
Python implementation of the algorithm discussed in Lecture #2
-
Fibonacci2a.java:
Another Java implementation of the algorithm discussed in Tutorial Exercise #2,
with changes made to ensure that larger integers can be represented exactly
-
Fibonacci2.py:
Python implementation of the algorithm discussed in Tutorial Exercise #2
-
Fibonacci3.java:
Java implementation of the algorithm discussed in Lecture #3
-
Fibonacci3.py:
Python implementation of the algorithm discussed in Lecture #3
-
Fibonacci4.java:
Java implementation of the algorithm discussed in this tutorial exercise
-
Fibonacci4.py:
Python implementation of the algorithm discussed in this tutorial exercise
Lecture #4: Analyzing the Running Time of a Simple Algorithm with a
While Loop
Tutorial Exercise #4: Analyzing the Running Time of a Simple Algorithm
with a Loop
Reading Exercise #3: The Logarithmic Cost Criterion
Lecture #5: Analyzing the Running Time of a Simple Recursive Algorithm
Tutorial Exercise #5: Analyzing the Running Time of a Simple Recursive Algoairhm
Reading Exercise #4: Analyzing Running Time as a Function of Input Size
Lecture #6: Asymptotic Notation and Standard Functions
Tutorial Exercise #6: Asymptotic Notation and Standard Functions
Assignment #1: Analysis of Simple Algorithms
