CISC 320: Algorithms and Advanced Programming

Catalog Description:
Design and analysis of algorithms; worst-case/average-case analysis, proof techniques for correctness and performance of modern algorithms, control abstractions (divide and conquer, greedy method, branch and bound); NP-hard and NP-complete problems.

Current Texts:
Algorithm Design
Goodrich and Tamussia
John Wiley

Goals:
This course prepares students to study and explore the principles and complexities of basic discrete computer algorithms. Emphasis in on design, analysis and comparisons of algorithms. Good programming techniques are stressed throughout.

Content:

• Searching (binary, interpolation, balanced trees)
• Selection and related topics
• Minimum spanning trees -- Prim's algorithm
• Shortest paths - Dijkstra's algorithm
• Transitive closure: Floyd/Warshall algorithm
• Matrix multiplication
• Integer multiplication and polynomial evaluation
• String processing: KMP and Boyer-Moore matching, file compression, cryptology
• Geometric algorithms
• Dynamic programming: matrix mult and optimal BSTs
• Union-Find Methods
• NP-completeness and its implications