Computer Science 331 — Introduction to the Analysis of Algorithms

Algorithm Analysis

Introduction to the Analysis of Algorithms

Overview

These initial lectures introduce techniques that can be used to prove the correctness of simple algorithms and bound their running times. Students will be required to use these techniques to solve problems on assignments and tests in this course.

Unfortunately there does not seem to a standard way to present some of this material. Descriptions of this from other places might describe things very differently and may use technial terms like “loop invariant” to mean different things. The lecture notes that are supplied here should, therefore, be used as the main reference for this material.

When techniques are introduced one of more examples are provided — but a general description of how to use the technique is generally also supplied. This general description should be consulted when you try to use these techniques yourself. It will often not be easy (or even possible) to modify one of the examples to solve a new problem, instead.

Implementations of the algorithms from lectures and tutorials are supplied as both Python and Java programs. Students are encouraged to compile the Java programs and execute both versions in order to verify claims about what happens when the algorithms from this course are implemented and used.

Lecture #2: Introduction to the Correctness of Algorithms I — Correctness of Simple Recursive Algorithms

Required Reading

Lecture Presentation

Implementations of the Algorithm Considered in This Lecture

Additional Information That May Be of Interest

Tutorial #3: Introduction to the Correctness of Algorithms I

Lecture #3: Introduction to the Correctness of Algorithms II — Simple Algorithms with a While Loop

Required Reading

Lecture Presentation

Implementations of the Algorithm Considered in This Lecture

Additional Information That May Be of Interest

Tutorial #4: Introduction to the Correctness of Algorithms II

Reading Exercise #1: Introduction to the Testing of Programs

Lecture #4: Analyzing the Efficiency of Algorithms

Required Reading

Lecture Presentation

Additional Information That May Be of Interest

Tutorial #5: Analyzing the Efficiency of Algorithms

Lecture #5: Asymptotic Notation

Required Reading

Lecture Presentation

Additional Information That May Be Of Interest

Tutorial #6: Asymptotic Notation

Assignment #1: Proving the Correctness of Simple Algorithms — and Implementing Them as Java Programs


University of Calgary Extension of Logo
Department of Computer Science

cpsc 331 computer science faculty of science u of c

cpsc 331 intro and math review analysis of algorithms basic data structures and adts search trees hash tables searching and sorting graph algorithms java develoment exercises assignments tests