CISC-365/3.0 Algorithms IOriginal Author: Robin Dawes
Last Revised: October 16, 2006
Principles of design, analysis and implementation of efficient algorithms. Case studies from a variety of areas illustrate divide and conquer methods, the greedy approach, branch and bound algorithms and dynamic programming.
Prerequisites: CISC 203/3.0, 204/3.0, 235/3.0.
Learning Hours 120 (36L;84P)Objectives
This course introduces some fundamental algorithmic paradigms, and also introduces the topic of NP-completeness. This knowledge is essential in all fields of computer science.
The courses to which this course is a prerequisite are:
and CISC-365/3.0 is recommended for CISC-462/3.0 (Computability and Complexity).
This course is required in BMCO, CSCI, SODE, and MAJ.Topics
Complexity of algorithms and Complexity of problems
Complexity Notation, Reducibility, P, NP, and NP-Completeness, Classic NP-Complete Problems, Proofs of NP-Completeness.The Divide and Conquer Paradigm
Quicksort, Median Value of a Set, Closest Pair of Points.The Greedy Paradigm
Huffman Coding, Change-Making Problem, Activity Selection, Minimum-Weight Spanning Trees.The Dynamic Programming Paradigm
Longest Common Subsequence, Change-Making Problem Revisited, Subset Sum, Chained Matrix Multiplication.The Branch-and-Bound Paradigm
15-Puzzle, Travelling Salesperson Problem, Subset Sum.Advanced Topics
Recent choices have included Linear Programming, Text Searching and Approximate String Matching, Convex Hull Algorithms.Possible Texts