27:57

the subset sum problem is NP-complete

41:14

the 3-dimensional matching problem is NP-complete

28:02

the traveling salesman problem is NP-complete

40:56

the Hamiltonian cycle problem is NP-complete

43:22

circuit satisfiability is NP-complete

31:54

certification and NP-completeness

29:40

the 3-satisfiability problem is polynomial-time reducible to the independent set problem

48:27

polynomial-time reductions of independent set and vertex cover, generalizations to set cover

24:31

airline scheduling solved by circulations with demands and lower bounds, via Ford-Fulkerson

37:39

the edge-dispoint paths and survey design problems solved by the Ford-Fulkerson algorithm

34:26

determining the feasibility of circulation with demands via the Ford-Fulkerson algorithm

47:39

solving the bipartite matching problem with the Ford-Fulkerson algorithm to compute maximum flow

41:28

optimality of the Ford-Fulkerson algorithm to compute the maximum flow and the minimal cut

45:14

an iterative algorithm for maximum flow: the Ford-Fulkerson algorithm

29:21

the Bellman-Ford algorithm to compute all shortest paths in a directed graph with negative weights

39:10

dynamic programming to solve the subset sum and the knapsack problem

34:03

sequence alignment of words of size m and n runs in time O(m*n) via dynamic programming

37:45

the segmented least squares problems solved by dynamic programming in time cubic in the dimension

54:30

Greedy Algorithms and Divide-and-Conquer in the Design and Analysis of Algorithms

54:34

Representative Questions with Answers on Design and Analysis of Algorithms

30:58

principles of dynamic programming, from a memoized recursive to a direct iterative version

46:19

weighted interval scheduling solved by dynamic programming

28:14

Strassen's method to multiply two matrices runs in subcubic time

40:13

the fast Fourier transform runs in quasilinear time

38:05

closest pair computation and integer multiplication by divide and conquer algorithms

41:05

measuring disorder by counting inversions fast via a divide and conquer algorithm

32:47

data structures to implement greedy algorithms to compute minimum spanning trees

43:45

Minimum Spanning Trees of Connected Graphs by Kruskal's, Prim's and the reverse-delete algorithm

28:24

Dijkstra's algorithm to compute all shortest paths in a weighted directed graph is optimal

30:13

Farthest-in-Future is an optimal greedy algorithm for cache maintenance, via an exchange argument

29:09

An exchange argument shows that he Earliest Deadline First algorithm is an optimal greedy algorithm

44:18

Interval Scheduling and Interval Partitioning by Greedy Algorithms

42:45

Directed Graphs and Topological Orderings for Directed Acyclic Graphs

41:08

Implementing Depth-First Search and Applications to Connectivity and Bipartiteness

48:07

Implementing Graph Traversals: the Breadth-First Search Algorithm with arrays of adjacency lists

46:34

Graph Traversals: Breadth-First and Depth-First Search Algorithms

41:34

Implementing Algorithms by Selecting Data Structures, applied to the Gale-Shapley Algorithm

39:58

Properties of Asymptotic Growth of Running Times of Algorithms

41:35

Efficient Algorithm: asymptotic growth, defining big O, big Omega, big Theta

38:59

analysis of the Gale-Shapley algorithm to solve the stable matching problem

37:08

Welcome to CS 401/MCS 401, a course on computer algorithms.

16:41

computing nearest singularities and solutions of polynomial systems

44:31

Visibility Graphs to Compute the Shortest Paths for Point Robots

47:26

Quadtrees and Mesh Generation

43:33

Robot Motion Planning via Trapezoidal Maps and Minkowski Sums

42:50

Binary Space Partition Trees to solve the Hidden Surface Removal Problem

41:48

Applications of Convex Hulls to Voronoi diagrams, Delaunay triangulations and a cost analysis

45:04

A Randomized Incremental Algorithm to Compute Convex Hulls in 3-Space

34:08

Convex Hulls in Three Dimensions have a Linear Complexity in the Number of Vertices

01:00:29

Avoiding and Computing Singularities in Polynomial Homotopy Continuation

53:12

Review for the Second Midterm Exam on Computational Geometry

45:48

Segment Trees for intersecting line segments with vertical query segments

48:49

Priority Search Trees for efficient Windowing Queries on Points

39:08

Making Windowing Queries Efficient by the Construction of Interval Trees

50:46

On the expected cost of computing Delaunay triangulations

43:59

An Incremental Algorithm for Delaunay Triangulations and the Dual Graph of Voronoi Diagrams.

46:02

The Delaunay triangulation of a set of points in the plane, definition and complexity, edge flips.

37:36

The Zone Theorem shows that an incremental algorithm for a line arrangement is optimal.

45:14

Arrangement of Lines: combinatorial complexity and incremental construction

45:14

Discrepancy and Duality: the dual of counting points below a line is counting lines below a point.