Design and Analysis of Algorithms
Students must have completed: (MATH 142 or MATH 152) and CMSC 341 and one of the following (STAT 355, STAT 451, or CMPE 320) all with a grade of ‘C’ or better.
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.
Each student will:
- Have acquired the mathematical skills to rigorously analyze the running time, memory usage and correctness of algorithms.
- Have gained the problem-solving skills needed to develop algorithms for new problems using several algorithmic paradigms including: iterative improvement, divide and conquer, greedy and dynamic programming.
- Be familiar with the performance analysis and proofs of correctness for a broad range of standard algorithms (sorting & searching and basic graph algorithms).
|Level Of Emphasis|
|Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions.||X|
|Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline.||X|
|Communicate effectively in a variety of professional contexts.||X|
|Recognize professional responsibilities and make informed judgments in computing practice based on legal and ethical principles.||X|
|Function effectively as a member or leader of a team engaged in activities appropriate to the program’s discipline.||X|
|Apply computer science theory and software development fundamentals to produce computing-based solutions.||X|
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms. Fourth Edition. MIT Press. ISBN: 978-0262046305
- Asymptotic analysis
- Recurrence relations
- Divide and Conquer algorithms
- Sorting: Mergesort, Heapsort, Quicksort, and linear-time sorts
- Dynamic programming
- Greedy algorithms
- Graph algorithms: breadth-first search, depth-first search, minimum spanning trees, shortest paths
- Optional topics may include: multithreaded algorithms, flow networks, linear programming, number theoretic algorithms
|10% – 40%||Homework Assignments|
|20% – 50%||Quizzes or Midterm Exams|
|20% – 30%||Final Exam|
|0% – 30%||Projects|
|0% – 10%||In-class Exercises|