Course contents:

This course investigates data structures, methods, technques, and theories for algorithm analysis and design. Topics include: advanced data structures and algorithms for graph, string, geometric, and operations research problems; algorithms on parallel computational models; and parameterized, randomized, approximation, and heuristic algorithms to cope with NP-completeness.

Prerequisites:

CSCI 6470/4470 Algorithms.
CSCI 6610 Automata and Formal Languages.

Texts:

Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 2nd ed, McGraw-Hill, 2001.

Grading policy:

Three written reports 30%
One research project (report and presentation): 50%
Final exam: 20%
All homework answers need to be typed or word-processed.
Late homework answers will not be accepted.

Tentative schedule:

Part I. Algorithms for graph, string, geometric problems (4 weeks)
Part II. Parallel computation models and algorithms (2.5 weeks)
Part III. Parameterized and randomized algorithms (3.5 weeks)
Part IV. Approximation and heuristic algorithms(4 weeks)

It is expected that the work you submit is your own. Plagiarism and other forms of academic dishonesty will be handled within the guidelines of the Student Handbook. The usual penalty for academic dishonesty is loss of credit for the assignment in question; however, stronger measures may be taken when conditions warrant.

Attendance policy:

Regular class attendance is required though class attendance may not be used in the final determination of grades. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.