CSCE 411 Lecture 16

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 $i$^th insert is

1. $1+2^{k}$ for $i-1=2^{k}$ for some $k\geq 0$
2. 1 otherwise

Aggregate

$n$ insert operations cost

$\sum _{i=1}^{n}c_{i}\quad \leq \quad n+\sum _{j=0}^{\log {n}}2^{j}=n+(2n-1)\quad <\quad 3n$

Thus amortized cost is at most ${\frac {3n}{n}}=3$

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 $n$ represent the number of vertices and $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 $O(n)$ for sparse graphs), but requires $O(n)$ time to test adjacency

Adjacency (Incidence) Matrix

Store 0s and 1s in an $n\times n$ matrix, where $M_{ij}$ represents whether there is an edge between vertex $i$ and $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 $\Omega (n)^{2}$ space, but adjacency is $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 $d_{v}$ to the shortest path distance from the source $s$ to that vertex $v$ for all vertices is $G$.
• Sets parent pointers to form a shortest path tree (edges unweighted)

Proof by Induction. on distance values $d$

• Basis: Distance 0 when at source.
• Induction: Assume that the above theorem is true for all nodes at a distance $x-1$ (show that theorem is true for every node $v$ at distance $x$)

Since a vertex $v$ is at a distance $x$, it has at least one neighbor at distance $x-1$. Let $u$ be the first of these neighbors that is enqueued. When $u$ is dequeued, $v$ is still unvisited. When $v$ is finally visited, $d_{v}$ will be set to $d_{u}+1$. By the inductive hypothesis, $d_{u}=x-1$, so $d_{v}=x$