CISC365/3.0 Algorithms IOriginal Author: Robin DawesLast Revised: October 16, 2006 Calendar Description 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 NPcompleteness. This knowledge is essential in all fields of computer science. The courses to which this course is a prerequisite are:
and CISC365/3.0 is recommended for CISC462/3.0 (Computability and Complexity). This course is required in BMCO, CSCI, SODE, and MAJ. TopicsComplexity of algorithms and Complexity of problems Complexity Notation, Reducibility, P, NP, and NPCompleteness, Classic NPComplete Problems, Proofs of NPCompleteness. The Divide and Conquer ParadigmQuicksort, Median Value of a Set, Closest Pair of Points. The Greedy ParadigmHuffman Coding, ChangeMaking Problem, Activity Selection, MinimumWeight Spanning Trees. The Dynamic Programming ParadigmLongest Common Subsequence, ChangeMaking Problem Revisited, Subset Sum, Chained Matrix Multiplication. The BranchandBound Paradigm15Puzzle, Travelling Salesperson Problem, Subset Sum. Advanced TopicsRecent choices have included Linear Programming, Text Searching and Approximate String Matching, Convex Hull Algorithms. Possible Texts
