# Algorithms

Suppose we are given an undirected graph G=(V,E) in an input file which has the number of nodes and the matrix. We want to preprocess the graph so we can quickly answer a query of the form:Path(i,j) that returns YES if there is a path from vertex to vertex j in G, and NO if there is no path. Your goal is to be able to answer Path(i,j) for any pair i, j in O(1) time.

a) A simple way to solve this problem is to construct an n × n matrix P such that P[i, j] = 1 if there is a path from i to j, otherwise P[i, j] = 0. Describe how to construct such a matrix P.(for this part, don’t worry about the fastest method). Give the complexity analyses of your method.

b) We now want an improved scheme to answerPath(i,j) that only uses O(n) extra space to store the information we use to answer in O(1) time. In addition, we want our preprocessing to be fast.

i) Describe how to do the preprocessing in O(m + n) time (and using O(n) extra space.

ii) Describe how to answer a Path(i,j) query in O(1) time for your method.

Provide details on the design of your algorithm. Explain how your algorithms work step by step andv answer the questions above.

Program call: mySM inputfile

Input format: First you will have a number which denotes the number of nodes (n) and second an (nxn) matrix in the file.

Tentang Majikan:
( 6 ulasan ) new york, Turkey

ID Projek: #1601280

msabouri

\$30 USD dalam 5 hari
(70 Ulasan)
5.5

## 20 pekerja bebas membida secara purata \$82 untuk pekerjaan ini

dobreiiita

Hi, I am JAVA expert and can surely help you here, Thank You

\$50 USD dalam 0 hari
(246 Ulasan)
6.7
WebDesignall

Hi We can help you we have the skills and experience to make the project successfully, please check our profile, reviews and PM for more details Best regards

\$150 USD dalam 3 hari
(24 Ulasan)
6.2
diepbp

\$50 USD dalam sehari
(118 Ulasan)
6.2
samitXI

\$50 USD dalam 0 hari
(89 Ulasan)
6.2
kevinxiaozi

Dear sir, I am strong in C++/java programming especially in algorithm implementation. I am proficient in Graph theory and algorithms. I have deep insight into Floyd-Warshall, Dijkstra, Breadth First Search, Depth Fi Lagi

\$30 USD dalam 0 hari
(43 Ulasan)
5.6
buzzcoder

\$70 USD dalam 2 hari
(44 Ulasan)
5.5
Alexod

\$250 USD dalam 5 hari
(19 Ulasan)
5.4
pkcoder

Hi sir. I am a qualified programmer. i can do this task. Kindly check pmb. Thank you

\$35 USD dalam 0 hari
(33 Ulasan)
4.9
duchuyctlk

Hi. I am good at Algorithm Design/Analysis and Data Structure. I have experience in C# too. Code and description are available. I can handle it, please check Inbox. Best regards.

\$75 USD dalam sehari
(44 Ulasan)
4.6
monumichael

\$50 USD dalam 3 hari
(14 Ulasan)
4.2
CodingWhiz

I am very proficient in Java, algorithms, and graph theory. I already know how to solve this problem. Please view my profile for previous feedback.

\$50 USD dalam 3 hari
(7 Ulasan)
4.2
Etcherator

This is a classical algorithms problem. I can do it for you with a full detailed implementation in 1 day.

\$30 USD dalam sehari
(4 Ulasan)
3.6
kikoqiu

I can do this.

\$100 USD dalam sehari
(3 Ulasan)
3.6
Launey36

Programmer Need We looking programmer in our account creating section. yah oo, gma il, ai m, hotma il, crai glist, facebook, twitter, myspace, mybookyear etc Account creating section need following knowledg Lagi

\$30 USD dalam sehari
(0 Ulasan)
0.0
jacksaninfotech

\$220 USD dalam 5 hari
(0 Ulasan)
0.0
VXt7E05Wr

Pls check PMB.

\$250 USD dalam sehari
(0 Ulasan)
0.0
JackGD

Hi, I've worked a lot with pathfinding in graphs and I can easily do it for you.

\$40 USD dalam sehari
(0 Ulasan)
0.0
musaali91

So you just want all of this written in a text file right? The complexity analysis of how to make the nxn matrix which tells if path(i,j) exists. and for part b, you want a memory efficient method and also how to do th Lagi

\$50 USD dalam sehari
(0 Ulasan)
0.0
MICPassionate

I research on algorithms. So I can do it. I can give u details.

\$30 USD dalam sehari
(0 Ulasan)
0.0