Design and Analysis of Algorithms
Prerequisites
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.
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
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).
Student Outcomes
| Level Of Emphasis | |||
| ABET Outcome | Low | Medium | High |
| 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 | ||
Text
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms. Fourth Edition. MIT Press. ISBN: 978-0262046305
Topics
- 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
- NP-completeness
- Optional topics may include: multithreaded algorithms, flow networks, linear programming, number theoretic algorithms
Grading
| 10% – 40% | Homework Assignments |
| 20% – 50% | Quizzes or Midterm Exams |
| 20% – 30% | Final Exam |
| 0% – 30% | Projects |
| 0% – 10% | In-class Exercises |