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 hour credits

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 combinatons, 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 comptation), 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 based 15% on the homework, 5% on the prerequisite quiz (Tuesday, January 18), 5% on other quizzes (unannounced), and 25% on each of three exams (two midterms and a final). An average of 90% or greater guarantees an A, 75% guarantees a B. Other factors, such as improvement in performance and consistent quality and creativity on homework problems, will be used to decide grades in borderline situations. I will assign about 25 homework problems during the semester. A homework assignment will be due about every other week. In order to perform well on the tests, it is important that you work through the homework on your own, asking for help by email or message board if you have trouble understanding the concepts. Use email (plain text is preferred) for questions that reveal details of your homework solutions, the message board for all others. Homework assignments will not be handed out in class. Homeworks are due on ...to be decided (not at class time) and should be turned in at ...to be decided submitted electronically, or emailed to the TA before ... (see the homework page for more details). 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 during the previous class if possible). Homework must be stapled (not folded) with the cover sheet , completed and signed by you, attached to the front. Electronically submitted homework should include the information on the cover sheet (your signature is assumed).
Textbook		Introduction to Algorithms (Second Edition) by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein (2002, McGraw-Hill, ISBN 9780072970548).
Computer and Internet Requirements		NCSU has recommended minimum specifications for computers that are generally used for courses. Those specifications can be found here: http://www.ncsu.edu/it/compspecs/ Engineering Online recommends that your computer meets or exceeds the following minimum specifications below. A computer with greater capability (processor speed, RAM, internet bandwidth, disk capacity) will be more likely to properly display the video content of Engineering Online courses. Windows: Microsoft Windows XP, Windows 2003, or Windows Vista Intel-compatible 1 GHz processor 512 MB RAM 60 GB hard drive with 1 GB free space available Video display at 1024 x 768 or greater Sound output and speakers Microsoft Internet Explorer 6.0 SP1 or later, Firefox 2.0 or later, or Google Chrome 1.0 Windows Media Player 9.0 or later Real One Player Basic (required for certain courses) Adobe Acrobat Reader Broadband Internet connection (256 Kbps or more) Mac OS X: Mac OS X 10.4.8 or later G4 processor 512 MB RAM 60 GB hard drive with 1 GB free space available Video display at 1024 x 768 or greater Sound output and speakers Safari 2.0.4 (or later) or Firefox 2.0 (or later) Silverlight (viewers may be prompted to install this when first viewing a presentation) Real One Player Basic (required for certain courses) Adobe Acrobat Reader Broadband Internet connection (256 Kbps or more) NOTE: The Flip4Mac plug-in causes problems when viewing Mediasite presentations and should be disabled. Linux: Playback of Mediasite presentations on Linux is accomplished via the Moonlight Project, an open source implementation of Microsoft Silverlight. For more installation on the installation and configuration of Moonlight, please visit http://www.go-mono.com/moonlight/. The compatible operating systems and browsers are listed on this page. Microsoft Media Pack for Moonlight Adobe Reader for Unix Broadband Internet connection (256 Kbps or more)
Instructor		Dr. Matthias Stallmann, Associate Professor North Carolina State University Dept. of Electrical & Computer Engineering and Computer Science Engineering Bldg II (COE II) 2252, Box 8206 NCSU Campus Raleigh, NC 27695 Phone: 919-515-7978 Fax: 919-515-7896 EMail: matt_stallmann@ncsu.edu Web Site: http://people.engr.ncsu.edu/mfms/