Skip to main content

CSC 505 Design and Analysis of Algorithms

3 Credit Hours

Algorithm design techniques: use of data structures, divide and conquer, dynamic programming, greedy techniques, local and global search. Complexity and analysis of algorithms: asymptotic analysis, worst case and average case, recurrences, lower bounds, NP-completeness. Algorithms for classical problems including sorting, searching and graph problems (connectivity, shortest paths, minimum spanning trees).

Prerequisite

  • calculus and lower level math
  • discrete mathematics, for example CSC 226, or a comparable course
  • data structures, for example CSC 316, or a comparable course
  • basic programming skills

To brush up on your prerequisites, I recommend reviewing sections 3(2), 10, 12(1-3), and Appendix A, B, and C(1-2) of our textbook.

Course Objectives

You will learn how to solve problems using concepts of algorithms and discrete mathematics, e.g.

  • how to rigorously analyze correctness, time, and space usage of algorithms
  • when and how to use fundamental algorithms and data structures
  • how to apply algorithm design strategies such as recursion, divide-and-conquer, and dynamic programming.
  • in addition, each student will learn how to plan, prepare, and record a short podcast about a class topic

Course Requirements

Grades will be computed as a weighted average of four homework assignments (equal weights, total 20%), multiple announced online quizzes (equal weight, total 40%), a podcast episode about a class topic (consisting of outline, detailed draft, and audio recording, total 35%), and class participation (total of 5%). Bad quiz forgiveness rule: the two lowest quiz scores will be dropped.

The Piazza software (message board system) will be the primary mode of communication about all aspects of the course (questions about homework, exams, and course topics) – email should be used only for personal matters.

Homework assignments will be posted electronically and solutions must be submitted electronically. Submissions must be pdf files without any scanned parts. Late homework will be accepted only in circumstances that are grounds for excused absence under university policy (arrangements for turning in late homework must be made at least a day before the due date if possible).

All assignments for this course are intended to be individual work. Copying of text, code, or other content from the Internet (or other sources) is plagiarism. Any tool/resource must be approved in advance by the instructor and identified and acknowledged clearly in any work turned in.

Textbook

Introduction to Algorithms (third edition) by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein 2009, McGraw-Hill, ISBN 978-0-262-03384-8 (hardcover) or ISBN 978-0-262-53305-8 (paper).