Find Jobs
Hire Freelancers

Java Depth First Search

$30-250 USD

Completed
Posted over 8 years ago

$30-250 USD

Paid on delivery
DepthFirstSearch (DFS) : parent node; discovery/finishing time; parenthesis theorem. Requirements: implement/update specific methods for the DFS of a graph; for at least 2 graphs (1 being the provided one), show the DFS order of vertices in the graph, and for each node, specify its parent node in the search (the node from which the currect node was reached). Moreover, display for each node the discovery and finishing time, to check that the Parenthesis Theorem holds true. Approach:You may start from the DFT in the textbook and do the appropriate changes. For counting the dfs time, you should set a global counter (let’s name it time), which is set to 0 in the moment the search starts with the root vertex. At any moment the search starts with a new vertex (that is, justafter entering a new dfs) the counter has to be incremented by one; also it has to be incremented by one when the search from the current node ends (just before exit a dfs). For each node, calculate also the discovery and finishing time; for doing this, you may use two arrays (let’s name them d[] for discovery and f[] for finishing). The discovery time of a given vertex v receives the value of the counter just when enter to the dfs for that vertex (that is d[v]=time, before incrementing time), and the finishing just before exit from that dfs (that is f[v]=time, before decrementing time). Parentheses Theorem: In any depth first search, for any 2 vertices u and v, one of the following 3 conditions holds true: The intervals [d[u], f[u]] and [d[v], f[v]] are completely disjoint; The [d[u], f[u]] interval is completely contained within interval [d[v], f[v]], and u is a descendant of v in the dfs tree; The [d[v], f[v]] interval is completely contained within interval [d[u], f[u]], and v is a descendant of u in the dfs tree; Design and implement a driver to show the following (check for 2 graphs; 1 is provided, including the starting vertex): Display the dfs starting from a specified vertex; Display the discovery/finishing time for each node in the graph; Display the parent node for each node in the dfs; Show the Parentheses Theorem holds true, by mentioning the specific condition in each case (this has to me manually calculated and added in the documentation). Input data: You should test your application and include the tests in your documentation for at least two graphs; one is mandatory to be this one provided below. It is represented in the G = (V, E) representation, where V is the vertices set, and E is the edges set. Please note that our graph is a directed one (that is edges have directions, thus, the presence of an (u, v) edge does not imply (v, u) is also present in the graph). Nevertheless, this has no impact on the algorithm and its implementation. The dfs should start with vertex 1. V= {1, 2, 3, 4, 5, 6, 7} E= {1, 2}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {4, 5}, {5, 1},{6, 4}, {6, 7} Deliverables: You should submit (1) all the source (.java) files, (2) a screenshot sample file (the output displayed while running your application to show the required functionalities) and (3) a documentation file. It should contain the design decisions, test plan, the output for the two runs, and the condition met by the Parentheses Theorem in each case. The documentation should be no more than five pages in length and no less than two pages. The font size should be 12 point, the page margins one inch, and the paragraphs formatted with single spaced. Any figures, tables, equations, and references should be properly labeled and formatted using APA style. Wrapp all the files in a single .zip archive
Project ID: 8177084

About the project

12 proposals
Remote project
Active 9 yrs ago

Looking to make some money?

Benefits of bidding on Freelancer

Set your budget and timeframe
Get paid for your work
Outline your proposal
It's free to sign up and bid on jobs
Awarded to:
User Avatar
Hi christine, I would like to do this project please. Let me know if you are interested so I can start. Thanks.
$35 USD in 3 days
4.9 (1032 reviews)
7.5
7.5
12 freelancers are bidding on average $67 USD for this job
User Avatar
Hi there! I'm a Professional java Developer and Data analyst for a well known Software House in Islamabad, Pakistan named "PacSquare". I'm doing freelancing to get most out of my free time. Please consider my bid. I assure you that you'll get my best services and Satisfaction in return. Thanks a million! Maher Shahmeer
$45 USD in 2 days
5.0 (111 reviews)
5.9
5.9
User Avatar
I have 5 years of programming experience. I can help you solve this problem. When you work with me you will feel very comfortable.
$50 USD in 3 days
4.8 (50 reviews)
4.8
4.8
User Avatar
Hello I am .Net Software Developer working on Web & Desktop applications (C# expert developer) Languages , i can on : C#.Net, VB.Net, Android, Java, C, C++, PHP, Java script, JQuery, Ajax, HTML etc... Database : SQL SERVER / Oracle / MS-Access / Text My good points: - Full support. - Master Degree in Computer Science - 3+ Years of experience - Delivered before time - My good habit is to leaving comment on important lines. ----------------------------------------------------------------------- if you have any confusion, Feel free to ask Lets discus your project
$155 USD in 3 days
5.0 (17 reviews)
4.3
4.3
User Avatar
I can handle this task easily.
$35 USD in 2 days
5.0 (3 reviews)
2.5
2.5
User Avatar
I have a good knowledge of algorithms and graphs theory. Will do great job. Contact me if you have questions.
$77 USD in 1 day
5.0 (1 review)
1.8
1.8
User Avatar
I am student of second year of Theoretical Computer Science. I use DFS very often to solve many graphs problems so I know that algorithm. The Parentheses Theorem is easy to prove as DFS finds spanning tree in the graph and then it is trivial to show that works.
$30 USD in 1 day
5.0 (1 review)
1.2
1.2
User Avatar
Hello, I'm interested in doing this project. I'm a computer science student at senior standing and have done projects like this in the past. I've had to do a similar project in JAVA so I know what needs to be done. Seeing that it is an assignment I understand the importance of following good style and would be sure to do it the way your instructor expects. I'm a good communicator and would make sure to ask before assuming anything and would keep you updated on my progress. If you have any questions or concerns please let me know, Thank you.
$115 USD in 4 days
5.0 (1 review)
0.7
0.7
User Avatar
I am good at data structures and algorithms. I implemented the algorithm from cormen book. My topcoder rating for SRM is 1312. I can do it by Saturday. Will not ask for any advance milestone payments .
$55 USD in 2 days
0.0 (1 review)
0.0
0.0
User Avatar
A proposal has not yet been provided
$111 USD in 5 days
0.0 (0 reviews)
0.0
0.0
User Avatar
A proposal has not yet been provided
$50 USD in 7 days
0.0 (0 reviews)
0.0
0.0

About the client

Flag of KOREA, REPUBLIC OF
Seoul, Korea, Republic of
5.0
22
Payment method verified
Member since Mar 3, 2014

Client Verification

Thanks! We’ve emailed you a link to claim your free credit.
Something went wrong while sending your email. Please try again.
Registered Users Total Jobs Posted
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Loading preview
Permission granted for Geolocation.
Your login session has expired and you have been logged out. Please log in again.