An introduction to the design and analysis of computing algorithms. Techniques for designing algorithms, such as divide-and-conquer, greedy method, dynamic programming, and backtracking, are emphasized and illustrated. Many problems of practical importance are covered, including matrix operations, number theory, minimum spanning tree, single-source shortest path, traveling salesperson, and graph search. The concepts of NP-completeness are also considered. Substantial programming in a high-level language is required. COS 485 is a core requirement for the University of Southern Maine Computer Science major. Credits: 3.
Prerequisite(s): Grade of C or higher in COS 360.
Learning Outcomes
By the end of this course, students will be able to:
- List various algorithm design techniques.
- Explain how different algorithm design principles translate to computational solutions.
- Use mathematical analysis to calculate expected runtimes of algorithm designs.
- Evaluate and compare algorithms’ performance on problems using experiments.
- Assess the effectiveness of different techniques for designing efficient algorithms.
- Prove properties like correctness and computational complexity.
- Design experiments to compare algorithms.
- Compose clear written explanations of algorithmic approaches.
Textbook
Neapolitan, R. E. (2015). Foundations of Algorithms (5th ed.). Jones & Bartlett Learning.
Syllabus
Offered
Spring Semester