CSc 4520/6520 DESIGN AND ANALYSIS: ALGORITHMS

Fall 2014
Computer Number 15048/9
MW 2:50pm - 4:35pm  auditorium ALC 312

Instructor:  Dr. Alex Zelikovsky
                     Office: 1443, Peachtree Str. 34
                     Phone: (404) 413 5730
                     Fax: (404) 413-5717
                     Email: alexz@cs.gsu.edu
                     Web site: http://alan.cs.gsu.edu/NGS/?q=content/classes
Office Hours: TT 2:00pm –2:50pm (except meetings), and others by appointment
Text:
- T. H. Cormen, C. E. Leiserson and R. L. Rivest "Introduction to Algorithms" MIT Press, 2nd or 3d  editions)
- Manber, Introduction to Algorithms, a Creative Approach, Addison-Wesley ( optional).

Course Content:
- General algorithmic paradigms: divide and conquer, greedy algorithms, dynamic programming.
- Sorting and order statistics: merge-sort, quicksort, heapsort;
- Data structures: binary heaps, priority queues, binary search trees;
- Graph algorithms: BFS/DFS, MST, topological sort, shortest paths;
- Computational Geometry: sweep-Line, convex hull, closest pair, voronoi diagrams/Delanau triangulation
- NP-completeness and approximation algorithms for combinatorial problems:
      -  independent set, clique, vertex cover, TSP, Steiner tree, set cover
- Additional topics: Stable matching, Linear programming, FFT.

Prerequisite: CSc 2010.
Withdrawals: The last day of regular withdrawal.
Course Requirements: Students should attend all classes, regularly complete all outside reading,
                                            project and other assignments.
Course Grades:
            CSc 4520 - Homework 20% (lowest will be dropped), program assignment - 10%, Quizzes 30% (lowest will be dropped), final 40%
            CSc 6520 - Homework 20% (lowest will be dropped), program assignment - 10%, Quizzes 30% (lowest will be dropped), project 40%
Other Policy:
Make-up's or missed deadlines must be arranged prior, and generally are not allowed.
Any material submitted for the grade should be the student's own work.
Collaboration is allowed prior to preparation of actual material that will be submitted for the grade.