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.


• Prerequisite
  • Calculus and lower level math (approximating the area under a curve, limits, L'Hôpital's rule, logarithm identities, summation formulas, complex numbers, polar coordinates, sines and cosines),
  • Discrete Mathematics [CSC 226] (Solving recurrences, permutations and combinations, proof techniques, induction, logic, equivalence relations, partially ordered sets),
  • Data structures [CSC 316] (stacks, queues, lists, trees, graphs, abstract data types, recursion, binary search trees, balanced tree schemes, tree traversals, big-O notation),
  • (recommended) Automata Theory [CSC 333] (Turing machines, nondeterministic computation),
  • Structured Programing Language (abstract data types, recursion).

For quick reference, much of this material is reviewed in the following sections of the text: 3.2, 10.1-10.4, 11.1-11.3, 12.1-12.3; and Appendix A.1, all of B, and C.1.

• Course Objectives
  • to become comfortable with rigorous mathematical approaches to computational problems: proofs of correctness of algorithms, analysis of running time, mathematical models of computation, properties of problems that lead to efficient algorithms or make them intractable
  • to get an overview of and experience with the most prevalent algorithm design techniques: greedy, divide and conquer, dynamic programming, graph searching, and the use of efficient data structures
  • to acquire the ability to analyze worst-case and average-case running times of algorithms
  • to be exposed to problem domains in which theoretical results in algorithm design and analysis have practical applications

• 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