Notice: This repo was archived on May 14th, 2021.
This repository contains tutorial material for Design and Analysis of Algorithms at the University of the West Indies, St. Augustine. Note that this repository created for material sharing convenience, and all solutions may be redacted at the end of the academic year in 2021.
No Class.
Introduction to time efficiency analysis and mathematical proofs.
Overview of the properties of asymptotic notations, comparing orders of growth using limits and time efficiency calculations using summation formulae.
Brute force approaches and their time efficiency calculations.
Decrease and conquer approaches and their time efficiency calculations (plus an introduction to Master's theorem).
Divide and conquer approaches and their time efficiency calculations.
Deriving recurrence relations. Transform and conquer approaches and their time efficiency calculations.
Dynamic programming algorithms.
Greedy approach.
Backtracking and branch-and-bound techniques.
No class. Review this instance of the 0/1 branch-and-bound knapsack problem from Week 10.
Branch-and-bound technique and space-and-time trade-offs (comparison and distribution counting).
Please revise the basic properties of logarithms and the summation formulas and rules [1].
[1] Levitin, Introduction to the Design & Analysis of Algorithms, 475–476