Data Structures Lesson 17

Professor Abdul-Quader

Topological Sorting

Presentations

P vs NP

  • Formally: a problem is in the class P if there is an algorithm which, for any input of length \(n\), runs in polynomial time in terms of \(n\):

    \[P = \bigcup\limits_{i = 0}^{\infty} O(n^i)\]

  • These are easy to solve.

Class NP

  • A problem is in NP if there is an algorithm which checks a solution in polynomial time. (easy to check)
  • Example: composites. Given a number \(x\) of length \(N\) (in binary), determine if \(x\) is composite.
  • Verifier: on input \(x\) and \(c\), check if \(c | x\) (can be done in polynomial time in \(N\)). If so, output true. If not false.
  • Solver? On input \(x\), determine if any \(c\) divides \(x\)?
    • Naive: exponential in the length of \(x\). Why?

Examples

  1. Given a representationn (adjacency matrix or list) of a graph \(G = (V, E)\) and an assignment of colors to the vertices, check if it is a valid coloring.
  2. The Eulerian path/cycle problem is in P. (The algorithm we talked about is a proof of this fact.)
  3. Hamiltonian cycle problem? TSP?
  4. Non-Hamiltonian cycle? Give a graph \(G = (V, E)\), determine if the graph does not have a Hamiltonian cycle.

P vs NP

In the year 2000, the Clay Mathematics Institute posed a list a 7 Millenium problems, offering a $1M cash prize for a solution to any of these. The P vs NP question is one of them:

Problem: Prove or disprove that every problem in NP is also in P.

NP-Completeness

  • NP-complete: problems which, if solved, can be used to solve (in polynomial time) any other problem in the class NP.
  • Not obvious that such problems exist!
  • Examples:
    • Hamiltonian circuit problem
    • Traveling Salesman Problem
    • Graph Coloring problem

Not known

Many other problems are known to be in NP, but not known to be NP-complete:

  • Integer factorization,
  • Discrete logarithm (both of these are used in encryption algorithms)
  • Graph isomorphism
  • …

Simulation

(If time) Let’s go back to the RandomGraph from last time:

  • Implement the hasAPath method. How?
  • Play around with different values of \(p\) and \(size\).
  • Check if your implementation works correctly by calling printGraph (and checking by hand if there is a path).

Simulation

  • Implement the simulate method and play around with \(size\) and \(prob\):
  • If \(p = 0.5\), for what values of \(size\) will the probability of a path be at least \(90\%\)?
  • If \(p = 0.25\), same question.
  • If \(p = 0.001\), for what values of \(size\) will the probability of a path be at least \(50\%\)?

Sorting

Sorting problem: given an array of integers, re-arrange the elements to be in increasing order.

CS2:

  • Bubble Sort
  • Merge Sort

Remember these?

Bubble Sort

  • Repeatedly compare consecutive elements, moving the bigger one to the right.
  • Pseudocode?
  • Running time?

Selection Sort

  • for each \(i\), repeatedly search for the smallest element in the list in between positions \(i\) and \(n - 1\), and swap it with the element at position \(i\).
  • Pseudocode?
  • Running time?

Insertion sort

  • Keep the beginning of the list (first \(i\) elements) sorted, and then figure out where the element \(a_{i+1}\) goes.
  • Pseudocode?
  • Running time?

Video

Merge Sort

Recursive algorithm:

procedure mergesort(array, tmpArray, left, right):
    if (left >= right) return
    mid = (left + right)  / 2
    mergesort(array, tmpArray, left, mid)
    mergesort(array, tmpArray, mid + 1, right)
    merge(array, tmpArray, left, mid + 1, right)

How do we implement the merge algorithm? (This is why we have a tmpArray)

Analysis

  1. How many comparisons does this algorithm make for an array of size \(4\)? How many would the insertion sort algorithm make?
  2. What is the worst case running time of this algorithm? Average case?
  3. A sorting algorithm is called stable if whenever multiple elements of the input array are equal, they are left in their original order. Is this algorithm stable?
  4. What is the space complexity of this algorithm?

Upcoming

  • Quiz 2 (now)
  • HW 3 due Friday
  • Project 3 will be posted soon.
  • Final project (group project).

Remaining topics

  • Sorting (2 weeks)
  • Greedy and on-line algorithms
  • Dynamic programming
  • Concurrency and concurrent data structures (1.5 weeks)
  • Java miscellany

Quiz