Design and Analysis of Computing Algorithms (COS 485 / Spring 2024)

Department of Computer Science at the University of Southern Maine

Instructor: James Quinlan
Day/Time: Tue/Thur 12:30pm - 1:45pm (Payson Smith 207)
Syllabus: .pdf

---

Course description

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 Computer Science major at University of Southern Maine.

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

Prerequisites

Grade of C or higher in COS 285 - Data Structures

Textbook

Neapolitan, R. E. (2015). Foundations of Algorithms (5th ed.). Jones & Bartlett Learning.

Additional Resources

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
• Kleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Skiena, S. S. (2020). The algorithm design manual (3rd ed.). Springer.
• Dictionary of Algorithms and Data Structures

Unix Computer Lab

The Unix computer lab is located in 103 Science, and is accessible when the building is unlocked: roughly 7:00 am – 10:00 pm M-F. You are permitted to stay later if you are already in the lab.

Programming Language

COS 485 is programming language agnostic. The book uses "C/C++" like pseudo-code. Choose a language wisely. Maybe you will select a language you have been wanting to learn (e.g., C++), one with simple syntax (e.g., Python), or one that is highly expressive (e.g., Octave).

Communication

Please communicate through Brightspace.

Grading

Grades will be based on assignments (homework, in-class, coding projects), attendance/participation, a midterm, and a final exam with the following percentages:

• 10%: Attendance and Participation
• 50%: Assignments (includes homework, in-class, and/or programming projects)
• 20%: Midterm Exam (March 7, 2024)
• 20%: Final Exam (April 30, 2024)

Final Exam

Final Examination The final examination will be an in-person, written, comprehensive examination. Per the registrar’s schedule, it will be given on Tuesday, April 30, from 11:00 a.m. to 1:00 p.m. in Payson Smith 207.

LaTeX Template

Assignments must be neatly prepared and submitted through Brightspace under the associated assignment. It is recommended to typeset assignments in LaTeX (.tex) or Markdown (.md). This LaTeX template can be used. Check out the tutorial: Learn LaTeX in 30 minutes. The website containing a compresensive list of LaTeX Symbols is useful. Basic markdown syntax website is a markdown guide. You may use verbatim to include code. For example,

\begin{verbatim}
for i in range(10):
  print(i)
\end{verbatim}

Late policy

Unless otherwise noted, homework assignments will be due on Friday by 11:59pm. Late submissions will not be accepted. In recognition of the fact that there may unforeseen circumstances that prevent you from submitting some assignments, the two lowest homework grades will be dropped.

Tips for Success

• attend all class meetings
• read the material before coming to class
• complete assignments by the due dates specified
• create a study and/or assignment schedule to stay on track
• read announcements
• communicate regularly with your instructor and peers
• read and respond to course email messages as needed
• utilize USM's Online Student Support Services

Classroom Policies

1. No cellphones (put it away)
2. Bring a laptop (but only use when coding)
3. No AI (you are not learning if copilot codes for you)