Analysis of
Algorithms, Correctness of Algorithms
Author: PhD Jaanus Pöial, Estonian
IT College
All videoclips are captured
during fall semester of 2011 when the course was taught in
English.
Learning outcomes:
- Student knows the basic definitions of the field and is able
to estimate both time complexity and space complexity of
simple algorithms (average and worst case)
- Student is familiar with common complexity classes and
standard functions (constant, logarithmic, linear, polynomial,
exponential, etc)
- Student knows the basic definitions of correctness (total
correctness, partial correctness) and understands the basic
techniques to prove the correctness of algorithms (accordance
to outer specification)
Video (111 min)
Lecture Notes
Lecture 1 - Algorithms, properties of algorithms, time
complexity and space complexity, asymptotic behaviour of
functions, analysis of algorithms, main complexity classes (in
Estonian: algoritmide omadused, ajaline ja mahuline keerukus,
funktsioonide asümptootiline käitumine, algoritmianalüüs,
levinumad keerukuse mõõtmise etalonfunktsioonid)
Lecture 2 - Correctness of algorithms:
preconditions, postconditions, loop invariants, weakest
precondition, structural rules, total correctness and partial
correctness, halting problem (in Estonian: algoritmide
korrektsuse tõestamine, eel- ja järeltingimused,
tsükliinvariant, nõrgima eeltingimuse meetod, täielik ja
osaline korrektsus, peatuvuse probleem)
Extra
