Module: Analysis examples

Insertion sort, merge sort, asymptotic analysis, recurrences, loop invariants, linear search, binary search.

Learning Outcomes

Understand analysis of algorithm styles.

By viewing examples, become familiar with the style of analysis used in ICS 311.


Insertion Sort

Insertion sort example

Screencast Suthers 8 min

Loop Invariant

Loop invariant example

Screencast Suthers 6 min

Insertion sort analysis

Insertion sort analysis

Screencast Suthers 28 min

Merge Sort

Merge sort example

Screencast Suthers 11 min

Merge Sort Analysis

Merge sort analysis

Screencast Suthers 21 min

CLRS 2 - Getting started

Getting started with analysis of algorithms

Textbook 26 pages

Introduction to algorithms, Lecture 1

Analysis of algorithms-insertion sort, asymptotic analysis, merge sort, recurrences

Screencast Leiserson 80 min

Chapter 2 Notes

Modeling a problem, loop invariants, analysis


Experiential Learning

More on linear and binary search

Analyze linear and binary search (homework)