# Analysis of Algorithm: Course Outline MAT

The analysis of algorithms is the determination of the amount of resources (such as time and storage) necessary to execute them. Most algorithms are designed to work with inputs of arbitrary length.

## Course Outline

• Introduction to analysis of algorithms
• Insertion sort, merge sort
• Asymptotic notation, recurrences, substitution
• Master method
• Divide and conquer, strassen, Fibonacci polynomial multiplication
• Quicksort, randomized algorithms
• Linear time sorting, lower bounds, counting sort, radix sort
• Order statistics median
• Hashing and hash functions
• Universal hashing, perfect hashing
• Relation of bsts to quick sort, analysis of random bst
• Red black trees, rotations, insertions, deletions
• Augmenting data-structures, dynamic order statistics, interval trees
• Skip-lists
• Amortized-algorithms-table-doubling-potential-method
• Competitive-analysis-self-organizing-lists
• Dynamic-programming
• longest-common-subsequence
• Greedy-algorithms
• Minimum-spanning-trees
• Class & Method Design
• Shortest paths
• Dijkstras algorithm