Design and Analysis of Algorithms

Prerequisites

C or better in (MATH 142 (Calculus and Infinite Series) or MATH 152 (Calculus II)), CMSC 341 (Data Structures), and STAT 355 (Probability and Statistics)

Description

This course studies fundamental algorithms, strategies for designing algorithms, and mathematical tools for analyzing algorithms. Fundamental algorithms studied in this course include algorithms for sorting and searching, hashing, and graph algorithms. Mathematical tools include asymptotic notations and methods for solving recurrences. Algorithm design strategies include the greedy method, divide-and-conquer, dynamic programming, and randomization.

Course Outcomes

1. An in depth introduction to the design and analysis of algorithms, providing the student with the understanding and the skills needed to design and analyze algorithms.
2. Proficiency with fundamental algorithmic building blocks.
3. A rudimentary understanding on how algorithms fit within the larger context of computer science, mathematics, and other disciplines.

Program Outcomes

Text

Introduction to the Design and Analysis of Algorithms (3rd Edition), Anany Levitin, Pearson Press, 2012. Required

Topics

• Introduction
  • What is computable? What is an algorithm?
  • Measures of algorithmic efficiency, i.e., space and time complexity.
  • Fundamental tools, i.e., asymptotic notation and methods for solving recursions
  • When is a program correct? I.e., a brief look at program verification.
• Number theoretic and symbolic algorithms
• Divide and conquer algorithms
• Graph algorithms
• Greedy algorithms
• Dynamic programming
• Linear programming
• The fast Fourier transform
• P versus NP
• Quantum algorithms and reversible computation

Grading

Updated: March 4, 2011