CISC-365/3.0 Algorithms I

Original Author: Robin Dawes
Last 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)


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:

  • CISC-466/3.0 (Algorithms II)
  • CISC-471/3.0 (Computational Biology)
  • CISC-472/3.0 (Medical Informatics)

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.


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
  • Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms, McGraw-Hill, 2001.

  • Levitin, A.V.: Introduction to the Design and Analysis of Algorithms (2nd edition), Addison Wesley, 2006.

  • Algorithms, by Johnsonbaugh and Schaeffer, Pearson/Prentice Hall, 2004.

  • Kleinberg, J. and Tardos, E.: Algorithm Design, Addison Wesley, 2005.

  • Skiena, S.: The Algorithm Design Manual, Telos (Springer Verlag), 1998.