Course Overview

Theoretical foundations and practical applications of algorithm analysis and design. Builds upon the data abstractions introduced in CS 2003 - Data Structures, while introducing various algorithm strategies and techniques.

Prerequisites

Students are required to have a prior background in data structures (e.g. arrays, linked lists, stacks, queues, binary trees, graphs, etc.), calculus, and discrete mathematics.

Outline

The following represents a tentative list of topics for the class.

Week	Topic	Notes
1	Course Introduction
2	Complexity Analysis
3	Heaps, Priority Queues, and Heapsort
4	Recurrences
5	Quicksort
6	Linear Time Sorts
7	Height-balanced Binary Search Trees
8	Advanced Data Structures
9	Dynamic Programming
10	Dynamic Programming (cont.)
11	Greedy Algorithms
12	Graphs and Minimum Spanning Trees
13	Single-Source Shortest Path Algorithms
14	All-Pairs Shortest Path Algorithms
15	Polynomial Time and Nondeterministic Polynomial Time
16	Final Examination

Major Course Topics

• Analysis of the complexity and asymptotic performance of algorithms
• Design and implement algorithms for problem solving
• Build algorithms using the following designs: brute force, backtracking, divide and conquer, greedy algorithms, dynamic programming, and graphs
• Construct algorithms with a focus on optimization
• Understand the trade-off between time and space

Assigned Reading

The following textbook is assigned to this course:

• Introduction to Algorithms (Third Edition) by Cormen, Leiserson, Rivest, and Stein (ISBN: 978-0-262-03384-8)

Resources

The following resources are available for students to use.

• Introduction to the Linux Command Line

Lab Work

Review the course website for more information

Examinations

The following are examinations from prior semesters: