# CS代考计算机代写 algorithm V. Adamchik Lecture 2

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?