Analysis of Algorithms II

20-CS-472 - Analysis of Algorithms II
Electrical Engineering and Computing Systems

Instructor

John Franco

John Franco
Electrical Engineering and Computer Science
University of Cincinnati
Cincinnati, Ohio 45221-0030

Email: franco@gauss.ececs.uc.edu
Phone: 556 1817
Office hours:
Monday, Wednesday 3:40-4:30, Rhodes 831,
or arrange a time by email

Registration Data

Credit Level: U. Credit Hrs: 3.00.
Prerequisites: 20-CS-471

Logistics

Meets: 10:00-10:50, MWF, Baldwin 643
Grader: xxx Office hours: xxx
Course material: my notes, web pages, Cormen and other texts

Course Description

Further introduction to the study of algorithms. Analysis of computing time, asymptotic notation and generating functions. Strategies for designing algorithms: Divide-and-conquer, Greedy method, Backtracking, etc. Further topics such as techniques for algebraic manipulations, lower and upper bound theory, NP-Complete problems, and parallel algorithms.

Keywords

Divide-and-Conquer, Greedy Algorithm, matroids, backtracking, Branch-and-Bound, Stochastic Local Search, complexity classes, NP-complete, NP, P, logic algorithms, Binary Decision Diagrams, probabilistic algorithm, lower bounds, upper bounds, probabilistic analysis.

Addendum

There are numerous sources of material on which the lectures will be based. Most of those are posted on the course website. The texts referred to here also contain much information. It is not required that any of these texts be purchased but it is highly recommended. There are many other great sources of information in this area and the student is encouraged to seek out such material independently.