CSC 512 Syllabus (Fall Semester 2008)

Analysis and Design of Algorithms (graduate)

Credit hours: 3

Goals of the course: The aim of the course is to provide a solid background in design and analysis of algorithms for computer science students so to enable them to analyze problems encountered either in industry or advanced level courses and design efficient algorithms for them. General design paradigms will be introduced and applied on several typical example problems.

Recommended textbooks: I will not follow a single textbook in this course, listed below are some textbooks which I recommend:

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2/e, MIT Press, 2001.
• Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006.
• Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms.

Topics (tentative): Mathematical essentials. Asymptotic notations. Practical complexities. String Matching algorithms. Advanced data structures (heaps, graph, disjoint set union/find). Main design techniques: divide and conquer, greedy algorithms, dynamic programming, backtracking. Randomized algorithms. Introduction to NP theorem.

Evaluation (tentative): Assignments:  30 points; Midterm exams (2):  30 points; Final exam:  40 points

Yahoo group for this course: http://groups.yahoo.com/group/CSC512-G-KSU/You must subscribe to the group in order to post/download materials. To join, send a short email to: CSC512-G-KSU-subscribe@yahoogroups.com

Below you'll find some old exams and a cheat sheet.

### CSC512_Materials

 Modified By

Theoretical CS Cheat Sheetعقيل محمد مصطفى عبدالرحمن العظ
Midterm (Fall 06)عقيل محمد مصطفى عبدالرحمن العظ
Assignment 4 (Fall 06)عقيل محمد مصطفى عبدالرحمن العظ
Assignment 3 (Fall 06)عقيل محمد مصطفى عبدالرحمن العظ
Assignment 2 (Fall 06)عقيل محمد مصطفى عبدالرحمن العظ
Assignment 1 (Fall 06)عقيل محمد مصطفى عبدالرحمن العظ
Useful Mathematical Formulasعقيل محمد مصطفى عبدالرحمن العظ