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. Other discussions of this 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 Notes: [ PDF ] [ Video ]
- Supplemental Aid for Lecture Video:
[ PDF ]
- Implementations of Algorithm from Lecture Slides:
[ Python ]
[ Java ]
- Supplement — Examples of Proofs about Correctness: [ PDF ]
- Supplement — Example Trace of Execution and Recursion Tree:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
Ice-Breaking Topics
- Information about More Superheroes: [Captain Marvel] [Black Panther] [Shang-Chi] [Northstar] [Batwoman] [Dreamer]
Tutorial #3: Introduction to the Correctness of Algorithms I
-
Problems To Be Solved
- Implementations of Algorithm from Tutorial Exercise: [ Python ] [ Java ]
Assignment #1: Proving the Correctness of a Simple Recursive Algorithm
-
Problems To Be Solved
-
City.java:
This Java program should be downloaded and compiled before
you try to compile the programs you write to solve the
programming problems on Assignments #1 and #2.
-
Test_Benefits.java:
JUnit tests for the program you should write to solve
the programming problem on this assignment. These tests will
also be used when your program is marked.
- Assignment #1: Additional Information about Submission and Grading
Lecture #3: Introduction to the Correctness of Algorithms II — Correctness of Simple Algorithms with a While Loop
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Implementations of Algorithm from Lecture Slides:
[ Python ]
[ Java ]
- Supplement — More Examples of Proofs of Correctness: [ PDF ]
- Supplement – Two Useful Theorems about While Loops:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
Resources for Work on the Assignments
Students will be encouraged to work in groups when completing the assignments in this course. Resources provided by ITP Metrics, that are designed to help people to work more successfully in groups, will be provided for consideration and discussion in this lecture.
- ITP Lab Team Contract: [ Word ] [ PDF ]
- Assignments #1 and #2: Instructions for the Formation of an Assignment Group
Tutorial #4: Introduction to the Correctness of Algorithms II
-
Problems To Be Solved
- Implementations of Algorithm from Tutorial Exercise: [ Python ] [ Java ]
Lecture #4: Introduction to the Correctness of Algorthms III — Other Statements and Algorithms
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — Proofs Discussed in Lecture #4:
[ PDF ]
- Questions for Review:
[ PDF ]
Lecture Presentation
Resources for Work on Assignments
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — Proofs Discussed in Lecture #4:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
Resources for Work on Assignments
Resources provided by ITP Metrics includes surveys that can be completed to learn more about one’s personality traits and approaches to conflict. This information is sometimes helpful when you are getting ready to work with other people to complete a group assignment. You can follow the link, given below, to complete these surveys and submit them for assessment.
Reading Exercise #1: Introduction to the Testing of Programs
-
Assigned Reading
- Implementation of Algorithm from Tutorial Exercise #3: [ Java with Defensive Programming ]
Lecture #5: Analyzing the Efficiency of Algorithms
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — Proof of a Claim from the Lecture: [ PDF ]
- Supplement — The Logarithmic-Cost Criterion:
[ PDF ]
- Questions for Review: [ PDF ]
