程序代写代做代考 scheme data structure algorithm AI Program Analysis

Program Analysis

Review of Priority Queues and Graphs

David Weir (U of Sussex) Program Analysis Term 1, 2017 79 / 606

Priority Queue Abstract Datatype

What does a priority queue look like?

An ordered sequence of elements

(a1, . . . ,an)

A linear data structure

a1 is the first element in the queue

an is the last element in the queue

David Weir (U of Sussex) Program Analysis Term 1, 2017 80 / 606

Priorities

What role do priorities play?

Ordering of elements is determined by the priority associated with

each element

a1 has as high a priority as any element in a1, . . . ,an

Priorities do not need to be distinct

— provide a partial ordering of elements in the queue

Priorities can change as a computation proceeds

David Weir (U of Sussex) Program Analysis Term 1, 2017 81 / 606

Issues

How might priorities be determined?

What operations are typically performed on priority queues?

How can priority queues be efficiently implemented?

David Weir (U of Sussex) Program Analysis Term 1, 2017 82 / 606

Priorities

A queue of jobs to be processed by some resource

— priority determined by importance/urgency of job

A queue of items on an agenda

— priority measures whether items are ready to be considered

David Weir (U of Sussex) Program Analysis Term 1, 2017 83 / 606

Priority Queue Operations

Find/remove element with highest priority on queue

Add new element to queue

Update priority of element on queue

Determine if queue is empty (or more generally length of queue)

Return an empty priority queue

David Weir (U of Sussex) Program Analysis Term 1, 2017 84 / 606

Implementations of Priority Queues

We will consider two alternatives:

Unsorted list implementation

Heap implementation

David Weir (U of Sussex) Program Analysis Term 1, 2017 85 / 606

Unsorted List Implementation

Elements arranged in arbitrary order

— e.g. the order in which they were added

Example:

a1 a2 a3 a4 a5 a6 a7 a8

lowest priority

element highest priority

element

last element

added

David Weir (U of Sussex) Program Analysis Term 1, 2017 86 / 606

Efficiency of Unsorted List Implementation

Suppose we have a queue containing n elements: (a1, . . . ,an)

Adding new element:

— add to end of list

— takes Θ(1) time to execute

Removing front of queue:

— requires linear search of queue

— takes Θ(n) time in worst-case

Update priority of an element:

— no reordering of elements required

— takes Θ(1) assuming constant time access to priority values

David Weir (U of Sussex) Program Analysis Term 1, 2017 87 / 606

Heap Implementation

What is a heap?

An array of values where ordering is constrained in a particular

way

A full binary tree

a1 a2 a3 a4 a5 a6 a7 a8

root of

tree left child

of root

right child

of root

leftmost grandchild

of root

David Weir (U of Sussex) Program Analysis Term 1, 2017 88 / 606

Heaps

In general:

a1 . . . ai . . . a2i a2i+1 . . . an

root of

tree

some node

within tree

left child

of ai

right child

of ai

David Weir (U of Sussex) Program Analysis Term 1, 2017 89 / 606

Heap as Tree

a1

a2

a4

a8 a9

a5

a10 a11

a3

a6

a12 a13

a7

a14 a15

David Weir (U of Sussex) Program Analysis Term 1, 2017 90 / 606

Heap Ordering

The clever idea behind heaps:

Exploits a “light-touch” ordering scheme

Goal: just ordered enough to be useful

— the highest priority element can be found quickly

— avoid unnecessarily maintaining complete orderliness

A heap is well-formed when for each i the priority of ai is as

high as the priority of its children

For all i :
priority(ai) ≥ priority(a2i)
priority(ai) ≥ priority(a2i+1)

David Weir (U of Sussex) Program Analysis Term 1, 2017 91 / 606

Example Heap

98

97

14

10 13

88

70 1

20

15

12 13

10

3 2

98 97 20 14 88 15 10 10 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

David Weir (U of Sussex) Program Analysis Term 1, 2017 92 / 606

Working with Heaps

How do we add an element to a heap?

Insert new element to end of sequence

Repeatedly swap with parent if higher priority

This is operation is called heapify

David Weir (U of Sussex) Program Analysis Term 1, 2017 93 / 606

Adding a New Element

98

97

14

10

50

13

88

70 1

20

15

12 13

10

3 2

98 97 20 14 88 15 10 10 13 70 1 12 13 3 2 50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 94 / 606

Exchange with Parent

98

97

14

50

10

13

88

70 1

20

15

12 13

10

3 2

98 97 20 14 88 15 10 50 13 70 1 12 13 3 2 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 95 / 606

Exchange with Parent

98

97

50

14

10

13

88

70 1

20

15

12 13

10

3 2

98 97 20 50 88 15 10 14 13 70 1 12 13 3 2 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 96 / 606

Running Time

How long does it take to insert an element into a heap?

The number of exchanges is bounded by the depth of the tree

The tree is a balanced binary tree so has depth log n

The running time is Θ(log n) in worst-case

Best-case running time is Θ(1)

David Weir (U of Sussex) Program Analysis Term 1, 2017 97 / 606

Removing Element from Heap

Not quite as easy as it sounds

The highest priority element is at the front of the sequence

Need to restore heap property

Insert last element in sequence at front and put down tree as

required

David Weir (U of Sussex) Program Analysis Term 1, 2017 98 / 606

Illustrative Example

98

97

50

14

10

13

88

70 1

20

15

12 13

10

3 2

98 97 20 50 88 15 10 14 13 70 1 12 13 3 2 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 99 / 606

Remove Root

97

50

14

10

13

88

70 1

20

15

12 13

10

3 2

97 20 50 88 15 10 14 13 70 1 12 13 3 2 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 100 / 606

Insert Last Element at Root

10

97

50

14 13

88

70 1

20

15

12 13

10

3 2

10 97 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 101 / 606

Compare Root with Children

10

97

50

14 13

88

70 1

20

15

12 13

10

3 2

10 97 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 102 / 606

Left Child Should be Root

10

97

50

14 13

88

70 1

20

15

12 13

10

3 2

10 97 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 103 / 606

Swop Root and Left Child

97

10

50

14 13

88

70 1

20

15

12 13

10

3 2

97 10 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 104 / 606

Compare with Children

97

10

50

14 13

88

70 1

20

15

12 13

10

3 2

97 10 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 105 / 606

Right Child Should Move Up

97

10

50

14 13

88

70 1

20

15

12 13

10

3 2

97 10 20 50 88 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 106 / 606

Swop Nodes

97

88

50

14 13

10

70 1

20

15

12 13

10

3 2

97 88 20 50 10 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 107 / 606

Compare with Children

97

88

50

14 13

10

70 1

20

15

12 13

10

3 2

97 88 20 50 10 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 108 / 606

Left Child Should Move Up

97

88

50

14 13

10

70 1

20

15

12 13

10

3 2

97 88 20 50 10 15 10 14 13 70 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 109 / 606

Swop Nodes

97

88

50

14 13

70

10 1

20

15

12 13

10

3 2

97 88 20 50 70 15 10 14 13 10 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 110 / 606

Restored the Heap

97

88

50

14 13

70

10 1

20

15

12 13

10

3 2

97 88 20 50 70 15 10 14 13 10 1 12 13 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

David Weir (U of Sussex) Program Analysis Term 1, 2017 111 / 606

A Heap for you to restore

68 90 57 59 75 30 22 43 10 16 20 13 17 2 21

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Show the heap as a tree

David Weir (U of Sussex) Program Analysis Term 1, 2017 112 / 606

A Heap for you to restore

68 90 57 59 75 30 22 43 10 16 20 13 17 2 21

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Show the heap as a tree

90

68

57

22 43

59

10 16

75

21

20 13

30

17 2

David Weir (U of Sussex) Program Analysis Term 1, 2017 112 / 606

Running Time

How Long Does This Take?

Worst-case bounded by depth of tree, so Θ(log n)

Best-case Θ(1)

David Weir (U of Sussex) Program Analysis Term 1, 2017 113 / 606

Building a Heap from Scratch

Two approaches:

Straightforward approach:

— repeatedly insert new elements

— each insertion takes O(log n) time
— total running time is O(n log n)

More efficient alternative:

— create heap bottom-up

David Weir (U of Sussex) Program Analysis Term 1, 2017 114 / 606

Bottom-up Heap Construction

Consider nodes in order of increasing height in tree

Height of a node is length of longest path to leaf node

Restore heap for subtree rooted at node being considered

— through required exchanges with highest priority child

David Weir (U of Sussex) Program Analysis Term 1, 2017 115 / 606

Heapification Order

44

32

37

94 25

75

48 19

65

15

58 72

29

23 11

44 32 65 37 75 15 29 94 25 48 19 58 72 23 11

height 3 2 2 1 1 1 1 0 0 0 0 0 0 0 0

David Weir (U of Sussex) Program Analysis Term 1, 2017 116 / 606

Analysis of Running Time

For each node, processing time for node of height

O(h)

Number of nodes of height h


⌈ n

2h+1

David Weir (U of Sussex) Program Analysis Term 1, 2017 117 / 606

Total Running Time

⌈log n⌉

h=0

n

2h+1
O(h) =

1

2
n

⌈log n⌉

h=0

1

2h
O(h)

= O

n

⌈log n⌉

h=0

h

2h

= O(n)

note that


h=0

h

2h
converges to 2

David Weir (U of Sussex) Program Analysis Term 1, 2017 118 / 606

Review of Graphs

David Weir (U of Sussex) Program Analysis Term 1, 2017 119 / 606

Graphs

A general purpose data structure

Need not be linear like a list, but could be

Need not be hierarchical like a tree, but could be

Can express arbitrary binary relationship between a collection of

elements

Strength of relationship can be encoded using weights

David Weir (U of Sussex) Program Analysis Term 1, 2017 120 / 606

Graphs: Examining an Example

Let’s look at an example graph

v1

v2

v3

v4

v5

v6

v7

v8

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

There are 8 vertices or nodes

v1

v2

v3

v4

v5

v6

v7

v8

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

Use n to refer to the number of nodes — so n = 8

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

Use V to refer to the set of all nodes — so V = {v1, . . . , v8}

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

There are 10 edges

v1

v2

v3

v4

v5

v6

v7

v8

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

Each edge denoted by a set of two vertices

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

For example: {v5, v7}

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

Use m to refer to the number of edges — so m = 10

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

Use E to refer to the set of all edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

E = {{v1, v2}, {v1, v3}, {v2, v3}, {v2, v5}, {v3, v6},
{v4, v6}, {v4, v7}, {v5, v7}, {v5, v8}, {v6, v8}}

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

Use G to refer to the graph — so G = (V ,E)

v1

v2

v3

v4

v5

v6

v7

v8

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1

v2

v3

v4

v5

v6

v7

v8

The layout of the graph is unimportant

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

Graphs: Examining an Example

v1v2

v3v4

v5

v6

v7v8

This is the same graph

David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606

What Are Graphs Good For?

Expressing all sorts of binary relationships

Transport networks
◮ node: a place
◮ edge: route connecting two places

Communication networks
◮ node: computer cluster
◮ edge: communication link between two clusters

David Weir (U of Sussex) Program Analysis Term 1, 2017 122 / 606

What Are Graphs Good For?

Information networks
◮ node: web page
◮ edge: hyperlink from one page to another

Social networks
◮ node: person
◮ edge: some sort of relationship between two people

Dependency networks
◮ node: task to be performed
◮ edge: dependency between two tasks

And much much more

David Weir (U of Sussex) Program Analysis Term 1, 2017 123 / 606

Directed Graphs

v1v2

v3v4

v5

v6

v7v8

Sometimes relationships are directional

David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606

Directed Graphs

v1v2

v3v4

v5

v6

v7v8

Capture this with directional edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606

Directed Graphs

v1v2

v3v4

v5

v6

v7v8

This is called a directed graph

David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606

Directed Graphs

v1v2

v3v4

v5

v6

v7v8

E is now a set of directed pairs

David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606

Directed Graphs

v1v2

v3v4

v5

v6

v7v8

E = {(v1, v2), (v3, v1), (v2, v3), (v2, v5), (v6, v3),
(v4, v6), (v7, v4), (v5, v7), (v8, v5), (v6, v8)}

David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606

Directed Acyclic Graphs

v1v2

v3v4

v5

v6

v7v8

Important special case: directed acyclic graphs or DAGs

David Weir (U of Sussex) Program Analysis Term 1, 2017 125 / 606

Weighted Graphs

v1v2

v3v4

v5

v6

v7v8

Sometimes want to associate weights with edges – e.g. distance

David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606

Weighted Graphs

v1v2

v3v4

v5

v6

v7v8

Capture this with weighted edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606

Weighted Graphs

v1v2

v3v4

v5

v6

v7v8

15

2
40

8

11

1429

41 33
6

This is called a weighted graph

David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606

Trees: A Special Kind of Graph

v1v2

v3v4

v5

v6

v7v8

Let’s remove these edges to give a tree

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3v4

v5

v6

v7v8

How can we tell that its a tree?

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3v4

v5

v6

v7v8

Let’s pick it up by v8

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

What happens if we put back the edges we removed

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Adding that one creates a cycle

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Adding that one also creates a cycle

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Guess what!

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Fact 1: there are no cycles

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Fact 2: its connected, i.e. path between any pair of nodes

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

Fact 3: n nodes and n − 1 edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Trees: A Special Kind of Graph

v1v2

v3 v4

v5 v6

v7

v8

. . . and that’s what makes it a tree

David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606

Graphs: Implementation

Question: What data structure can we use to store a graph?

Answer: There are two alternatives:

Adjacency matrix

Adjacency list

David Weir (U of Sussex) Program Analysis Term 1, 2017 128 / 606

Adjacency Matrix Representation

Adjacency matrix for undirected graph shown earlier

v1 v2 v3 v4 v5 v6 v7 v8
v1 0 1 1 0 0 0 0 0

v2 1 0 1 0 1 0 0 0

v3 1 1 0 0 0 1 0 0

v4 0 0 0 0 0 1 1 0

v5 0 1 0 0 0 0 1 1

v6 0 0 1 1 0 0 0 1

v7 0 0 0 1 1 0 0 0

v8 0 0 0 0 1 1 0 0

Entry value in (i , j) same as value in (j , i) for undirected graph

David Weir (U of Sussex) Program Analysis Term 1, 2017 129 / 606

Adjacency Matrix Representation

Adjacency matrix for directed graph shown earlier

v1 v2 v3 v4 v5 v6 v7 v8
v1 0 1 0 0 0 0 0 0

v2 0 0 1 0 1 0 0 0

v3 1 0 0 0 0 0 0 0

v4 0 0 0 0 0 0 0 0

v5 0 0 0 0 0 0 1 0

v6 0 0 1 1 0 0 0 1

v7 0 0 0 1 0 0 0 0

v8 0 0 0 0 1 0 0 0

David Weir (U of Sussex) Program Analysis Term 1, 2017 130 / 606

Adjacency Matrix Representation (cont.)

Two issues worth considering:

Space efficiency of adjacency matrix representation

Running time of basic operations of adjacency matrix

representation

David Weir (U of Sussex) Program Analysis Term 1, 2017 131 / 606

Space Efficiency of Adjacency Matrix Representation

Given a graph G = (V ,E) where |V | = n and |E | = m

Question: How much space used to store G?

Answer: Θ(n2)

Doesn’t matter how many edges there are

i.e. its not a function of m

Inefficient for graphs without many edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 132 / 606

Time Efficienty of Matrix Representation

First, the good news:

It takes Θ(1) to determine if there’s an edge between two nodes

The not so good news:

It takes Θ(n) to find all nodes adjacent to some node

Even if there aren’t any adjacent nodes it still takes Θ(n) to
discover this

Common for an algorithm to need to enumerate adjacent nodes

Desirable that finding next node in enumeration take constant time

David Weir (U of Sussex) Program Analysis Term 1, 2017 133 / 606

Adjacency List Representation

v8

v7

v6

v5

v4

v3

v2

v1 v2 v3

v1 v4 v5

v1 v2 v6

v6 v7

v2 v7 v8

v3 v4 v8

v4 v5

v5 v6

David Weir (U of Sussex) Program Analysis Term 1, 2017 134 / 606

Adjacency List Representation Features

Same two issues need to be considered:

Space efficiency of adjacency list representation

Running time of basic operations of adjacency list representation

David Weir (U of Sussex) Program Analysis Term 1, 2017 135 / 606

Space Efficiency of Adjacency List Representation

Given a graph G = (V ,E) where |V | = n and |E | = m

Question: How much space used to store G?

Answer: Θ(m)

More efficient than adjacency matrix for graphs without many edges

David Weir (U of Sussex) Program Analysis Term 1, 2017 136 / 606

Time Efficiency of Adjacency List Representation

First the good news:

Enumeration of adjacent nodes Θ(1) per adjacent node

Not so good news:

Takes O(n) to establish if a particular edge is in graph

Linear search of adjacency list

Adjacency list length is O(n)

For most of the algorithms we consider here, the adjacency list

implementation is preferable.

David Weir (U of Sussex) Program Analysis Term 1, 2017 137 / 606

Vertices and Edges

Let G = (V ,E) be a graph where |V | = n and |E | = m

Question: What can we say about |E | in terms of |V |?

How few edges could there be?

Possible that E could be empty, i.e. m = 0

If G is connected then m ≥ n − 1

How many edges could there be?

If G is a complete graph then m = n(n − 1)/2 which is Θ(n2)

So, in general, m is O(n2)

David Weir (U of Sussex) Program Analysis Term 1, 2017 138 / 606

Questions for you

Give adjacency list and adjacency matrix encodings of this graph

Which uses the least space?

If this was a complete graph, how many edges would it have?

v1

v2

v3

v4

v5

v6

v7

David Weir (U of Sussex) Program Analysis Term 1, 2017 139 / 606

Questions for you

Give adjacency list and adjacency matrix encodings of this graph

Which uses the least space?

Adjacency list uses less memory

If this was a complete graph, how many edges would it have?

21

v1

v2

v3

v4

v5

v6

v7

David Weir (U of Sussex) Program Analysis Term 1, 2017 139 / 606