Course Description

Algorithms for solving problems that occur frequently in computer applications. Basic principles and techniques for designing and analyzing algorithms. Prerequisites: CS 2010 and MATH 2220 or equivalent.

Course Syllabus

1. Basic Concepts
   1. Order of an Algorithm
   2. Worst Case Analysis
   3. Average Case Analysis
   4. Optimality of Algorithms
2. Sorting
   1. Lower Bounds for Sorting
   2. Sorting Methods and their Analysis
      (Bubble sort, Insertion Sort, Quicksort, Mergesort, Heapsort, Shellsort, External Sorting)
3. Graphs and Digraphs
   1. Minimal Spanning Trees
   2. Shortest Path Algorithms
   3. Traversing Graphs and Digraphs
4. Optimal Binary Search Trees
5. String Matching (KMP Algorithm)
6. Polynomials and Matrices
   1. Evaluating Polynomial Functions (Horner's Method)
   2. Matrix Multiplication (Strassen's Algorithm)
7. NP-Complete Problems and Approximation Algorithms
   1. Definition and Motivation
   2. Polynomial Reducibility
   3. Approximation Algorithms
      1. First Fit Bin Packing
      2. Knapsack Problem
8. Dynamic Programming
9. Parallel Algorithms

During the term, the Divide-and-Conquer strategy is introduced by using several examples including quicksort, mergesort, binary search, finding the maximum and minimum, and Strassen's matrix multiplication.

The Greedy Method is also discussed and used for solving some problems such as optimal storage on tapes, knapsack problem, job sequencing with deadlines, minimal spanning trees, and single source shortest paths.

Course Requirements

1. Homework Assignments:
   A number of homework assignments will be given during the semester. Some of the problems may require programming in a high-level language.
2. Programming Assignment:
   One or two programming projects will be assigned during the semester.