Readings on the Analysis of Algorithms

Readings on the Analysis of Algorithms

This set of notes is provided for students moving into the computer science program after having completed the data structures course CPSC 319 instead of CPSC 331. They can also be used by students in senior courses in theoretical computer science who wish to review material about establishing the correctness and efficiency of algorithms.

Reading #1: Review of Proofs and Mathematical Induction

• Notes on This Topic
• A Suggested Exercise
• Solution for Suggested Exercise
• Questions for Review
• Assignment

Reading #2: Proving the Correctness of a Simple Recursive Algorithm

• Notes on This Topic
• Fully Documented Version of the Algorithm “MaxInRange”
• A Suggested Exercise
• Solutions for Suggested Exercise
• Questions for Review
• Assignment

Reading #3: Proving the Partial Correctness of a Simple Algorithm with a Loop

• Notes on This Topic
• Supplemental Document: A Useful Theorem about while Loops
• A Suggested Exercise
• Solutions for Suggested Exercise
• Questions for Review
• Assignment

Reading #4: Proving Termination and Analyzing the Running Time of a Simple Algorithm with a While Loop

• Notes on This Topic
• Supplemental Document: Another Useful Theorem about while Loops
• Supplemental Document: A Fully Documented Version of the arrayMax Algorithm
• A Suggested Exercise
• Solutions for Suggested Exercise
• Questions for Review
• Assignment

Reading #5: Analyzing the Running Time of a Simple Recursive Algorithm

• Notes on This Topic
• Supplemental Document: Analyzing Running Time as a Function of Input Size
• A Suggested Exercise
• Solutions for Suggested Exercise
• Questions for Review
• Assignment

Reading #6: Asymptotic Notation and Standard Functions

• Notes on This Topic
• A Suggested Exercise
• Solutions for Suggested Exercise
• Questions for Review
• Assignment

main page for notes computer science faculty of science u of c

Reading #1 Reading #2 Reading #3 Reading #4 Reading #5 Reading #6