Duke University

Overview

Algorithms are a cornerstone of the computational sciences and the need for efficient algorithms is ubiquitous in modern technology. However, the primary goals of algorithm design, the resources that need to be optimized, and even the model of computation varies widely between application areas. In this course, we will study some of the fundamental principles of algorithm design that appear in multiple areas and have had broad impact. In addition, we will focus on the mathematical tools that are frequently used in the theoretical analysis of algorithms, and study how such analysis, in turn, influences algorithm design. The course will be at an undergraduate level.

Syllabus

Introduction

History of Algorithms

Asymptotic and Worst-case Analysis

Basic Algorithm Design Techniques

Divide and Conquer

Greedy Algorithms

Dynamic Programming

Graph Algorithms

Graph Representations

Graph Traversal and Applications

Shortest Path

Minimum Spanning Tree

Network Flows

Randomized Algorithms

Monte Carlo and Las Vegas Algorithms

Hashing

Linear Programming

Design of Linear Programs

Solving Linear Programs (basics)

Linear Programming Duality

Intractability

NP-completeness

Polynomial-time Reductions

Approximation Algorithms