CSC 505 Design and Analysis of Algorithms

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). 3 credit hours.


• Prerequisites
  • 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. 

• Course Requirements

Grades will be computed as a weighted average of four homework assignments (equal weights, total 20%), two midterm exams (equal weight, total 40%), and the final exam (total 40%). Bad midterm forgiveness rule: one lowest midterm score will be replaced by the final exam score if this improves your grade.

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).

• Computer and Internet Requirements

NCSU and Engineering Online have recommended minimum specifications for computers. For details, click here.

• Instructor

Dr. Steffen Heber, Associate Professor
Dept. of Computer Science
2260 EB2, Box 8206
NCSU Campus
Raleigh, NC 27695-8206

Phone: 919-513-1118
Fax: 919-515-7896