Design and Analysis of Algorithms
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)
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.
- 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.
- Proficiency with fundamental algorithmic building blocks.
- A rudimentary understanding on how algorithms fit within the larger context of computer science, mathematics, and other disciplines.
Introduction to the Design and Analysis of Algorithms (3rd Edition), Anany Levitin, Pearson Press, 2012. Required
- 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