From: Jie Bao
Time: Sept 12, 2002, 10:47am
To: com_s_472@cs.iastate.edu; com_s_572@cs.iastate.edu
Cc: Dimitris Margaritis
Subject: hint for hw1

Some information about Turing Test ( for problem 1.1):
http://cogsci.ucsd.edu/~asaygin/tt/ttest.html
 
For Problem 1.3, You can think about Godel Theorem:
http://users.ox.ac.uk/~jrlucas/mmg.html

for the last problem:

you should discuss 4 cases for DFS and BFS
1) worst-case space complexity
2) expected-case space complexity
3) worst-case time complexity
4) expected-case time complexity

notes that d is depth of goal and D is the depth of whole tree

Example solutions for expected-case space complexity
Suppose we search the tree from top to bottom and from left to right
i) DFS: best case: the goal node is the left-most node, maximum space required is bd
              otherwise: , maximum space required is bD
   there are b^d nodes at depth d and suppose the goal node is distributed with uniform 
probability . So the expected space requirement is :
     (bd+bD(b^d-1))/(b^d)

ii) BFS: best case: the goal node is the left-most node, maximum space required is b^d
2nd-best case: the goal node is the second to left-most node, maximum space required is b^d+b-1
3rd-bset: the goal node is the 3rd to left-most node, maximum space required is b^d+2b-2
....
worst case: the goal node is the right-most node, maximum space required is b^d+(b-1)(b^d-1)
each case have probability  of 1/(b^d), so the expectation is :
(b^d+b^d-1+b+...+ b^d+(b-1)(b^d-1)) / (b^d) 

final solution for some other cases:
expected-case time complexity
DFS: ((b^(D-d+1)-1)/(b-1) +(d-1)+1 +
          2*(b^(D-d+1)-1)/(b-1)+ # of ancestors of self and "elder brothers"
          ........... +
          (b^(D+1)-1)/(b-1) - (b^(D-d+1)-1)/(b-1))
          /(b^d)
          = (2d(b-1))+(b^d-1)(b^(D-d+1)-1)/(b-1)+1))
BFS: ((b^d-1)/(b-1)+
          (b^d-1)/(b-1)+1+
          (b^d-1)/(b-1)+2+
          ....+
          (b^(d+1)-1)/(b-1)-1 )     / (b^d)
          = (b^(d+1)+b^d-b-1)/(2b-2)

please complete your solution with those hints and explain IN DETAIL how do you get these numbers.

/**
Jie Bao 
Dept of Computer Science
Iowa State University
baojie@cs.iastate.edu
www.cs.iastate.edu/~baojie
1-515-460-5095
**/