DATA STURCTURES - Post Midterm 2

Priority queues are implemented with a…

binary heap

Properties of a binary heap

A binary heap is always a complete binary tree:

1) Every level of the tree is completely filled, except the last which should be filled from left to right

2) Largest key is a[1]

3) Can use array indices to move through tree —> Parent of node at k is k/2 and children of node at k are at 2k and 2k+1

In a binary heap, the parent’s key must be ________________ than children’s keys

no smaller

How do you insert into a binary heap?

Add node at the end, then swim it up

Note: May need to swim because the new element can have a larger key than its parent

How does swim work in binary heap?

For example, for a MAX heap:

1) Identify the parent

2) If the value of the child is greater than the parent, swap

3) Once parent is greater than child, stop

How does sink work in binary heap?

1) Identify the largest child

2) If the parent is smaller than the largest child, swap

3) Repeats until parent is larger than children

How do you demote a key in a binary heap?

Exchange key in parent with key in larger child until heap order is restored (sink)

Note: May have to sink when a key becomes smaller than one or both of its children

How to delete the maximum in a binary heap?

Exchange root with node at end, then sink it down

What is the max-heap order invariant?

The key in each node is greater than or equal to all its children keys

What is the running time of insert and delete-max in a binary heap?

Both are log(n)

Heapsort

1) View input array as a complete binary tree

2) Heap construction: Build a max-heap with all n keys

3) Sortdown: Repeatedly remove the maximum key

What is the best, average, and worst case for heapsort?

O(n log n) for all three cases.

Note: n log n guarantee and in-place sorting algorithm

Heapsort is optimal for both time and space, but…

1) Inner loop longer than quicksort’s

2) Makes poor use of cache

3) Not stable

Separate-chaining symbol table

Uses an array of m linked lists:

1) Hash: Map key to integer i between 0 and m - 1

2) Insert: Put at front of ith chain (if not already in chain)

3) Search: Sequential search in ith chain

When resizing a hash table, what happens to all keys?

All keys must be rehashed

Linear-probing hash table

1) Hash: Map key to integer i between 0 and m - 1

2) Insert: Put at table index i if free; if not try i + 1, i + 2, etc.

3) Search table index i; if occupied but no match, try i + 1, i + 2, etc.

Note: Array length m must be greater than number of key-value pairs n

What is the running time of separate chaining and linear probing?

A graph is a set of vertices connected pairwise by _______.

edges

Two vertices are connected if…

there is a path between them

In an undirected graph, what is the maximum number of edges on a Graph of V vertices?

V * (V-1)/2

In a directed graph, what is the maximum number of edges on a Graph of V vertices?

V * (V-1)

Depth-first search

To visit a vertex v:

1) Mark vertex v

2) Recursively visit all unmarked vertices adjacent to v

Note: Uses a Stack and goes as deep as possible down one path before backtracking

What data structures are used in depth-first search?

1) Boolean array marked[] to mark vertices

2) Integer array edgeTo[] to keep track of paths (edgeTo[w] == v) means that edge v-w taken to discover vertex w

3) Function-call stack for recursion

Breadth-first search

Repeat until queue is empty:
1) Remove vertex v from queue

2) Add to queue all unmarked vertices adjacent to v and mark them

Note: Explores all neighbors at the current depth before moving to the next level

In any connected graph G, BFS computes __________ paths from s to all other vertices in time proportional to E + V

shortest

Which is order of growth of running time of removing an edge v→w from a digraph uses the adjacency-lists representation, where V is the number of vertices and E is the number of edges?

outdegree(v)

Which is order of growth of running time of the following code fragment ifthe digraph uses the adjacency-lists representation, where V is the number of vertices and E is the number of edges?

E + V

What is the adjacency list representation of a directed graph?

A vertex-indexed array of lists

What is an in-degree in directed graphs?

The number of edges pointing into a vertex

What is an out-degree in directed graphs?

The number of edges pointing out of a vertex

Directed acyclic graph (DAG)

Directed graph with no cycles

Topological sort

1) Start with DFS

2) Move to an unvisited neighbor until there is a node that has no unvisited neighbors left

3) Push that node onto the stack

4) Go back to previous node and se eif it has other unvisited neighbors. If not, push it onto the stack

Once every node is visited, reverse postorder is simply the elements as you pop them off the Stack

In topological sort, how do you find the stopping and starting points?

Vertices with outdegree = 0 will always be the stopping points

Vertices with indegree = 0 should be at the front of the order

What are the steps to heapify an unsorted array?

1) Find the last parent at index i = n/2

2) Compare the parent to its left child (= 2i) and right child (= 2i + 1). Then sink or swim as needed

3) If a sink or swim was performed, check that max-heap or min-heap properties are still valid and continue to sink or swim if needed

4) Once that node is settled, move to the previous index (= i - 2) and repeat

How does the sortdown algorithm work?

1) Swap the root (at index 1) with the last element in the active heap —> This puts the largest number in its final sorted position

2) The last element is no longer in the “active” heap, it is no longer touched again for the rest of the sort

3) Sink the new root/first element to its proper level —> Compare the root with its children and swap with the larger child

Recall that left child = 2i and right child = 2i + 1

On the undirected and directed graph implementation, what is the worst-case running time for the space needed in: list of edges, adjacency matrix, adjacency lists?

List of edges: E

Adjacency matrix: V²

Adjacency lists: E + V

On the undirected and directed graph implementation, what is the worst-case running time for checking if w is adjacent to v in: list of edges, adjacency matrix, adjacency lists?

List of edges: E

Adjacency matrix: 1

Adjacency list: degree(v)

On the undirected graph implementation, what is the worst-case running time for determining the degree of v in: list of edges, adjacency matrix, adjacency lists?

List of edges: E

Adjacency matrix: V

Adjacency lists: degree(V)

On the directed graph implementation, what is the worst-case running time for determining the degree of v in: list of edges, adjacency matrix, adjacency lists?

List of edges: Out-degree and in-degree is both E

Adjacency matrix: Out-degree and in-degree is both V

Adjacency list: Out-degree = degree(v) and in-degree = E + V

Depth-First Search (DFS) populates two data structures marked[] and edgeTo[]. List three distinct characteristics of an undirected graph that you could determine based on the results of examining those data structures after DFS runs once from a vertex s.

1) Is the graph connected

2) Is there a path from the starting vertex to a given vertex

3) What is a path from the starting vertex to a given vertex (if one exists)