Sign inSign in

Longest common subsequence

The problem of finding the longest subsequence that is present in two given strings in the same relative order, but not necessarily contiguous.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 3 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Lecturers

2

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    • 5:20Hardness within P
  • Erik Demaine

    MIT · Undergraduate

    The problem of finding the longest sequence that can be obtained from two given sequences by deleting zero or more elements from each without changing the relative order of the remaining elements.
    • 28:00Dynamic Programming III: Parenthesization, Edit Distance, Knapsack

Connections

8

The lectures that define it or assume it, and the concepts next to it.

Concepts5

Lectures3

2 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.