Algorithms

Notes: These summaries are made based on lecture notes of CSCI 3110 Design and Analysis of Algorithms I taught by Dr. Travis Gagie in fall 2019. I do not claim ownership of knowledge being shared. These notes are shared for study purposes

oRDER OF GROWTH & master theorem

The order of growth of the running time of an algorithm gives a simple characterization of the algorithms efficiency and also allows us to compare the relative performance of alternative algorithms.

• Asymptotic Notations

• Summary

• Examples

Greedy algorithm

A greedy algorithm obatins an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Note that this heuristic strategy does not always produce an optimal solution.

• Examples

• Summary

• Huffman Code

Dynamic programming