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: Grade of C or higher in COS 285.
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