February 25: course introduction and overview. Why do we need efficient algorithms? An example related to sorting: predicted running time of two well-known algorithms, Bubblesort and MergeSort, to sort 1GB of data. Measuring running time: theory and practice. First examples of analysis of simple iterative programs. Exercises:
February 27: exercises. Analysis of double nested for loops (quadratic running time). Introduction to the problem of Fibonacci numbers: the tree of rabbits.
March 4: A recursive algorithm for Fibonacci numbers. Analysis: recursion tree, recurrence relations. A key inefficiency: memoized solution. Iterative solution.
March 6: Implementation examples in Python: Fibonacci numbers. Recursive and iterative solution. Source code.
March 11: no class
March 13: no class
March 18: Asymptotic analysis: notation O, Omega, Theta. Worst, best, average case. Sequential search. Introduction to binary search.
March 20: Iterative binary search with analysis. Recursive binary search: analysis using the recursion tree and the recurrence relation. Solution of recurrences by iteration.
Exercise: analyze the binary search algorithm assuming that the array is divided into two unbalanced parts, where the left part is half of the right one (how do you choose index m?). Consider both an iterative and a recursive implementation.
March 25: Sorting algorithms (some nice visualizations). Quadratic algorithms: insertion sort, selection sort, bubble sort.
Exercise: the cocktail shaker sort is a variant of bubblesort that sorts in both directions (left-to-right and right-to-left) at each pass. You can find a description and implementation here. After providing your own pseudocode for the algorithm, analyze its best-case and worst-case running time and discuss the structure of best-case and worst-case instances.
March 27: Algorithm design and Python programming exercise: anagram checking. Three different solutions with running times O(n^2), O(n log n), O(n). Source code.
April 1: mergesort
April 3: master theorem, binary heaps
April 8: heapsort
April 10: quicksort
April 15: exercises
April 17: first midterm
April 29: trees and their representations, depth first search
May 6: exercises on DFS, breadth first search
May 8: binary search trees: search, insert and delete operations
May 13: AVL trees: Fibonacci trees, tree height, searching in O(log n) time
May 15: AVL trees: rotations, insert and delete operations
May 20: graph representation. DFS and its properties.
May 22: More on DFS. BFS and its properties.
May 27: no class due to elections
May 29: second midterm