1 of 107

Graphs, Heaps, Midterm 2 Review

Discussion 09

CS 61B Fall 2022

2 of 107

Announcements

Week 8 Survey due 11:59 PM Monday 10/17
No Lab this Week!
Homework 3 due 11:59 PM Tuesday, 10/18
Midterm 2 is Thursday, 10/20 7-9 pm

CS 61B Fall 2022

3 of 107

Content Review

CS 61B Fall 2022

4 of 107

Trees, Revisited (and Formally Defined)

Trees are structures that follow a few basic rules:

If there are N nodes, there are N-1 edges
There is exactly 1 path from every node to every other node
The above two rules means that trees are fully connected and contain no cycles

A parent node points towards its child.

The root of a tree is a node with no parent nodes.

A leaf of a tree is a node with no child nodes.

CS 61B Fall 2022

5 of 107

Graphs

Trees are a specific kind of graph, which is more generally defined as below:

Graphs allow cycles
Simple graphs don’t allow parallel edges (2 or more edges connecting the same two nodes) or self edges (an edge from a vertex to itself)
Graphs may be directed or undirected (arrows vs. no arrows on edges)

Check! How would you describe each of these graphs (in terms of directedness and cycles)?

CS 61B Fall 2022

6 of 107

Graph Representations

Adjacency lists list out all the nodes connected to each node in our graph:

A

B

C

D

E

F

A	B , C
B	E
C	F
D	B
E
F	D

CS 61B Fall 2022

7 of 107

Graph Representations

Adjacency matrices are true if there is a line going from node A to B and false otherwise.

A

B

C

D

E

F

	A	B	C	D	E	F
A	0	1	1	0	0	0
B	0	0	0	0	1	0
C	0	0	0	0	0	1
D	0	1	0	0	0	0
E	0	0	0	0	0	0
F	0	0	0	1	0	0

CS 61B Fall 2022

8 of 107

Breadth First Search

Breadth first search means visiting nodes based off of their distance to the source, or starting point. For trees, this means visiting the nodes of a tree level by level. Breadth first search is one way of traversing a graph.

BFS is usually done using a queue.

A

B

C

D

E

BFS(G):

Add G.root to queue

While queue not empty:

Pop node from front of queue and process

for each immediate neighbor of node:

Add neighbor to queue if not

already processed

CS 61B Fall 2022

9 of 107

Depth First Search

Depth First Search means we visit each subtree (subgraph) in some order recursively.

DFS is usually done using a stack. Note that for graphs more generally, it doesn’t really make sense to do in-order traversals.

Post-order traversals visit the child nodes before visiting the parent nodes

In-order traversals visit the left child, then the parent, then the right child.

Pre-order traversals visit the parent node before visiting child nodes.

A

B

E

C

D

B

E

A

C

E

C

D

A

B

CS 61B Fall 2022

10 of 107

General Graph DFS Pseudocode

A

B

C

D

E

F

DFSPreorder(G):

process G.root

for each immediate neighbor of G.root:

Add neighbor to top of stack

DFSPreorder(neighbor)

Pop from top of stack

DFSPostorder(G):

for each immediate neighbor of G.root:

Add neighbor to top of stack

DFSPostorder(neighbor)

process G.root

Pop from top of stack

“Process the node as soon as it enters the stack: myself, then all my children”

“Process the node as soon as it leaves the stack: all my children, then myself”

* in-order for binary trees:

DFSInorder(T):

DFSInorder(T.left)

process T.root

DFSInorder(T.right)

“Process my left child, then myself,

Then my right child”

CS 61B // Spring 2022

11 of 107

Heaps

Heaps are special trees that follow a few basic rules:

Heaps are complete - the only empty parts of a heap are in the bottom row, to the right
In a min-heap, each node must be smaller than all of its child nodes. The opposite is true for max-heaps.

0

5

1

7

8

2

Check! What makes a binary min-heap different from a binary search tree?

CS 61B Fall 2022

12 of 107

Heap Representation

We can represent binary heaps as arrays with the following setup:

The root is stored at index 1 (not 0 - see points 2 and 3 for why)
The left child of a binary heap node at index i is stored at index 2i
The right child of a binary heap node at index i is stored at index 2i + 1

0

5

1

7

8

2

[-, 0, 5, 1, 7, 8, 2]

Check! What kind of graph traversal does the ordering of the elements in the array look like starting from the root at index 1?

CS 61B Fall 2022

13 of 107

Insertion into (Min-)Heaps

0

5

1

7

8

2

-1

0

5

-1

7

8

2

1

-1

5

0

7

8

2

1

We insert elements into the next available spot in the heap and bubble up as necessary: if a node is smaller than its parent, they will swap. (Check: what changes if this is a max heap?)

CS 61B Fall 2022

14 of 107

Root Deletion from (Min-)Heaps

0

5

1

7

8

2

4

5

1

7

8

2

1

5

4

7

8

2

1

5

2

7

8

4

We swap the last element with the root and bubble down as necessary: if a node is greater than its children, it will swap with the lesser of its children. (Check: what changes if this is a max heap?)

CS 61B Fall 2022

15 of 107

16 of 107

Worksheet

CS 61B Fall 2022

17 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder:

BFS:

Stack:

CS 61B Fall 2022

18 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder:

BFS:

Stack: 10

CS 61B Fall 2022

19 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder:

BFS:

Stack: 10 3

CS 61B Fall 2022

20 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder:

BFS:

Stack: 10 3 1

CS 61B Fall 2022

21 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1

BFS:

Stack: 10 3

CS 61B Fall 2022

22 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3

BFS:

Stack: 10

CS 61B Fall 2022

23 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3

BFS:

Stack: 10 7

CS 61B Fall 2022

24 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7

BFS:

Stack: 10

CS 61B Fall 2022

25 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10

BFS:

Stack:

CS 61B Fall 2022

26 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10

BFS:

Stack: 12

CS 61B Fall 2022

27 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10

BFS:

Stack: 12 11

CS 61B Fall 2022

28 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11

BFS:

Stack: 12

CS 61B Fall 2022

29 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12

BFS:

Stack:

CS 61B Fall 2022

30 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12

BFS:

Stack: 14

CS 61B Fall 2022

31 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12

BFS:

Stack: 14 13

CS 61B Fall 2022

32 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13

BFS:

Stack: 14

CS 61B Fall 2022

33 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14

BFS:

Stack: 14

CS 61B Fall 2022

34 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14

BFS:

Stack: 15

CS 61B Fall 2022

35 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS:

Stack:

CS 61B Fall 2022

36 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS:

CS 61B Fall 2022

37 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS:

Queue: 10

CS 61B Fall 2022

38 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10

Queue: 3, 12

CS 61B Fall 2022

39 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3

Queue: 12, 1, 7

CS 61B Fall 2022

40 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12

Queue: 1, 7, 11, 14

CS 61B Fall 2022

41 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1

Queue: 7, 11, 14

CS 61B Fall 2022

42 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1 7

Queue: 11, 14

CS 61B Fall 2022

43 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1 7 11

Queue: 14

CS 61B Fall 2022

44 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1 7 11 14

Queue: 13, 15

CS 61B Fall 2022

45 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1 7 11 14 13

Queue: 15

CS 61B Fall 2022

46 of 107

1a Trees, Graphs, and Traversals, Oh My! Write out the inorder and BFS traversals of this BST.

10

3

1

7

12

11

14

13

15

Inorder: 1 3 7 10 11 12 13 14 15

BFS: 10 3 12 1 7 11 14 13 15

Queue:

CS 61B Fall 2022

47 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

CS 61B Fall 2022

48 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A
B
C
D
E
F
G

From

To

CS 61B Fall 2022

49 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B
C
D
E
F
G

From

To

CS 61B Fall 2022

50 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B			✓
C
D
E
F
G

From

To

CS 61B Fall 2022

51 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B			✓
C						✓
D
E
F
G

From

To

CS 61B Fall 2022

52 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B			✓
C						✓
D		✓			✓	✓
E
F
G

From

To

CS 61B Fall 2022

53 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B			✓
C						✓
D		✓			✓	✓
E						✓
F
G

From

To

CS 61B Fall 2022

54 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

	A	B	C	D	E	F	G
A		✓		✓
B			✓
C						✓
D		✓			✓	✓
E						✓
F
G						✓

From

To

CS 61B Fall 2022

55 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

A
B
C
D
E
F
G

CS 61B Fall 2022

56 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

A
B
C
D
E
F
G

B, D

CS 61B Fall 2022

57 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

A
B
C
D
E
F
G

B, D

C

CS 61B Fall 2022

58 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

A
B
C
D
E
F
G

B, D

C

F

CS 61B Fall 2022

59 of 107

1b Graph Representations Write out the adjacency matrix and adjacency list.

A

B

D

E

F

C

G

A
B
C
D
E
F
G

B, D

C

F

B, F, E

F

CS 61B Fall 2022

60 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

DFS Post-Order:

Stack:

CS 61B Fall 2022

61 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A

DFS Post-Order:

Stack: A

CS 61B Fall 2022

62 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B

DFS Post-Order:

Stack: A, B

CS 61B Fall 2022

63 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C

DFS Post-Order:

Stack: A, B, C

CS 61B Fall 2022

64 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F

DFS Post-Order:

Stack: A, B, C, F

CS 61B Fall 2022

65 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F

DFS Post-Order:

F

Stack: A, B, C

CS 61B Fall 2022

66 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F

DFS Post-Order:

F, C

Stack: A, B

CS 61B Fall 2022

67 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F

DFS Post-Order:

F, C, B

Stack: A

CS 61B Fall 2022

68 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F, D

DFS Post-Order:

F, C, B

Stack: A, D

CS 61B Fall 2022

69 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F, D, E

DFS Post-Order:

F, C, B,

Stack: A, D, E

CS 61B Fall 2022

70 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F, D, E

DFS Post-Order:

F, C, B, E

Stack: A, D

CS 61B Fall 2022

71 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F, D, E

DFS Post-Order:

F, C, B, E, D

Stack: A,

CS 61B Fall 2022

72 of 107

1c Graph Representations Write out the order in which nodes are visited by DFS pre-order and post-order.

A

B

D

E

F

C

G

DFS Pre-Order:

A, B, C, F, D, E

DFS Post-Order:

F, C, B, E, D, A

Stack:

CS 61B Fall 2022

73 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - ]

CS 61B Fall 2022

74 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - f ]

f

CS 61B Fall 2022

75 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - f h ]

f

h

CS 61B Fall 2022

76 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - f h d ]

f

h

d

CS 61B Fall 2022

77 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - d h f ]

d

h

f

CS 61B Fall 2022

78 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - d h f b ]

d

h

f

b

CS 61B Fall 2022

79 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - d b f h ]

d

b

f

h

CS 61B Fall 2022

80 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - b d f h ]

b

d

f

h

CS 61B Fall 2022

81 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - b d f h c ]

b

d

f

h

c

CS 61B Fall 2022

82 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - b c f h d ]

b

c

f

h

d

CS 61B Fall 2022

83 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - ? c f h d ]

???

c

f

h

b

d

CS 61B Fall 2022

84 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - d c f h ]

d

c

f

h

CS 61B Fall 2022

85 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - c d f h ]

c

d

f

h

CS 61B Fall 2022

86 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - ? d f h ]

???

d

f

h

CS 61B Fall 2022

87 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - ? d f h ]

???

d

f

h

c

CS 61B Fall 2022

88 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - h d f ]

h

d

f

CS 61B Fall 2022

89 of 107

2a Absolutely Valuable Heaps Draw the heap and its corresponding array after each operation below.

MinHeap<Character> h = new MinHeap<>();

h.insert(‘f’);

h.insert(‘h’);

h.insert(‘d’);

h.insert(‘b’);

h.insert(‘c’);

h.removeMin();

Underlying array: [ - d h f ]

d

h

f

CS 61B Fall 2022

90 of 107

2b Absolutely Valuable Heaps

Your friendly TA Allen challenges you to quickly implement an integer max-heap data structure. However, you already have written a min-heap and you don't feel like writing a whole second data structure. Can you use your min-heap to mimic the behavior of a max-heap? Specifically, we want to be able to get the largest item in the heap in constant time, and add things to the heap in 𝚹(log(n)) time, as a normal max heap should.

CS 61B Fall 2022

91 of 107

2b Absolutely Valuable Heaps

Your friendly TA Allen challenges you to quickly implement an integer max-heap data structure. However, you already have written a min-heap and you don't feel like writing a whole second data structure. Can you use your min-heap to mimic the behavior of a max-heap? Specifically, we want to be able to get the largest item in the heap in constant time, and add things to the heap in 𝚹(log(n)) time, as a normal max heap should.

For every insert operation, negate the number and add it to the min-heap.

For a removeMax operation call removeMin on the min-heap and negate the number returned. Any number negated twice is itself, and since we store the negation of numbers, the order is now reversed (what used to be the max is now the min).

CS 61B Fall 2022

92 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

CS 61B Fall 2022

93 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

logN

jedi(N, 1)

CS 61B Fall 2022

94 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

logN

jedi(N, 1)

jedi(N, 5)

5logN

CS 61B Fall 2022

95 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

logN

jedi(N, 1)

jedi(N, 5)

jedi(N, 25)

5logN

25logN

CS 61B Fall 2022

96 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

logN

jedi(N, 1)

jedi(N, 5)

jedi(N, 25)

…

jedi(N, N/5)

5logN

25logN

(N/5)* logN

…

CS 61B Fall 2022

97 of 107

3a Runtimes Go Brrr Assume that logarithmic runs in log(N) time with respect to N. Give the tightest possible runtime bound for weird.

public void weird(int N) {

jedi(N, 1);

}

public void jedi(int N, int x) {

if (x < N) {

for (int i = 1; i <= x; i += 1) {

logarithmic(N); // runs in log(N) time

}

jedi(N, x * 5);

}

logN

jedi(N, 1)

jedi(N, 5)

jedi(N, 25)

…

jedi(N, N/5)

5logN

25logN

(N/5)* logN

…

Total work: logN + 5logN + 25logN + … + (N/5)logN

= (1 + 5 + 25 + … + N/5)logN

Runtime: Θ(NlogN)

CS 61B Fall 2022

98 of 107

3b Runtimes Go Brrr Give the best- and worst-case asymptotic bounds. Assume that randomInt(a, b) returns a random integer in the range [a, b) and runs in constant time.

public int untilDuplicate(int N) {

ArrayList<Integer> L = new ArrayList<>();

while (true) {

int num = randomInt(0, N);

if (L.contains(num)) {

return num;

}

L.add(num);

}

Best:

Worst:

CS 61B Fall 2022

99 of 107

3b Runtimes Go Brrr Give the best- and worst-case asymptotic bounds. Assume that randomInt(a, b) returns a random integer in the range [a, b) and runs in constant time.

public int untilDuplicate(int N) {

ArrayList<Integer> L = new ArrayList<>();

while (true) {

int num = randomInt(0, N);

if (L.contains(num)) {

return num;

}

L.add(num);

}

Best: Θ(1)

Worst: Θ(N²)

The best case occurs when the first two calls to randomInt return the same number.

The worst case occurs when the first N calls to randomInt all return a new number not in the list yet (contains runs in linear time with respect to the length of the list)

CS 61B Fall 2022

100 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

CS 61B Fall 2022

101 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

3^N

lucy(N)

CS 61B Fall 2022

102 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

3^N

lucy(N)

3^N-2

lucy(N - 2)

CS 61B Fall 2022

103 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

3^N

lucy(N)

3^N-2

3^N-4

3^N-2

3^N-4

lucy(N - 2)

lucy(N - 4)

CS 61B Fall 2022

104 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

3^N

lucy(N)

3^N-2

3^N-4

3^N-2

3^N-4

lucy(N - 2)

lucy(N - 4)

…

1

lucy(1)

CS 61B Fall 2022

105 of 107

3c Runtimes Go Brrr Given that exponentialWork runs in Θ(3^N ) time with respect to input N, what is the runtime of lucy?

public void lucy(int N) {

if (N <= 1) {

return;

}

lucy(N - 2);

exponentialWork(N);

}

3^N

lucy(N)

3^N-2

3^N-4

3^N-2

3^N-4

lucy(N - 2)

lucy(N - 4)

…

1

lucy(1)

Total work = 3^N + 3*3^N-2 +

9*3^N-4 + … + 3^N/2*1

= 3^N + 3^N-1 + 3^N-2 + … + 3^N/2

Runtime: Θ(3^N)

CS 61B Fall 2022

106 of 107

4 Updog Implement updog such that two dogs will only greet each other once (ie. Lucky should not bark at Fido if Fido has already barked at Lucky).

public class Dog {

String name;

public Dog(String name) {

this.name = name;

}

public void bark(Dog d) {

System.out.println("Hello " + d.name + ", I'm " + this.name);

}

public static void updog(Iterable<Dog> dogs) {

}

CS 61B Fall 2022

107 of 107

4 Updog Implement updog such that two dogs will only greet each other once (ie. Lucky should not bark at Fido if Fido has already barked at Lucky).

public class Dog {

String name;

public Dog(String name) {

this.name = name;

}

public void bark(Dog d) {

System.out.println("Hello " + d.name + ", I'm " + this.name);

}

public static void updog(Iterable<Dog> dogs) {

HashSet<Dog> seenDogs = new HashSet<Dog>();

for (Iterator<Dog> iter1 = dogs.iterator(); iter1.hasNext(); ) {

Dog d1 = iter1.next();

seenDogs.add(d1);

for (Iterator<Dog> iter2 = dogs.iterator(); iter2.hasNext();) {

Dog d2 = iter2.next();

if (!seenDogs.contains(d2)) {

d1.bark(d2);

}

CS 61B Fall 2022