WILLIAM T. DOAN


The notes herewith are derived from the lecture notes of Dr. Ding-Zhu Du as presented in his CS 6363: Design and Analysis of Computer Algorithms course given in the Spring semester of 2026. The textbook for this course is Introduction to Algorithms (3rd edition) by T.H. Corman, C.E. Leiserson, R.L. Rivest and C. Stein.

Table of Contents

  1. Algorithms with Self-Reduction
    1. Sorting and Divide and Conquer
      1. Introduction
      2. Sorting
      3. Sorting and Selection
      4. Divide and Conquer
    2. Shortest Path and Dynamic Programming
      1. Dynamic Programming
      2. Shortest Path
      3. Dijkstra's Algorithm
      4. Priority-Queues and an Implementation of Dijkstra's Algorithm
      5. All Pairs Shortest Paths
    3. Minimum Spanning Tree and Greedy Algorithms
      1. The Greedy Strategy
      2. Spanning Trees
      3. Matroids
      4. Self-Reducibility
  2. The Incremental Method
    1. Network Flows and the Incremental Method
      1. The Ford-Fulkerson Method
      2. The Edmonds-Karp Algorithm
      3. Maximum Matchings
      4. Pre-flow Pushing
      5. Minimum Cost Flows
  3. Complexity and Approximation
    1. NP-hard Problems and Approximation Algorithms
      1. What is NP?
      2. NP-Complete Problems
      3. Vertex Cover and the Hamiltonian Cycle
      4. The Partition and Knapsack Problems
      5. 3D-Matching and Set Cover
      6. Planar 3SAT
    2. Linear Programming and the Primal-Dual Method
      1. Linear Programming
      2. The Primal-Dual Method
      3. Label Correcting

Algorithms with Self-Reduction

Sorting and Divide and Conquer

Introduction

Sorting

Sorting and Selection

Divide and Conquer

Shortest Path and Dynamic Programming

Dynamic Programming

Shortest Path

Dijkstra's Algorithm

Priority-Queues and an Implementation of Dijkstra's Algorithm

All Pairs Shortest Paths

Minimum Spanning Tree and Greedy Algorithms

The Greedy Strategy

Spanning Trees

Matroids

Self-Reducibility

The Incremental Method

Network Flows and the Incremental Method

The Ford-Fulkerson Method

The Edmonds-Karp Algorithm

Maximum Matchings

Pre-flow Pushing

Minimum Cost Flows

Complexity and Approximation

NP-hard Problems and Approximation Algorithms

What is NP?

NP-Complete Problems

Vertex Cover and the Hamiltonian Cycle

The Partition and Knapsack Problems

3D-Matching and Set Cover

Planar 3SAT

Linear Programming and the Primal-Dual Method

Linear Programming

The Primal-Dual Method

Label Correcting