CS 260 - Data Structures

Review for Final

Yusuf Osmanlioglu
Department of Computer Science
Drexel University
Binary Search Trees
● What is a tree ADT?
● What is a binary search tree?
● Tons of definitions: node, edge, parent, child, root, leaf, node height, tree height, node
depth, ancestor, descendent, sibling, left/right, path
● What are tree walks?
○ Why on earth would you like to use it?
○ What are the main functions for BST?
■ How do they work?
■ Especially, delete function? What observations do we benefit from?
○ What are the runtime for functions: initTree, insert, delete, search, print
● Given a tree with n nodes;
○ what is the height in worst case (i.e., max possible height)?
○ What is the height in best case (i.e., min possible height)?
○ How many of the nodes are there at the max height if the tree is a perfect tree?

2
Red-Black Trees
● What are Red-Black(RB) trees?
● How do RB trees differ from BSTs?
● What is the asymptotic cost of
○ insertion
○ deletion
○ search

in RB-trees?

● What is the height of an RB-tree with n nodes in the best/worst/average case?

● What is a potential use case of RB-trees?
● Given n integers in arbitrary order, suggest a sort algorithm that uses RB-trees?
○ What would be the runtime?

3
Heaps
● What are the basic properties of binary heaps?
● What is binary heaps good for?
● What is binary heaps NOT good for?
● How is it different than binary search trees?
● What is the runtime of deleteMin? Insert?
● What is the runtime of heap sort? Explain.
● What is the runtime of buildHeap function, which builds a heap from a set of elements
given as input
○ one at a time?
○ If the input is given to you all at once? (i.e., doing build heap in place)

4
Graphs
● What does G=(V,E) stand for when describing a graph?
● What type of data is proper to be represented with a graph?
● What is the difference/relationship between graphs and trees?
● In a graph G having V vertices, how many edges can there be at most if the graph is:
○ Directed (no self edges)
○ Undirected (no self edges)
○ Undirected (self edges allowed)
● In a graph, what does degree, path, cycle, subgraph mean?
○ Give real life examples/use cases for a cycle/path/subgraph/degree?
● How can you represent graphs?
○ What are their advantages/disadvantages?
● How can you search graphs?

5
Breadth-First Search
● What is the basic idea behind breadth-first search?
● What is the helper data structure used in BFS?
BFS(G,s)
○ What is its utility in the algorithm? 1 for each u in V
● What can be a good use case for BFS? 2 color[u] = white;
3 dist[u] = INFINITY;
● What is the runtime of BFS? 4 pred[u] = NULL;
5 color[s] = gray;
6 dist[s] = 0;
7 Q = {s};
8 while (Q is nonempty)
9 u = Dequeue[Q];
10 for each v in Adj[u]
11 if (color[v] == white)
12 color[v] = gray;
13 dist[v] = dist[u]+1;
14 pred[v] = u;
15 Enqueue(Q, v);
16 color[u] = black;

6
Depth-First Search
● What is the basic idea behind depth-first search?
● What is the helper data structure used in DFS?
○ What is its utility in the algorithm?
● What type of by-products does DFS produce after it is run?
○ Suggest ways to benefit from these by-products?
● What can be a good use case for DFS?
● What is the runtime of DFS?
DFS(G) DFSVisit(u)
1 for each u in V 1 color[u] = gray;
2 color[u] = white; 2 d[u] = ++time;
3 pred[u] = nil; 3 for each v in Adj(u)
4 if (color[v] == white)
4 time = 0;
5 pred[v] = u;
5 for each u in V
6 DFSVisit(v);
6 if (color[u] == white)
7 color[u] = black;
7 DFSVisit(u); 8 f[u] = ++time;
7
Topological sort
● What does it mean to sort a graph?
● Is it possible to sort a graph that contains cycle(s)?
● What does it mean to have a directed acyclic graph (DAG)?
● How can you identify a cycle in a directed graph?
● How can you topologically sort a graph?
● What is the runtime of topological sort?

1 TopologicalSort(G)
2 call DFS(G) to compute finishing times v.f for each vertex v
3 as each vertex is finished, insert it in head of a linked list
4 return the linked list of vertices

8
Strongly Connected Components
● Briefly explain what does a strongly connected component means?
● Suggest a real life problem where identifying a SCC solves the problem?
● Given an undirected graph, how could you calculate SCCs?
○ Given an undirected graph, how could you calculate connected components?
● Given a directed graph, how can you calculate SCCs?
● What is the runtime for calculating SCCs?

1 STRONGLY-CONNECTED-COMPONENTS(G)
2 call DFS(G) to compute finishing times u.f for each vertex u
3 compute GT, i.e., inverted graph
4 call DFS(GT), but in the main loop of DFS, consider the vertices in order of
decreasing u.f (as computed in line 2)
5 output the vertices of each tree in the depth-first forest formed in line 4
as a separate strongly connected component
9
Minimum Spanning Trees
● Given a graph G=(V,E), what is a:
○ spanning tree of that graph?
○ minimum spanning tree of that graph?
● How many edges would there be in an MST?
● Given an MST T of a weighted graph G=(V,E), what happens when:
○ an edge is added to T?
○ an edge is removed from T?
○ weight of an edge in E that is not in T is decreased? (is T still an MST?)
○ weight of an edge in E that is not in T is increased? (is T still an MST?)
○ weight of an edge in T is decreased? (is T still an MST?)
○ weight of an edge in T is increased? (is T still an MST?)

10
MST: generic algorithm
● What is the main idea behind calculating an MST?
○ sort the edges by weight
○ for each edge on sorted list, include that in MST if it
does not form a cycle with the edges already taken;
otherwise discard it

● Why does generic algorithm try to avoid cycles?

● When would the above algorithm halt?
● What determines the runtime of the above algorithm?

11
MST: Kruskal’s
● Which helper data structure does Kruskal’s algorithm use?
○ What is the purpose/benefit of using this data structure in achieving MST?
● What is the runtime of Kruskal’s algorithm?

function kruskal(Graph G = (E , V ))
Sort Edges
T = Empty Set
for each node n in V do
make-set(n)
end for
for each edge (x,y) in order do
if find-Set(x) ≠ find-Set(y) then
T = T ∪ {(x,y)}
union(Find-Set(x),Find-Set(y))
end if
end for
return T
end function

12
MST: Prim’s
● How does Prim’s algorithm differ from Kruskal’s?
○ Does it use a helper data structure?
○ If not, how does it handle avoiding cycles?
● What is the runtime of Prim’s?

function prim(Graph G = (V,E),w,r)

for each u in V do
u.key = ∞
u.p = NIL
end for
r.key = 0
Q = V
while Q ≠ ∅ do
u = EXTRACT-MIN(Q)
for each v in G.Adj[u] do
if v in Q and w(u,v) < v.key
then
v.p = u
v.key = w(u,v)
end if
end for 13
return r
Shortest Path Problem
● Can a shortest path include a cycle?
● Can there be a valid shortest path in a graph which has negative weight edges?
● Why is shortest path problem undefined in the presence of a negative weight cycle?
● What does sub-optimality of shortest path means in plain English?
● How does triangle inequality related to shortest path?
● What does relaxation of an edge mean in calculating shortest path?

14
Single-Source Shortest Path: Bellman-Ford
● What is the main catch of Bellman-Ford’s function Bellman-Ford(G, w, s)
shortest path algorithm? for each v in G.V do
v.d = ∞
● Does Bellman-Ford use a helper data
v.p = NIL
structure, other than the graph representation end for
itself? If yes, which one? s.d = 0
for i=1 to |G.V|-1 do
● Why does Bellman-Ford stop after running for each edge (u,v) in G.E do
|V|-1 iterations? if v.d > u.d + w(u,v) then
● Why does the algorithm make another final v.d = u.d + w(u,v)
v.p = u
iteration of relaxation after |V|-1 iterations? end if
● Does Bellman-Ford work for graphs with end for
negative weight edges? end for
for each edge (u,v) in G.E do
● What type of algorithm design paradigm does if v.d > u.d + w(u,v) then
Bellman-Ford fit under? return false
● What is the runtime of Bellman-Ford? return true
end function
15
Single-Source Shortest Path: Dijkstra
● What is the main catch of Dijkstra’s
function Dijkstra(G, w, s)
shortest path algorithm? for each v in G.V do
v.d = ∞
● Does Dijkstra’s use a helper data v.p = NIL
end for
structure, other than the graph s.d = 0
representation itself? If yes, which one? Q = V
while Q ≠ ∅ do
● Does Dijkstra’s work for graphs with u = Extract-Min(Q)
for each vertex v in G.Adj[u] do
negative weight edges? if v.d > u.d + w(u,v) then
v.d = u.d + w(u,v)
○ If no, give an example where the algorithm v.p = u
fails to find the shortest path. end if
end for
● What type of algorithm design paradigm end while
end function
does Dijkstra’s fit under?
● What is the runtime of Dijkstra’s?

16
All-Pairs Shortest Path
● Given Dijkstra’s and/or Bellman-Ford, how could you calculate all-pairs
shortest path of a given graph?
○ What would be the runtime of each for APSP problem?
● What is the main catch of Floyd-Warshall’s shortest path algorithm?
● Does Floyd-Warshall use a helper data structure, other than the graph
representation itself? If yes, which one?
● Does Floyd-Warshall work for graphs with negative weight edges?
○ If no, give an example where the algorithm fails to find the shortest path.
● What type of algorithm design paradigm does Floyd-Warshall fit under?
● What is the runtime of Floyd-Warshall?
● In calculating Arbitrage, how did we benefit from shortest path algorithms?

17
Algorithm Design Paradigms
● Dynamic programming
● Divide-and-Conquer
● Greedy
● Heuristics

18
Heuristic Graph Search: A* Algorithm
● What is the main catch of A* algorithm?
● How does it differ from
○ BFS?
○ DFS?
○ Dijkstra’s?
● Does A* use a helper data structure, other than the graph representation itself?
○ If yes, which one?
● What type of algorithm design paradigm does A* fit under?
● What is a heuristic?
○ Which heuristics does A* use?

19
Hard Problems
● What does it mean for a problem to be:
○ easy?
○ hard?
● Does NP mean “not-polynomial”?
● Does NP mean “not solvable”?
○ Can NP-hard problems be solved? How?
● What does NP mean?
● What does it mean to approximate a hard problem?
● What does polynomial time reduction mean?
● If you are given a problem A, which can be reduced (or converted) into another problem
B in polynomial time, and you already have a polynomial time solver for B, what can you
say about the hardness of A?
● If you are given a problem B, which you don’t know whether it is hard or not. But, you
were able to come up with a polynomial time reduction (or conversion) from a famous
hard problem A into your problem B, what can you say about the hardness of B?

20