Time: T/Th 11:00-12:15...Room: Baldwin 757

Professor:

Kenneth Berman Office:, Rhodes 891
Telephone: 556-5205, E-mail: ken.berman@uc.edu
Office Hours: (to be announced)

Web:

Check on my homepage regularly for an updated version of this syllabus, announcements, assignments, etc. My web homepage address is:

http://www.ececs.uc.edu/~berman/472-2002
 

Teaching Assistant: Anshumaan Rajshiva
E-mail: rajshia@ececs.uc.edu

Web address: http://www.ececs.uc.edu/~rajshia
Office: (to be announced)

Prerequisite:

Design & Analysis of Algorithms I

Textbook:

Kenneth A. Berman and Jerome L. Paul, Fundamentals of Sequential and Parallel Algorithms, PWS, 1997.

Goals:

Provide a solid foundation for the classical theory of sequential algorithms, and to cover some of the most important recent algorithmic developments, including the rapidly emerging theory of parallel algorithms. Provide the mathematical tools necessary to analyze the correctness and efficiency of algorithms, and to be able to judge how close an algorithm is to being optimal for a given problem. To enhance the ability to create new algorithms or to modify existing algorithms in order to solve new problems.

Description:

Continuing the study of sequential and parallel algorithms begun in the first course in the sequence. Intro to graph theory and graph algorithms.    Major design strategies: the greedy method, divide-and-conquer, dynamic programming, NP-completeness

Approximate Schedule (subject to change):

1. Intro to parallel algorithms and architectures (Chapter 5)
2. Parallel Sorting (Chapter 6)
3. Graphs, Digraphs and Sets (Chapter 8)
4. Greedy Method (Chapter 12)
5. Divide-&-Conquer (Chapter 13)
6. Dynamic Programming (Chapter 14)
7. Intro to NP-complete problems (Chapter 20)

Assignments:

There will be 3 homework assignments. It is very important that the homework is done neatly and handed in on time. Programs should be well documented.

Grading:

Approximate distribution of credit: two tests counting 30% each. Homework assignments count 40%.

Late work is accepted only because of a) illness; b) family emergencies; and c) conflicts approved by me in advance.