Graphs

Question 1

Directed Edges

Answer 1

An edge (u,v) is from u to v, not v to u

Question 2

Undirected Edges

Answer 2

An edge (u,v) is from u to v AND from v to u

Question 3

Weighted Edges

Answer 3

Each edge has a “weight” (“cost”) associated with it (i.e. magnitude associated with relationship)

Question 4

Unweighted Edges

Answer 4

Edges do not have weights

Question 5

Cycle

Answer 5

A valid path starting and ending at the same node

Question 6

Class: Unstructured

Answer 6

A disconnected collection of nodes

Question 7

Class: Sequential

Answer 7

An ordered collection of connected nodes (i.e. Linked List)

Question 8

Class: Hierarchical

Answer 8

A ranked collection of connected nodes

Question 9

Class: Structured

Answer 9

A collection of both connected and disconnected nodes

Question 10

Multigraph

Answer 10

A given pair of nodes may have multiple distinct edges (i.e. cites and flights, different prices between same cities)

Question 11

Adjacency Matrix

Answer 11

O(|V|^2)
Good for dense graphs.
Not good for sparse graph.
Must iterate through all indices 
Access constant time for searching.

From is rows, To is columns.

For undirected graph, it will be symmetric matrix.

Diagonals will be self directed path.

Question 12

Adjacency List

Answer 12

Hash tables or has maps, or linked list. Has very fast look up and saves space without reference null connections unlike matrix. O(|V| + |E|)

Question 13

Breadth First Search (BFS) Algorithm

Answer 13

1. Add (0, start) to queue
2. While the queue is not empty:
   a. pop (d, curr) from the queue
   b. if curr has not been visited:
   
   • mark curr as visited with distance d
   • for all edges (curr, w):
     if w has not been visited add (d+1, w) to queue

Question 14

Depth First Search (DFS) Algorithm

Answer 14

1. Add start to stack
2. While the stack is not empty:
   a. pop curr from stack
   b. if curr has not been visited
   
   • mark curr as visited
   • for all edges (curr, w):
     
     • if w has not been visited, add w to stack

Question 15

Dijkstra’s Algorithm
1. know prerequisite condition)
2. valid by proof by contradiction. No future path will be less than the current path using algorithms
3. keep track of the shortest path coming from
4.

Answer 15

Fundamentally the same as BFS (Queue and DFS (stack), but Dijkstra’s is a (min) heap where lowest distance is highest priority

Set all nodes to infinite distance. 
1. add (0,start-inital node/source) to PQ/heap. Set others to -1 or infinity
2. while PQ !=empty:
 - A. Pop the (d,curr) from PQ
 - B. if curr is not done:
   - 1. mark curr as done
   - 2. (curr, w, e): 
only works for graphs with positive edge weights. No negative weights

Question 16

Dijkstra’s Algorithm Time Complexity

Answer 16

Overall: O(|V| + |E| log |E|)
P. Initialization of infinity = O(|V|)
1. Add (0,Start) to PQ = O(1)
2. while PQ not empty:
  A. Pop (d, curr) from PQ = O(log |E|) , since using a heap (perfectly balanced) number of pops is log of the number of edges

Question 17

BFS Search Algorithm (Min-Path)

Debashis (11/25)

Answer 17

P. Initialize all nodes (other than source) with infinity distance and previous=-1

1. Point CURR to source. Add CURR to PQ. Then enter while loop of (while PQ not empty).
2. Pop from PQ (min heap). Start with (source) node and add to PQ all neighboring nodes (technically edges). If distance is infinity update neighbors with distance between +1. Once all neighbors pushed to PQ, then exit.
3. Pop queue and update dist of curr to 2, prev to prev node, pop queue and update distance to 2 and prev prev node

Question 18

For directed and connected graph what is expected

Answer 18

Each node is only enqueued once

At any time the queue holds at most 2 distinct DISTANCE VALUE from all nodes in it.

It can work for a graph with a cycle

Question 19

Dijsktra’s Algorithm Properties

Answer 19

Properties (using PQ holding pairs (pointer to vertex, path cost ) )

Path Cost is the priority (low is higher priority)

The PAIR is maintaining a path cost to vertex.

Multiple pairs with the same “pointer-to-vertex” part can exist in the priority queue at the same time. These will usually differ in the “path cost”

Question 20

Dijkstra’s Algorithm: Data Structures

no negative vertex weight

Answer 20

Maintain a sequence (array, vector, etc) of vertex objects, indexed by vertex number

• vertex objects contain 3 fields (and others):
  1. Dist: cost of teh best (least cost) path discovered so far from start vertex to “this” (curr) vertex
  2. Prev: the vertex number (index) of the rpevious node to the best path
  3. Done: a boolean indicating whether the Dist and Prev fields contain the final best values for this vertex

Question 21

Disjoint Sets is ADT or DS

Answer 21

Abstract Data Type

ADT optimized for Union and Find

Union: Given two elements, merge the sets to which they belong

Find: Given an element e, return the set to which it belongs

Question 22

Purpose of union operation

Answer 22

Join two sets. Once two sets have been unioned , they should have the same sentinel node. (there are a lot of freedom around the concept of union, since there is many ways to merge two sets of vertices.)
Union by size
Union by weight

Question 23

Queue

Answer 23

Array 	       List
Enqueue 	O(1)/O(n) 	       O(1)
Dequeue 	O(1) 	               O(1)
Peek 	        O(1) 	               O(1)

Question 24

Disjoint Set is an ADT

Commonly referred to as Union-Find data type

Answer 24

Interface supports:
Union: given two elements u and v, merge the sets to which they belong

Find: Given an element e, return the set to which it belongs.

Efficiently implemented using Up-Tree DATA STRUCTURE. Simply a graph which all nodes have. ainge “parent” pointer. Those that do not have a parent pointer are the SENTINEL NODES. Sentinel Nodes represent a single set.

Question 25

Kruskal’s Algorithm is implemented efficiently, it has a worst-case Big-O time complexity that is the same as Prim’s Algorithm: O(|V| + |E|*log(|E|)

Answer 25

Implementation-wise, here is the pseudocode for Kruskal’s Algorithm on a weighted undirected graph G = (V,E):

Create a forest of vertices
Create a priority queue containing all the edges, ordered by edge weight
While fewer than |V| - 1 edges have been added back to the forest:
    Deque the smallest-weight edge (v, w, c) from the priority queue
    If v and w already belong to the same tree in the forest: go to stipek 3.1 (adding this edge would create a cycle)
    Else: Join those vertices with that edge and continue

Question 26

Can you identify the similarities and differences between Kruskal and rim’s algorithm?

Answer 26

The both have same run-time complexity O(|V| + |E|* log(|E|))

Prims uses PQ sorted by edge weights (single edge weights)

Dijkstra uses total path edge weights explored so far in PQ for comparison.

Prim’s adds an edge from anywhere in the existing/current subgraph of vertices with the least weight.

Prims and Dijsktra both start from a designed node/vertex.

Kruskal arbitrarily starts at any node in the graph.

Question 27

DFS uses STACK (ADT)

Stack is FILO (first in last out)

Answer 27

Stack guarantees visiting all vertices that enter the stack by most RECENT FIRST (ordering by time of entry), ensuring the next vertex is that one entering at the first junction point.

Question 28

The only difference in the pseudocode for BFS and DFS was their use of a queue and stack, respectively.

Thus, the difference in runtime complexity of DFS and BFS depends on their ADTs runtime.

But worst-cast time complexity of both ADT are the SAME.

Answer 28

Pop(), top(), and push() has worst-case time complexity of O(1)

DFS and BFS have worst-case time complexity of:
O(|V| +|E|)

Question 29

How do DFS and BFS differ?

Answer 29

They differ by their memory management.

BFS had to store all vertex’s neighbors at each step in a queue to later traverse those neighbors.

DFS only needed to store previous neighbor to explore the next one. Thus, in certain graphs (structures) DFS can be more memory efficient.

Question 30

How do DFS and BFS differ?

Answer 30

They differ by their memory management.

BFS had to store all vertex’s neighbors at each step in a queue to later traverse those neighbors.

DFS only needed to store previous neighbor to explore the next one. Thus, in certain graphs (structures) DFS can be more memory efficient.

A LONG/TALL/HEIGHT tree will have DFS store more elements in memory. A wider tree or a structure with many edges will have BFS store more information/elements

Question 31

In a GRAPH with a TREE structure, DFS is not guaranteed to find a path between any two nodes.

In a GRAPH that is NOT a TREE, DFS will guarantee to find a path between any two nodes, it is not guaranteed to find the shortest path between two nodes.

Answer 31

BFS is guaranteed to find the shortest path in a graph that is not a tree.

Important to consider parameters of the problem to choose between BFS and DFS.

Question 32

For a connected, weighted graph with n vertices and exactly n edges, it is possible to find a minimum spanning tree in O(n) time.

Answer 32

This graph only contains one cycle, which can be found by a DFS. Just remove the heaviest edge in that cycle.

Question 33

In a connected, weighted graph, every lowest weight edge is always in some minimum spanning tree.

Answer 33

It can be the first edge added by Kruskal’s algorithm.

Question 34

Algorithm:

If m = n, give an algorithm that runs in Θ(lg n) time.

Answer 34

Pick the median m1 for A and median m2 for B. If m1 = m2, return m1. If m1 > m2, remove the second half of A and the first half of B. Then we get two subarrays with size n/2. Repeat until both arrays are smaller than a constant m1 < m2 is symmetric.

Question 35

Argue that: Any comparison based sorting algorithm can be made to be stable, without affecting the running time by more than a constant factor. (seems like a Dijsktra’s Algorithm)

Answer 35

Solution: To make a comparison based sorting algorithm stable, we just tag all elements with their original positions in the array. Now, if A[i] = A[j], then we compare
i and j , to decide the position of the elements. This increases the running time at a factor of 2 (at most).

Question 36

Argue that you cannot have a Priority Queue in the comparison model with both the following properties.

EXTRACT-MIN runs in THETA (1) time.

BUILD-HEAP runs in THETA(n) time.

Answer 36

If such priority queues existed, then we could sort by running BUILD-HEAP (THETA(n)) and then extracting the minimum n times ( n*THETA(1)= THETA(n)). This algorithm would sort THETA(n) time in the comparison model, which violates the THETA(log n) lower bound for comparison based sorting.

Question 37

Prim’s Algorithm Runtime

Answer 37

O(n log n)

Question 38

Depth First Search

Answer 38

O(n)

Question 39

(requires a diagram) Given a set of keys, 2,3,5,7,11,13,17,19, can you place them accordingly to fit a predetermined structure and perserve invariants/rules?

Can you explain why this cannot be a Red Black Tree

Answer 39

One is 17, 11, 19 , 3, 13 , 2 ,5, 7

Why not a read black tree? The number of black nodes on the path of the root

Question 40

(requires a diagram) The binary search tree can be transformed into a red-black tree by performing a single rotation. Draw the red-black tree that results, labeling each node with “red” or “black.”
Include the keys from part (a).

Answer 40

Rotate right around the root. There are several valid ways to color the resulting tree. Here is one possible answer (all nodes are colored black except for 7).

Question 41

Minimum Spanning Tree:

Let G = (V, E) be a connected, undirected graph with edge-weight function w : E => R, and
assume all edge weights are distinct. Consider a cycle  in G, where vk+1 = v1,
and let (vi, vi+1) be the edge in the cycle with the largest edge weight. Prove that (vi, vi+1) does
not belong to the minimum spanning tree T of G.

Answer 41

Proof by contradiction. Assume for the sake of contradiction that (vi, vi+1) does belong to the minimum spanning tree T. Removing (vi, vi+1) from T divides T into two connected components P and Q, where some nodes of the given cycle are in P and some are in Q. For any cycle, at least two edges must cross this cut, and therefore there is some other edge (vj , vj+1) on
the cycle, such that adding this edge connects P and Q again and creates another spanning tree T ‘.
Since the weight of (vj, vj+1) is less than (vi, vi+1), the weight of T ‘ is less than T and T cannot
be a minimum spanning tree. Contradiction.

Question 42

Comparing Prims and Kruskals Algorithm

Both algorithms choose and add at each step a min-weight edge from the remaining edges, subject to constraints.

Prim’s:

1. start a root
2. Two rules for new edge.
   a. adding new edge does not create cycle in subgraph
   b. the graph is still a connected subgraph
3. terminate if no more edges to add can be found

Kruskal’s MST algorithm:

1. Start a a min-weight edge
2. One rule to follow for adding a new edge: No cycle in a forest of trees built
3. Terminate if no more edges to add can be found

At each step a forrest of trees merging as the algorithm progresses

Answer 42

To prove these algorithms:

Let B be a subset of V(G); |B|