Project 2The subject of this project is to create an implementation of the Nagamochi-Ibaraki algorithm (see in the lecture notes) for finding a minimum cut in anundirected graph, and experiment with it.Tasks:1. Explain how your implementation of the algorithm works. Providepseudo code for the description, with sufficient comments to make itreadable and understandable by a human.2. Write a computer program that implements the algorithm. You mayuse any programming language under any operating system, this isentirely of your choice.3. Run the program on randomly generated examples. Let the numberof nodes be fixed at n = 25, while the number m of edges will varybetween 50 and 550, increasing in steps of 5. Once a value of m isselected, the program creates a graph with n = 25 nodes and m edges.The actual edges are selected randomly among all possible ones, withparallel edges allowed, but self-loops are excluded.4. Using your random graph examples, find an experimental connectionbetween the number of edges and the edge-connectivity λ(G). (If thegraph happens to be disconnected, then take λ(G) = 0.) How doesthe connectivity depend on the number of edges? Show the foundrelationship graphically in a diagram, exhibiting λ(G) as a function ofm, while keeping n = 25 fixed.5. Investigate the following question experimentally: given a random graphwith n nodes (n = 25) and m edges, how many new random edges needto be added to it to increase the connectivity by one? Let us denotethis quantity by f (m). That is, given a random graph with m edges,keep adding new random edges one by one, until the connectivity growsby one. (New edges are allowed to be parallel to old ones.) The numberof added new edges will be the value of f (m). Due to the randomness,1the result may vary in different experiments, even for the same valueof m. To get a more reliable estimate, run several experiments for thesame m, and average out the obtained f(m) values. Then show thisaveraged f(m) graphically, as the function of m.6. Give a short explanation why the functions found in items 4 and 5 lookthe way they look. In other words, try to argue that they indeed showthe behavior that can be intuitively expected, so your program is likelyto work correctly. Note that it is part of your task to find out whatbehavior can be expected.Important note: If there is anything that is not specified in this projectdescription, that automatically means it is left to your choice.Submission guidelinesDescribe everything, including algorithms, program, results and figures neatlyand clearly in a study. Include everything in a single document that can beread as a report and submit it through e-learning. (Do not send it via e-mail!) Do not include executable code, but include the source code in anappendix to the study. Your submission will be read as a report, but usuallywe do not run the program. On the other hand, if either there are signs ofnon-original work or if you want to dispute the received score, then you willbe asked to demonstrate your program on a computer, show and explain itsdetails.Notes:• The work must be fully individual and original. Any form of cheat-ing is a serious violation of University policies and can lead to seriousconsequences.• It may be helpful to think about the whole project presentation thatyour task is not only to solve a technical problem, but you also haveto “sell” the results. Try to look at your work from the viewpointof a potential “customer”, who either wants to buy such a software,or perhaps wants to hire somebody to carry out similar tasks. Howconvincing would your presentation look for such a
View Full Document