Project 2The theme of the project is to compare three methods that we studied forcomputing the reliability of a general network configuration. (See the lecturenote “More Complex Configurations”.) The considered methods are theexhaustive enumeration, the method of minimal paths and the method ofminimal cuts.Specific tasks:1. Develop algorithms for each of the three methods. Note that the highlevel descriptions given in the lecture notes are not enough, since youalso have to specify how you actually want to find the details, such ashow you generate the possible states, the set of minimal paths, the setof minimal cuts etc.IMPORTANT NOTE: Finding algorithmic solutions for thesedetails is part of the task, you have to find them out yourself!Note, however, that you are not required to develop very sophisticatedalgorithms. It is acceptable here to use exhaustive search, that is,listing all possibilities, and excluding those that do not satisfy somecondition. While exhaustive search is not scalable for large tasks, forrelatively small examples it can still be appropriate.Describe how your algorithms work. First briefly explain informally theideas. Then provide pseudo code for the description of the algorithms,with sufficient comments to make them readable and understandableby a human.2. Write a computer program that implements all the three methods. Youmay use any programming language under any operating system, this isentirely of your choice. Make sure, however, that your program is wellstructured to support finding potential errors (debugging), checkingcorrectness or trying out algorithm changes. Explain how your programsupports these goals.13. Run the program on 5 examples, as detailed below, and show the resultsin an easily readable way.The input for the algorithms is described as follows. Represent theinput graph by an n× n matrix in which each row and and each columncorresponds to a node. Node 1 will be the source, and node n will be thedestination. Each entry of the matrix provides the reliability of an edgein the graph (each edge represents a component of the system) That is,the matrix entry pijis a number with 0 ≤ pij≤ 1. If it is 0, it meansthere is no edge between nodes i and j. If it is positive, it means thereis an edge between nodes i, j and its reliability is pij, that is, it operateswith probability pij, independently of the others. It is assumed that thegraph is undirected, that is, pij= pji. Let us restrict ourselves to graphsin which there are no multiple (parallel) edges between the same nodes,and there are no self-loops. The reliability of the entire configurationis defined as the probability of having at least one operational pathbetween the source (node 1) and the destination (node n).Choose your examples such that they are nontrivial, i.e, they cannotbe easily solved by hand. At the same time, their size should be chosensuch that the examples are still manageable by the program in reason-able time, taking into account that the program involves exhaustiveenumeration.4. Experiment with the three methods and draw some conclusions abouthow they behave. For example: how different are the reliability valuesobtained by the different methods for the same input? How do the run-ning times compare? If we tune the reliability of a single component,keeping the others fixed, how does the reliability change, as obtainedby the three algorithms? Make sure the program supports such ex-perimentation (for example, it can generate random inputs, presentsthe results in a way that supports comparison, represents the resultsgraphically whenever it is helpful etc).Note 1: If something is not specified in this project description, that meansit is automatically left to your choice.2Questions? See Note 1 above.Something is still not clear? Then follow the instructions in Note 1.Submission guidelinesDescribe everything, including verbal description, pseudo code, program, in-put/output data, exp erimental results, figures, conclusions, in a single doc-ument. Submit it through eLearning. Do not submit executable code, butinclude the source code as an Appendix in the document. Note: your sub-mission will be read as a document and not run as a program (but there aretwo exceptions, see them under Evaluation).Remark: It might be helpful to think about the whole project that yourtask is not only to solve the technical problem, but you also have to “sell”the results. Try to look at your work from the viewpoint of a potential“customer”: how convincing your presentation would look for a customer?EvaluationThe evaluation will focus on how well each of the specific tasks have beencarried out. Even though the submission will not be run, only read as adocument, but there are two exceptions. You will be asked to demonstrateon a computer how your program actually runs, if any of the following casesoccur:1. You do not agree with the grade and want to improve it. In this casethe demonstration should show that your work is actually better thanthe received grade.2. There is suspicion that the work is not original or not individually doneor the results were not produced by your own correctly running pro-gram. In this case a demonstration is required to clarify the situationand to receive any score.3Note:The work should be fully individual and original. Any form of cheating is aserious violation of University policies and can lead to serious
View Full Document
Unlocking...