Question 2. An airline serves 1000 cities and runs 5500 direct flights each day between these cities. Which of the following is a good data structure to represent the collection of flights?
a) A 1000 × 1000 array A, where A[i][j] = 1 if there is a direct flight from city i to city j and 0 otherwise. b) A stack containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j. c) A queue containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j. d) A list containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j.
Question 3. Suppose we obtain the following BFS tree rooted at node J for an undirected graph with vertices {A,B,C,D,E,F,G,H,I,J,K}. Which of the following cannot be an edge in the original graph?
Question 4. We are interested in topological orderings of the following DAG which satisfy the constraint that whenever 9 appears after 8, 2 must appear after 4. How many such orderings are there?
Question 5. Applying for permits to put up a factory is an 11 step process with specific dependencies. Each step takes a week to complete. What is the minimum number of weeks required to get all the permits in place?
Q2. Suppose we have a directed graph G = (V,E) with V = {1,2,…,n} and E presented as an adjacency list. For each vertex u in V, L(u) is a list [v1,v2,…,vk] such that (u,vi) in E for each i in {1,2,…,k}.
If we reverse the edges in G, we get a new graph GR = (V,ER) with the same set of vertices such that (u,v) in ER if and only if (v,u) in E.
We can represent GR using an adjacency list where, for each u in V, LR(u) is the list of neighbors of u with respect to ER.
Let n be the number of vertices in V and m be the number of edges in E. How long would it take to construct the adjacency lists LR(u), u in V, from the lists L(u), u in V?
These are Design and analysis of algorithms Week 3 Quiz Answers
Q5. Assembling a laptop consists of several steps, such as fixing the motherboard, inserting the battery, putting in the keyboard, attaching the screen, etc. Suppose there are 10 steps, labeled A, B, C, D, E, F, G, H, I, J. Each step takes a day to complete and we have the following dependencies between steps.
A must happen before H
B must happen before F
B must happen before G
C must happen before H
D must happen before E
E must happen before B
F must happen before A
F must happen before C
G must happen before F
I must happen before D
I must happen before G
J must happen before D
J must happen before I
What is the minimum number of days required to complete the interiors?
