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¶
Chapter 1: Introduction
Chapter 2: ِAlgorithm Analysis
Chapter 3: Brute force and Exhaustive Search
Chapter 4: Decrease and conquer
Chapter 5: Divide and conquer
Chapter 6: Transform and conquer
Chapter 7: Dynamic programming