Course Description

This course introduces formal techniques to support the design and analysis of algorithms, focusing on both the underlying mathematical theory and practical considerations of efficiency. Topics include correctness of algorithms, asymptotic notation, recurrences and Master theorem, divide and conquer, transform and conquer (Balanced Trees), time-space trade-offs, median and order statistics, searching and sorting algorithms, dynamic programming, greedy algorithms, randomized algorithms, recursive backtracking, computational geometry, string matching. Optional material: NP-completeness, competitive analysis, branch-and-bound, amortized analysis and approximation algorithms.

Course Requirements

  • Pre-requisite: CS2311 – Data Structures
  • Credit Hours: 3 CHs
  • Contact Hours: (3 hours lecture)

Textbook

Title: “Introduction to the Design and Analysis of Algorithms”
Author: Anany V. Levitin
Publisher: Pearson 2011
Year/Edition: 2011

Topics

  1. Chapter 1: Introduction
  2. Chapter 2: ِAlgorithm Analysis
  3. Chapter 3: Brute force and Exhaustive Search
  4. Chapter 4: Decrease and conquer
  5. Chapter 5: Divide and conquer
  6. Chapter 6: Transform and conquer
  7. Chapter 7: Dynamic programming