ESF logo        EIC logo



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:
  1. 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)
  2. Student is familiar with common complexity classes and standard functions (constant, logarithmic, linear, polynomial, exponential, etc)
  3. 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)
Video 1 - Analysis of algorithms
Video 2 - Correctness of algorithms
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

BeST logo

Creative Commonsi litsents
See teos on litsentseeritud Creative Commonsi Autorile viitamine + Mitteäriline eesmärk + Jagamine samadel tingimustel 3.0 Jurisdiktsiooniga sidumata litsentsiga.