V. Adamchik Lecture 2
Analysis of Algorithms
University of Southern California
Review Amortized Cost
Reading: chapters 1 & 2
CSCI 570

Ch1: review questions

Ch1: exercises

Topological Sort for DAG
Suppose each vertex represents a task that must
be completed, and a directed edge (u, v) indicates that task
v depends on task u. That is task u must be completed before v. The topological ordering of the vertices is a valid order in which you can complete the tasks.
ABD CE
F

How to find a topological order?
ABD CE
F

Linear Time Algorithm
ABD CE
• Select a vertex.
F
• Run DFS and return vertices that has no undiscovered leaving edges
• May run DFS several times
We get vertices in reverse order. Why is it linear time?

Discussion Problem 1
We have discussed finding the shortest path between two vertices in a graph. Suppose instead we are interested in finding the longest path in a directed acyclic graph (DAG). In particular, we are interested in a path that visits all vertices. Give a linear-time algorithm to determine if such a path exist.
ABD CE
F

Strongly Connected Graphs
Given a directed graph. It’s strongly connected if each vertex is reachable from any other vertex.
If we reverse the edge (3,4), it won’t be strongly connected.
It’s called a weakly connected graph.
34
15 2
How do you test if a graph is strongly connected?

Strongly Connected Graphs
4
1
2
3
5

Planar Graphs
A graph is planar if it can be drawn in the plane
=
A planar graph when drawn in the plane, splits the plane into disjoint faces.
without crossing edges
4 faces

Euler’s Formula
Theorem. If G is a connected planar graph with V vertices, E edges and F faces, then V – E + F = 2.

Proof of Euler’s Formula

Coloring Planar Graphs
A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same color

4 Color Theorem (1976) Theorem: Any simple planar graph can be
colored with less than or equal to 4 colors.
It was proven in 1976 by K. Appel and W. Haken.
They used a special-purpose computer program.
Since that time computer scientists have been working on developing a formal program proof of correctness. The idea is to write code that describes not only what the machine should do, but also why it should be doing it.
In 2005 such a proof has been developed by Gonthier, using the Coq logical proof system.

Theorem. Any simple planar graph can be colored with 6 colors.

Amortized Analysis
In a sequence of operations the worst case does not occur often in each operation – some operations may be cheap, some may be expensive.
Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound.
When same operation takes different times, how can we accurately calculate the runtime complexity?

The Aggregate Method
The aggregate method computes the upper bound T(n) on the total cost of n operations.
The amortized cost of an operation is given by 𝑇(𝑛) 𝑛
In this method each operation will get the same
amortized cost, even if there are several types of operations in the sequence.

Unbounded Array

Unbounded Array

Binary Counter
Given a binary number n with log(n) bits, stored as an array, where each entry A[i] stores the i-th bit.
The cost of incrementing a binary number is the number of bits flipped.

Binary Counter

Discussion Problem 2
Another Binary Counter. Let us assume that the cost of a flip is 2k to flip k-th bit. Flipping the lowest-order bit costs 20 = 1, the next bit costs 21 = 2, and so on. What is the amortized cost per increment? Use the aggregate method.

The Accounting Method
The accounting method (or the banker’s method) computes the individual cost of each operation.
We assign different charges to each operation; some operations may charge more or less than they actually cost.
The amount we charge an operation is called its amortized cost.

Discussion Problem 3
You have a stack data type, and you need to implement a FIFO queue. The stack has the usual POP and PUSH operations, and the cost of each operation is 1. The FIFO has two operations: ENQUEUE and DEQUEUE.
We can implement a FIFO queue using two stacks. What is the amortized cost of ENQUEUE and DEQUEUE operations?

V. Adamchik Lecture 2
Analysis of Algorithms
University of Southern California
Review Amortized Cost
Reading: chapters 1 & 2
CSCI 570

Ch1: review questions

Ch1: exercises

Topological Sort for DAG
Suppose each vertex represents a task that must
be completed, and a directed edge (u, v) indicates that task
v depends on task u. That is task u must be completed before v. The topological ordering of the vertices is a valid order in which you can complete the tasks.
ABD CE
F

How to find a topological order?
ABD CE
F

Linear Time Algorithm
ABD CE
• Select a vertex.
F
• Run DFS and return vertices that has no undiscovered leaving edges
• May run DFS several times
We get vertices in reverse order. Why is it linear time?

Discussion Problem 1
We have discussed finding the shortest path between two vertices in a graph. Suppose instead we are interested in finding the longest path in a directed acyclic graph (DAG). In particular, we are interested in a path that visits all vertices. Give a linear-time algorithm to determine if such a path exist.
ABD CE
F

Strongly Connected Graphs
Given a directed graph. It’s strongly connected if each vertex is reachable from any other vertex.
If we reverse the edge (3,4), it won’t be strongly connected.
It’s called a weakly connected graph.
34
15 2
How do you test if a graph is strongly connected?

Strongly Connected Graphs
4
1
2
3
5

Planar Graphs
A graph is planar if it can be drawn in the plane
=
A planar graph when drawn in the plane, splits the plane into disjoint faces.
without crossing edges
4 faces

Euler’s Formula
Theorem. If G is a connected planar graph with V vertices, E edges and F faces, then V – E + F = 2.

Proof of Euler’s Formula

Coloring Planar Graphs
A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same color

4 Color Theorem (1976) Theorem: Any simple planar graph can be
colored with less than or equal to 4 colors.
It was proven in 1976 by K. Appel and W. Haken.
They used a special-purpose computer program.
Since that time computer scientists have been working on developing a formal program proof of correctness. The idea is to write code that describes not only what the machine should do, but also why it should be doing it.
In 2005 such a proof has been developed by Gonthier, using the Coq logical proof system.

Theorem. Any simple planar graph can be colored with 6 colors.

Amortized Analysis
In a sequence of operations the worst case does not occur often in each operation – some operations may be cheap, some may be expensive.
Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound.
When same operation takes different times, how can we accurately calculate the runtime complexity?

The Aggregate Method
The aggregate method computes the upper bound T(n) on the total cost of n operations.
The amortized cost of an operation is given by 𝑇(𝑛) 𝑛
In this method each operation will get the same
amortized cost, even if there are several types of operations in the sequence.

Unbounded Array

Unbounded Array

Binary Counter
Given a binary number n with log(n) bits, stored as an array, where each entry A[i] stores the i-th bit.
The cost of incrementing a binary number is the number of bits flipped.

Binary Counter

Discussion Problem 2
Another Binary Counter. Let us assume that the cost of a flip is 2k to flip k-th bit. Flipping the lowest-order bit costs 20 = 1, the next bit costs 21 = 2, and so on. What is the amortized cost per increment? Use the aggregate method.

The Accounting Method
The accounting method (or the banker’s method) computes the individual cost of each operation.
We assign different charges to each operation; some operations may charge more or less than they actually cost.
The amount we charge an operation is called its amortized cost.

Discussion Problem 3
You have a stack data type, and you need to implement a FIFO queue. The stack has the usual POP and PUSH operations, and the cost of each operation is 1. The FIFO has two operations: ENQUEUE and DEQUEUE.
We can implement a FIFO queue using two stacks. What is the amortized cost of ENQUEUE and DEQUEUE operations?