Algorithmics (CE00333-3) Individual Assignment Page 3 of 3
Individual Assignment (Algorithmics-CE00333-3)
Learning Outcomes:
1) To learn how to create the Adjacency Matrix and Adjacency List for a given graph and to find best technique after analysis and any alternatives for the worst among given techniques.
2) To traverse and to find a vertex in the given graph using Depth and Breadth First Traversal methods.
3) To find the shortest path using Dijkstra’s Single Source Shortest Path algorithm.
4) To solve the given graph to find out the Minimum Spanning Tree (MST).
5) To compare the execution time efficiencies for all the above algorithms with their standard complexities in terms of Big Oh notation.
6) To determine the classes of the above problems with their justifications.
Research Assignment (100 marks)
Graph theory has many practical applications in the real world. One such application is to determine how a network of interconnected places can be optimized in order to ensure that commuters can travel as efficiently as possible.
For this specific assignment, the first graph problem is represented hereby:
Fig. 1 Graph Theory Problem (for BFS, DFS & Dijkstra’s SSSP)
The nodes in the above diagram represent the various places scattered across a country, while the edges represent the roads running between them. The weights of each edge represent the distance between each place.
You have to deliver a solution for the GRAPH THEORY problem mentioned above by drawing the adjacency list and adjacency matrix. Write a report on “which of the approaches is most beneficial and in under which circumstances it is beneficial”. You are also required to solve step-wise and compare the efficiencies of the given problem with BFS, DFS and Dijkstra’s Single Source Shortest Path (SSSP) algorithms in terms of Big-Oh notation with their calculated execution times (For BFS and DFS algorithm assume the graph as undirected and unweighted). Include algorithm/pseudo-code with your explanations and describe that how efficiency can be increased in case of Dijkstra’s Algorithm.
For this specific assignment, the second graph problem is represented hereby:
Fig. 2 Graph Theory Problem (MST)
The nodes in the above diagram represent the various oil stations scattered across a country, while the edges represent the oil pipelines running between them. The weights of each edge represent the distance between each point.
You have to deliver a solution for the GRAPH THEORY problem mentioned above by solving it step-wise to determine a Minimum Spanning Tree (MST) with Prim’s and Kruskal’s algorithmic approaches and to compare the efficiencies of both in terms of Big-Oh notation with their calculated execution times. Include algorithm/pseudo-code with your explanations.
Also, determine which complexity class, all the above Graph Theory Problems are in, provide the definition for their complexity class and also give justifications as to why the problems belong to respective classes.
Deliverables & Instructions
Write a report describing the GRAPH THEORY problem above and its analysis with all the solutions. Your report should be between 45-60 pages long or limited to 5000 words whichever possible, 12-point Times font and 1 inch margins. You should cite all references using the Harvard Referencing conventions. Your CD must contain the complete documentation including pseudo-codes/algorithms for the above problems.
The Starting and the Ending nodes for BFS, DFS and Dijkstra’s SSSP are A and G respectively.
There will be a short interview with the lecturer to ensure understanding of materials submitted.
General Rules and Guidelines
Using algorithms and code segments from published sources or from others without proper citations will be considered to be plagiarism. You may discuss ideas to solve assignment problems with other class members. However, all assignments are to be thought out, written and implemented individually; direct copying of another's solution will automatically be brought to the attention of the Disciplinary Board.
Level-3 Asia Pacific Institute of Information Technology 2012