Postagens

Question 3 – Network Flow

Imagem
 The contractors for the new " Alphaville Barão Geraldo " luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago ) through a series of seven interconnected retention dams (Nodes  A through G ) to the development site (Node Alpha) . The contract specifies that the network  must be able to deliver a minimum of 30,000 liters of water per minute . The students have produced the following design, with pipe capacities also measured in thousands of liters per minute: Analyze the following propositions regarding the network's performance and limitations. I.  Suppose that, to budget cuts, the pipe from  Dam E to Dam G  must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would  still be met . II.  To improve performance, a proposal is mad...

Question 2 - Strongly Connected Components

Imagem
Barabasi's  Network Science   book describes the World Wide Web as a directed network where nodes are web pages and links are URLs. Imagine a small portion of this network for a university department: A Homepage (H) links to an About page (A) and a Research page (R).  The About page (A) links back to the Homepage (H). The Research page (R) links to three specific Publication pages (P1, P2, P3). Each Publication page (P1, P2, P3) links back to the main Research page (R). Based on the concept of Strongly Connected Components (SCCs) and the Kosaraju-Sharir algorithm, consider the following propositions: Propositions: I. An SCC is any set of nodes where every node is mutually reachable from every other. Therefore, because a path exists from R to P1 and back, the set {R, P1} is a valid SCC. II. In the context of the World Wide Web, an SCC represents a maximal set of web pages where a user can navigate between any pair of pages within that set. Based on this, the set {H, A} is...

Question 1 - BFS

Consider the following five statements regarding the Breadth-First Search (BFS) algorithm: I. For any given unweighted graph, the length of the shortest path found by BFS between two nodes is always less than or equal to the length of the path found by a Depth-First Search (DFS) between the same two nodes.  II. A single execution of BFS starting from an arbitrary node s is sufficient to identify all connected components in any given undirected graph.  III. An undirected graph can be tested for its bipartiteness by running BFS from a source node ' s'  and ensuring that every edge connects two vertices that lie in layers of opposite parity (one at an even distance from  s , the other at an odd distance). IV. The BFS algorithm can be implemented using a stack data structure instead of a queue and will still fulfill its function of finding the shortest path in unweighted graphs.  Which statements are correct?  a) II and IV b) I and III ...