Task - code a small collection of graph algorithms

Assignment Help Data Structure & Algorithms
Reference no: EM132310314

Assignment - Algorithms on Directed Graphs

Overview - Your task is to code a small collection of graph algorithms:

1. Shortest paths.

2. DAG testing.

3. DAG Hamiltonian path testing.

4. Connected component search.

5. Strongly connected component search.

6. Topological Sort.

The Code - You are provided with a number of C++ files, the one you will be assessed on is directed_graph_algorithms.cpp. The six methods present in the skeleton are the entry point for the tests. To support this there is a directed_graph.hpp file, which includes a fully working implementation of a directed graph. Note that it is somewhat different from the assignment 1 specification, so make sure you familiarise yourself with it. You are also provided with a main.cpp to do any testing you like. The run button will compile and execute main.cpp, the submit button will run graph_algorithms.cpp against the tests.

You may modify any of these files as you see fit, as long as the tests still execute, apart from adding additional libraries, though you have an extended collection of libraries compared to assignment 1.

As with the first assignment, you should be able to complete the assignment within the graph_algorithms.cpp file (though you are not restricted to this), but you will likely need to add extra functions, perhaps extra classes, so on and so forth.

In a folder you can also view the testing code. This is not the copy that is executed, it's just there for your edification. If any bugs or mistakes in the tests are discovered, the actual tests may be altered, so the code here should only be taken as a guide (hopefully a good guide, but nonetheless).

The Algorithms - As mentioned in the overview, you are to implement six graph based algorithms. In rough order of difficulty, they are:

  • Shortest path
  • DAG testing.
  • DAG Hamiltonian path testing.
  • Topological Sort.
  • Connected component search.
  • Strongly connected component search.

This ordering may vary quite a bit, depending on how you approach the problems however, so take some time to think carefully how you will solve each one.

Attachment:- Assignment Files.rar

Reference no: EM132310314

Questions Cloud

Conducting individual performance evaluations : Identify four rules that should be followed when conducting individual performance evaluations.
What does it mean to be a human being and a human becoming : UNCC300 HUMAN DIGNITY-If you were asked to explain what Human Rights are, what would you say? What connection is there between Human Rights and Human Dignity?
Explain the use and function of each structure : Complete Part 2, Historical and Social Context: In a paragraph of at least 8-10 sentences, highlight key similarities and differences between the four structure
Discuss the problem related to healthcare cost : Healthcare cost is a major concern in public and private healthcare facilities since it consumes huge sums of money from the government.
Task - code a small collection of graph algorithms : Algorithms on Directed Graphs - Your task is to code a small collection of graph algorithms: Shortest paths, DAG testing, and DAG Hamiltonian path testing
Consider the many customs that are involved in social events : After reviewing the PowerPoint and chapter readings for this week, consider the many customs that are involved in social events.
Where does advocacy fit in your life : UNCC300-PRINCIPLES OF ADVOCACY- Analyse the challenges with realising aspirations of the common good in your professional community, locally and globally.
Discuss about how to prevent malpractice claims : You are the risk manager of a hospital and have been asked to make a speech to doctors and nurses about how to prevent malpractice claims.
Describe nurse role in protecting patient health information : How does the issue of patient confidentiality impact your professional practice as a nurse? Describe the nurse's role in protecting patient health information.

Reviews

len2310314

5/22/2019 10:33:10 PM

Hi I had given you ass1 but did not get full solution it was just 3 outputs working out of 19, and first tutor was not able to solve anything and second one did half work not even half and expert couldn’t fix the problem. For this assignment I need someone very good in data structure and C++ if you have quality expert please tell me other vise I would go somewhere else for solution.

len2310314

5/22/2019 10:33:04 PM

This ordering may vary quite a bit, depending on how you approach the problems however, so take some time to think carefully how you will solve each one. As these are described in the lectures, I will not add additional clutter here about their function or details (but you can of course as questions). Functionality will be marked exclusively by the tests, and constitutes 70% of the total mark (note that the marks for the tests add up to 70 - so they give you the percentage you will get as well). Design will be marked in your Week 12 tutorial by your tutor and constitutes 20% of the total mark. It does not depend on the functionality of your code. You may be asked questions by your tutor to help them test your understanding of your code.

len2310314

5/22/2019 10:32:58 PM

It will be marked qualitatively against the following rubric: Distinction - The design shows a high degree of understanding of how to use data structures to achieve a goal efficiently, and demonstrate some evidence that the design does not use unnecessary resources. The design should be clean and efficient. High Distinction - The design demonstrates a high degree of understanding of data structures and how to efficiently employ them to build algorithms that not only meet technical goals, but support maintenance and future development. Style will also be marked in your Week 12 tutorial by your tutor and constitutes 10% of the total mark. It will be marked qualitatively against the following rubric: Excellent formatting and variable naming. Excellent, judiciously employed comments that explain the code without just repeating the code.

len2310314

5/22/2019 10:32:51 PM

Marking Schedule - All being well, assuming you submit before the deadline and attend your Week 12 tutorial (in the class you are actually enrolled in - exceptions will only be made for cases where attendance at your enrolled tutorial is impossible), we aim to return the marks for the assignment within a week of the tutorial. However, we reserve the right to delay this schedule should technical problems arise.

len2310314

5/22/2019 10:32:47 PM

Submission - You will submit your work with the "submit" button on Ed. No other submissions will be accepted. You are welcome to develop your code elsewhere, if that suits your workflow, but remember it must compile and run on Ed. We are using the g++ compiler set to C++17 standard for this assessment. However code that compiles with clang++ should also work with g++ (unless you're doing something weird - so check first!).

Write a Review

Data Structure & Algorithms Questions & Answers

  Describe how algorithm works for adjacency matrix

All vertices according to their type (head, neck, shoulder, hip, front foot or rear foot). Note that as adjacency matrix has n2 entries, you can't scan entire matrix in O(n) time. Describe how algorithm works.

  What is the worst-case running time of algorithm a

Algorithm A executes an O(logn)-time computation for each entry of an n-element array. What is the worst-case running time of Algorithm A?

  Create a cpp program that receives in input a weighted graph

In this assignment, you will create a C++ program that receives in input a weighted graph and groups its nodes in the required number of clusters.

  Define the data structure array

Define the data structure array. Include uses; what represent the name of the array; importance of the index value; naming of the variables bundle within the array.

  Identify the closed loop system

Identify the closed loop system used in controlling an Industrial process and describe the method of operation of the control loop components.

  Can you design a hybrid data structure

Arrays are fast at jumping quickly to a given element, whereas linked lists are fast at insertion after a given element.

  What is the role of an if statement in control structures

What is the role of an if statement in control structures? What are the similarities and differences between single alternative structures, dual alternative structures, and case structures

  Sharing a large computer file

Assume you are sitting at desk at office and using your laptop computer. The boss calls an emergency meeting for you and many colleagues, and asks everyone to bring his or her laptop computer.

  Algorithm-find schedule to obtain maximum amount of profit

Give an algorithm to find schedule which obtains maximum amount of profit, assuming that all processing times are integers between 1 and n.

  Create a doubly linked list class named linkeditemlist

Create a doubly linked list class named LinkedItemList that implements the following interface. Write a program to thoroughly test all of the methods of your LinkedItemList class.

  Show how the following values would be stored by machines

Show how the following values would be stored by machines with 32-bit words, using little endian and big endian format. Assume each value starts at address 016. Draw a diagram of memory for each, placing the appropriate values in the correct (and ..

  Determine the order of insertions

Determine the order of insertions with this set of numbers that will result in a perfectly balanced BST(Binary Search Tree) and show the result of a preorder traversal of this tree.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd