A random walk is represented by a vector beginning with 0 and where each subsequ

Question

A random walk is represented by a vector beginning with 0 and where each subsequent entry in the vector is attained from the previous entry by adding a random choice of either 1 or -1. For example, a random walk might begin (0-1 0 1 2 3 2 3 2 3 4 3 2 3 4 5]. Write a function rand_walk 1 that takes as input a positive integer n and as output returns a length n random walk. Our example is a length 16 random walk, because it contains 16 total entries. Write a function rand_walk2 that takes as input a positive integer n and as output returns a random walk that stops the first time it reaches an entry of n or -n. For example, the above random walk example stopped the first time it reached 5 or -5. An example of an undirected graph and its corresponding adjacency matrix is shown. An undirected graph is a collection of n vertices numbered 1 to n, some of which may be connected by an edge. The corresponding adjacency matrix is an nxn matrix associated to an undirected graph. The adjacency matrix has a 1 in position (i,j) if there is an edge connecting i to j, and it has a 0 in position (i, j) if there is no edge connecting i to j. Write a function make_adj that takes two inputs, a number n (the number of vertices in the graph) and a list of the edges in the graph, and returns as output the corresponding nxn adjacency matrix. Include comments describing how the list of edges is represented; it is your choice how to represent it. Write a function find_nbrs that takes as input an adjacency matrix A and a number m and as output returns a vector containing the vertices joined to vertex m by an edge. For example, for the adjacency matrix shown above, if the input number m = 4, then the output would be the vector [2 3 5].

Explanation / Answer

Q3.
n = input("Enter the number of vertices")
// I am taking list of edges as aan array. I will ask user to enter the edge defined. The array will always have even numbers.
//Enter q to quit
edges = zeros
adj_matrix= zeros(n)
for i from 0 to n-1 do
l=input("Enter edges")
if =strcmp(l,'q')
break
else
edges[i]=l
end_for

for j from 0 to size(edges)
if(edges[j] && edges[j+1])
   adj_matrix[j][j+1]=1
end_for

Now the adj_matix is our adjacency matrix ! :)

Q4.
m = input("Enter the vertex")
x = []; //Resultant vector
end=0;
//Now scan your adjmatrix for that vertex

for j from 0 to size(adj_matrix)
  if(adj_matrix[m][j]==1)
   x(end+1) = j;

// Now x will contain the list of edges emerging from vertex m.

Q1. Lets us random function for it. For example, if random number gives us an even number, we use 1, else we use -1.

So,

number1 = rand(1)
if(number1%2==0)
add=1;
else
add=-1;

Now,


n = input("Enter your random walk list size")
x = []; //Resultant vector
end=0;
x(end)=0;
//Now scan your adjmatrix for that vertex

for j from 0 to n
  number1 = rand(1)
  if(number1%2==0)
  x(end+1)=x(end)+1
  else
  x(end+1)=x(end)-1
  
//Now x will be your random walk vector


Q2.
n = input("Enter your random walk stop point")
x = []; //Resultant vector
end=0;
x(end)=0;
//Now scan your adjmatrix for that vertex

for j from 0 to n
  if(x(end)==n || x(end)== -n)
  break;
  number1 = rand(1)
  if(number1%2==0)
  x(end+1)=x(end)+1
  else
  x(end+1)=x(end)-1
  
// Now x will be your rand_walk2 list!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.