Algorithms and computational complexity

Anas's picture
Course Code: 
66314
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