CSCE 411 Lecture 16

From Notes
Jump to navigation Jump to search
Lecture Slides

« previous | Monday, October 1, 2012 | next »

Late to class from West Campus POLS 207 Office Hours

Amortized Analysis of Doubling Table

Double size of table whenever it's about to overflow.

Cost of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} th insert is

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + 2^k} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i-1 = 2^k} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\ge 0}
  2. 1 otherwise

Aggregate

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} insert operations cost

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n c_i \quad \le \quad n + \sum_{j=0}^{\log{n}} 2^j = n + (2n-1) \quad < \quad 3n}

Thus amortized cost is at most

Accounting

Charge $3 for each operation, where the operation actually costs $1.

Assume after growing the table, all previous elements have already paid their dues and no money is left over. (like social security for data structures). Each element in the new half of the array has to pay for

  1. its own insertion,
  2. its future move, and
  3. the move of one other element in the old half.

Graph Algorithms

A graph consists of vertices that are connected by edges

Assume the edges are undirected

We say two vertices are adjacent when they are connected by an edge.

Representations

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} represent the number of vertices and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} represent the number of edges.

Adjacency List

Bucket list for each vertex; contains a list of adjacent vertices

a → b c
b → a d e
c → a d
d → b c e
e → b d

Space efficient (just Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} for sparse graphs), but requires Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} time to test adjacency

Adjacency (Incidence) Matrix

Store 0s and 1s in an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times n} matrix, where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_{ij}} represents whether there is an edge between vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j}

The same graph above would be represented by the following adjacency matrix:

  a b c d e
a 0 1 1 0 0
b 1 0 0 1 1
c 1 0 0 1 0
d 0 1 1 0 1
e 0 1 0 1 0

Requires Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(n)^2} space, but adjacency is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} .

Graph Traversals

Breadth First Search (BFS)

def breadth_first_search graph, source
  graph.nodes.each do |v|
    v.visited = false
  end

  q = Queue.new   # FIFO structure
  source.visited = true
  q.enqueue source

  until q.empty? do
    u = q.dequeue
    u.neighbors.select{|v| not v.visited?}.each do |v|
      v.visited = true
      q.enqueue v
    end
  end
end

We can make a spanning tree rooted at the source vertex by remembering the parent of each visited vertex: 

def bfs_tree graph, source
  graph.nodes.each do |v|
    v.visited = false
    v.parent = nil              #!
  end

  q = Queue.new
  source.visited = true
  source.parent = source        #!
  q.enqueue source

  until q.empty? do
    u = q.dequeue
    u.neighbors.select{|v| not v.visited?}.each do |v|
      v.visited = true
      v.parent = u              #!
      q.enqueue v
    end
  end
end

This tree is not necessarily unique for a graph (depends on order in which neighboring nodes are processed. Another useful thing we can do is remember the distance from the source node to another node (essentially its height on the BFS spanning tree) 

def bfs_distance graph, source
  graph.nodes.each do |v|
    v.visited = false
    v.distance = Float::INFINITY        #!
    v.parent = nil
  end

  q = Queue.new
  source.visited = true
  source.parent = source
  source.distance = 0                   #!
  q.enqueue source

  until q.empty? do
    u = q.dequeue
    u.neighbors.select{|v| not v.visited?}.each do |v|
      v.visited = true
      v.parent = u
      v.distance = u.distance + 1       #!
      q.enqueue v
    end
  end
end
BFS Theorem

The BFS algorithm:

  • visits all and only vertices reachable from the source.
  • sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_v} to the shortest path distance from the source Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} to that vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} for all vertices is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .
  • Sets parent pointers to form a shortest path tree (edges unweighted)

Proof by Induction. on distance values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d}

  • Basis: Distance 0 when at source.
  • Induction: Assume that the above theorem is true for all nodes at a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x-1} (show that theorem is true for every node Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} at distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} )

Since a vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is at a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , it has at least one neighbor at distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x-1} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} be the first of these neighbors that is enqueued. When Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} is dequeued, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is still unvisited. When Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is finally visited, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_v} will be set to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_u + 1} . By the inductive hypothesis, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_u = x-1} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_v = x}

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_411_Lecture_16&oldid=3290"