Algorithms and computational complexity
Wed, 2010-04-14 19:34 — Anas Sami Tomeh
Course Outline:
Introduction:
-
What is an algorithm?
-
Algorithms as a Technology.
-
Components of an Algorithm.
-
Algorithm’s Efficiency.
Getting Started:
-
Insertion Sort.
-
Analyzing and Designing Algorithms.
-
Merge Sort.
Growth of Functions:
-
Complexity.
-
Growth Rates of Functions.
-
Proofs.
Recurrences:
-
Substitution Method.
-
Iteration Method.
-
Master Method.
Sorting and Order Statistics:
-
Heapsort.
-
Quicksort.
-
Sorting in Linear Time.
-
Medians and Order Statistics.
Data Structures:
-
Binary Search Trees - review.
-
AVL Trees.
-
Red-Black Trees.
Advanced Design and Analysis Techniques:
-
Dynamic Programming.
-
Greedy Algorithms
Graph Algorithms:
-
Elementary Graph Algorithms
-
Minimum Spanning Trees
NP-Completeness