Yioop - PHP Search Engine

Apr 5 In-Class Exercise.

Post your solutions to the Apr 5 in Class Exercise here.

Best, Chris

Post your solutions to the Apr 5 in Class Exercise here. Best, Chris

-- Apr 5 In-Class Exercise

((resource:17820443_1231478860298308_243334986_o.jpg|Resource Description for 17820443_1231478860298308_243334986_o.jpg))

-- Apr 5 In-Class Exercise

 Algorithm(x,y,i)
 >> Z was chosen non-deterministically for the sake of what to show.

 ----i = 3
 1-4-3
 ----i = 2 
 *1-2-2 = #FOUND
 *2-4-2 >>
 ----i = 1
 **2-3-1 = #FOUND
 **3-4-1 = #FOUND

 Therefore 2-4-2 = #FOUND
 Therefore 1-4-3 = #FOUND

(Edited: 2017-04-05)

Algorithm(x,y,i) >> Z was chosen non-deterministically for the sake of what to show. ----i = 3 1-4-3 ----i = 2 *1-2-2 = #FOUND *2-4-2 >> ----i = 1 **2-3-1 = #FOUND **3-4-1 = #FOUND Therefore 2-4-2 = #FOUND Therefore 1-4-3 = #FOUND

-- Apr 5 In-Class Exercise

 -> (1,4,3)
 for z = 1
 computing (1,4,3) needs result of (1,1,2) & (1,4,2)
 -> (1,4,3) (1,1,2)
 computing (1,1,2) needs result of (1,1,1)
 -> (1,4,3) (1,1,2) (1,1,1)
 computing (1,1,1) needs result of (1,1,0) = true
 and so (1,1,1) is also true and (1,1,2) is also true.
 We can replace (1,1,2) with (1,4,2)
 -> (1,4,3) (1,4,2)
 computing (1,4,2) with z'=1 needs result of (1,1,1) and (1,4,1)
 -> (1,4,3) (1,4,2) (1,1,1)
 computing (1,1,1) needs result of (1,1,0) = true
 and so (1,1,1) is also true
 replace (1,1,1) with (1,4,1)
 -> (1,4,3) (1,4,2) (1,4,1)
 computing (1,4,1) needs result of (1,1,0) and (1,4,0)
 (1,1,0) = true. But (1,4,0) = false. so (1,4,1) = false
 Pop (1,4,1) and compute (1,4,2) for z'=2 which needs result of (1,2,1) and (2,4,1)
 -> (1,4,3) (1,4,2) (1,2,1)
 computing (1,2,1) needs result of (1,1,0) and (1,2,0). Both of which are true.
 So (1,2,1) is also true. Replace (1,2,1) with (2,4,1)
 -> (1,4,3) (1,4,2) (2,4,1)
 computing (2,4,1) with z = 1 needs result of (2,1,0) and (1,4,0).
 We will get false results till z	 = 3 which needs result of (2,3,0) and (3,4,0)
 Both return true so (2,4,1) = true. Which makes (1,4,2) also true. Which makes (1,4,3)
 also true.
 So PATH(1,4,3) = true.

-> (1,4,3) for z = 1 computing (1,4,3) needs result of (1,1,2) & (1,4,2) -> (1,4,3) (1,1,2) computing (1,1,2) needs result of (1,1,1) -> (1,4,3) (1,1,2) (1,1,1) computing (1,1,1) needs result of (1,1,0) = true and so (1,1,1) is also true and (1,1,2) is also true. We can replace (1,1,2) with (1,4,2) -> (1,4,3) (1,4,2) computing (1,4,2) with z'=1 needs result of (1,1,1) and (1,4,1) -> (1,4,3) (1,4,2) (1,1,1) computing (1,1,1) needs result of (1,1,0) = true and so (1,1,1) is also true replace (1,1,1) with (1,4,1) -> (1,4,3) (1,4,2) (1,4,1) computing (1,4,1) needs result of (1,1,0) and (1,4,0) (1,1,0) = true. But (1,4,0) = false. so (1,4,1) = false Pop (1,4,1) and compute (1,4,2) for z'=2 which needs result of (1,2,1) and (2,4,1) -> (1,4,3) (1,4,2) (1,2,1) computing (1,2,1) needs result of (1,1,0) and (1,2,0). Both of which are true. So (1,2,1) is also true. Replace (1,2,1) with (2,4,1) -> (1,4,3) (1,4,2) (2,4,1) computing (2,4,1) with z'' = 1 needs result of (2,1,0) and (1,4,0). We will get false results till z'' = 3 which needs result of (2,3,0) and (3,4,0) Both return true so (2,4,1) = true. Which makes (1,4,2) also true. Which makes (1,4,3) also true. So PATH(1,4,3) = true.

-- Apr 5 In-Class Exercise

we start with, (1, 4, 3) for z = 1, we take (1, 1, 2) and (1, 4, 2)

  for (1, 1, 2) we take, 
  z = 1, thus we get (1, 1, 1) and (1, 1, 1)
    for (1, 1, 1) we take,
    z = 1, thus we get (1, 1, 0) and (1, 1, 0)
    Since 1 = 1, we return True.

  Similarly, for both (1, 1, 1), we return True since there is a path of at most length 2 between them.

(1, 1, 2) is True from recursion.

  Now for (1, 4, 2) we take,
  z = 1, this we get (1, 1, 1) and (1, 4, 1)

    (1, 1, 1) returns True but (1, 4, 1) returns False.

  Since (1, 4, 1) returns False, return False.

for z = 2, we take (1, 2, 2) and (2, 4, 2).

  for (1, 2, 2) we take,
  z = 1, thus we get (1, 1, 1) and (1, 2, 1).

    (1, 1, 1) returns True. (calculated earlier)

    for (1, 2, 1), we take (1, 1, 0) and (1, 2, 0)
    Since 1 = 1, (1, 1, 0) returns True and (1, 2, 0) also returns True.
    Hence return True.

  Since both (1, 1, 1) and (1, 2, 1) returns True, return True.

  for (2, 4, 2), 
  z = 2, we take (2, 2, 1) and (2, 4, 1)

    Since 2 = 2, (2, 2, 1) returns True.

    for (2, 4, 1) we take, (2, 2, 0) and (2, 4, 0)
    Since (2, 4, 0) returns False, return False.

  Since (2, 4, 1) returns False, return False.

  z = 3, we take (2, 3, 1) and (3, 4, 1)

    Since there is a path of length 1 between 2 and 3, return (2, 3, 1) = True
    Since there is a path of length 1 between 3 and 4, return (3, 4, 1) = True

    return True.

Return True. Hence there exists a path between 1 and 4.

we start with, (1, 4, 3) for z = 1, we take (1, 1, 2) and (1, 4, 2) for (1, 1, 2) we take, z = 1, thus we get (1, 1, 1) and (1, 1, 1) for (1, 1, 1) we take, z = 1, thus we get (1, 1, 0) and (1, 1, 0) Since 1 = 1, we return True. Similarly, for both (1, 1, 1), we return True since there is a path of at most length 2 between them. (1, 1, 2) is True from recursion. Now for (1, 4, 2) we take, z = 1, this we get (1, 1, 1) and (1, 4, 1) (1, 1, 1) returns True but (1, 4, 1) returns False. Since (1, 4, 1) returns False, return False. for z = 2, we take (1, 2, 2) and (2, 4, 2). for (1, 2, 2) we take, z = 1, thus we get (1, 1, 1) and (1, 2, 1). (1, 1, 1) returns True. (calculated earlier) for (1, 2, 1), we take (1, 1, 0) and (1, 2, 0) Since 1 = 1, (1, 1, 0) returns True and (1, 2, 0) also returns True. Hence return True. Since both (1, 1, 1) and (1, 2, 1) returns True, return True. for (2, 4, 2), z = 2, we take (2, 2, 1) and (2, 4, 1) Since 2 = 2, (2, 2, 1) returns True. for (2, 4, 1) we take, (2, 2, 0) and (2, 4, 0) Since (2, 4, 0) returns False, return False. Since (2, 4, 1) returns False, return False. z = 3, we take (2, 3, 1) and (3, 4, 1) Since there is a path of length 1 between 2 and 3, return (2, 3, 1) = True Since there is a path of length 1 between 3 and 4, return (3, 4, 1) = True return True. Return True. Hence there exists a path between 1 and 4.

-- Apr 5 In-Class Exercise

work tape : PATH (1,4,3)

we need to compute PATH(1,1,2) && PATH(1,4,2)

push (1,1,2) on the work tape

work tape : (1,4,3) (1,1,2)

we need to compute PATH(1,1,1), PATH(1,1,1)

push PATH(1,1,1) on the work tape

work tape : PATH(1,4,3) PATH(1,1,2) PATH(1,1,1)

computation of PATH(1,1,0) returns true

therefore PATH(1,1,2) ==> true

now remove PATH(1,1,2) and push PATH(1,4,2) to the worktape

work tape : PATH(1,4,3) PATH(1,4,2)

computing: PATH(1,1,1) and PATH(1,4,1) push PATH(1,1,1) to work tape

work tape : PATH(1,4,3) PATH(1,1,1)

from above PATH(1,1,1) is true so we remove it and push PATH(1,4,1) tovwork tape

work tape : PATH(1,4,3) PATH(1,4,2) PATH(1,4,1)

computing PATH(1,4,1)

PATH(1,1,0) and PATH(,1,4,0)

PATH(1,1,0) return true and PATH(1,4,0) returns false

now for z'' = 2 we compute PATH(1,2,1) and PATH (2,4,1) push PATH(1,2,0) to the

work tape

work tape : PATH(1,4,3) PATH(1,4,2) PATH(1,2,1)

PATH(1,2,1) from the algorithm will evaluate to true

so we remove PATH(1,2,1) and push PATH(2,4,1) to the work tape

work tape : PATH(1,4,3) PATH(1,4,2) PATH(2,4,1)

to compute PATH(2,4,1) => PATH(2,1,0) and PATH(1,4,0) both of which are false

then we compute PATH(2,2,0) => true and PATH(2,4,0) => false

then we compute PATH(2,3,0) and PATH(3,4,0) both of which are true

which makes PATH(2,4,1) => true

which in turn makes PATH(1,4,2) => true and so we get PATH(1,4,3) as true

(Edited: 2017-04-05)

'''work tape''': PATH (1,4,3) we need to compute PATH(1,1,2) && PATH(1,4,2) push (1,1,2) on the work tape '''work tape''': (1,4,3) (1,1,2) we need to compute PATH(1,1,1), PATH(1,1,1) push PATH(1,1,1) on the work tape '''work tape''': PATH(1,4,3) PATH(1,1,2) PATH(1,1,1) computation of PATH(1,1,0) returns true therefore PATH(1,1,2) ==> true now remove PATH(1,1,2) and push PATH(1,4,2) to the worktape '''work tape''': PATH(1,4,3) PATH(1,4,2) computing: PATH(1,1,1) and PATH(1,4,1) push PATH(1,1,1) to work tape '''work tape''': PATH(1,4,3) PATH(1,1,1) from above PATH(1,1,1) is true so we remove it and push PATH(1,4,1) tovwork tape '''work tape''': PATH(1,4,3) PATH(1,4,2) PATH(1,4,1) computing PATH(1,4,1) PATH(1,1,0) and PATH(,1,4,0) PATH(1,1,0) return true and PATH(1,4,0) returns false now for z'' = 2 we compute PATH(1,2,1) and PATH (2,4,1) push PATH(1,2,0) to the work tape '''work tape''': PATH(1,4,3) PATH(1,4,2) PATH(1,2,1) PATH(1,2,1) from the algorithm will evaluate to true so we remove PATH(1,2,1) and push PATH(2,4,1) to the work tape '''work tape''': PATH(1,4,3) PATH(1,4,2) PATH(2,4,1) to compute PATH(2,4,1) => PATH(2,1,0) and PATH(1,4,0) both of which are false then we compute PATH(2,2,0) => true and PATH(2,4,0) => false then we compute PATH(2,3,0) and PATH(3,4,0) both of which are true which makes PATH(2,4,1) => true which in turn makes PATH(1,4,2) => true and so we get PATH(1,4,3) as true

-- Apr 5 In-Class Exercise

Given graph G: 1->2->3->4->5->6 i=log6 = 3 (1,4,3) for z=1, (1,1,2) and (1,4,2)

	for z=1
	(1,1,1)
		for z=1
		(1,1,0)
		True
	(1,1,1) and (1,4,1)
		z=1
		(1,1,0) and (1,1,0) and (1,4,0)
		True 	and True	and False
	return false
	
	for z=2
	(2,1,1)
		for z=1
		(2,1,0) and (1,2,0)
		False  and  False
		return false
	
	for z=3
	(1,3,1) and (3,4,1)
		z=1
		(1,1,0) and (1,3,0)
		True   and  False
		return false

If we try in similar fashion the equation works for z=2

	(1,2,2) and (2,4,2)
	z=1
	(1,1,1) and (1,2,1)
	(1,1,0) and (1,1,0) and (1,2,0)
	return true
	for z=3 
	(2,3,1) and (3,4,1)
	z=3
	(2,3,0) and (3,3,0) and (3,3,0) and (3,4,0)
	return True

=>PATH(1,4,3) is True

Given graph G: 1->2->3->4->5->6 i=log6 = 3 (1,4,3) for z=1, (1,1,2) and (1,4,2) for z=1 (1,1,1) for z=1 (1,1,0) True (1,1,1) and (1,4,1) z=1 (1,1,0) and (1,1,0) and (1,4,0) True and True and False return false for z=2 (2,1,1) for z=1 (2,1,0) and (1,2,0) False and False return false for z=3 (1,3,1) and (3,4,1) z=1 (1,1,0) and (1,3,0) True and False return false If we try in similar fashion the equation works for z=2 (1,2,2) and (2,4,2) z=1 (1,1,1) and (1,2,1) (1,1,0) and (1,1,0) and (1,2,0) return true for z=3 (2,3,1) and (3,4,1) z=3 (2,3,0) and (3,3,0) and (3,3,0) and (3,4,0) return True =>PATH(1,4,3) is True