Algorithms



Group: Undergraduate / Graduate

Name / Id-4:

(Submit in hard copy)

Artificial Intelligence/ Intro CSE 4301/5290 Fall 2016

Home Work on Search and Constraints Points UG:35/Grad:43 Time 110 min Closed Book, except for the Grad Questions

QA/

On question 1 part e, is the suggested pruning only for the given input of {a,b,c,t} or should it be a generalized pruning technique for all inputs?

::Generalized pruning technique(s).

problem 1 in quiz 1. The data set has four elements, if I use them to take a DFS, can I use an element repeatly? For example, If I pick (a) to take first search, can I use a again in next step, (aa)?

::yes, words may have repetition of letters.

For grad q12, in the a overlap b during c and a overlap-Inv d during c statements, do those statements mean

I.  (A overlaps b) during c so the result of the overlap is the first part of the during; or

II.  A overlaps b & b during c

::The second one. Draw as an input graph first with two arcs.

Question 8 on the take home exam has two nodes labeled as D.  Based on the relationship data, I am assuming that the bottom right node should be labeled C.  Please confirm.

::You are correct, constraints show what it should be. I fixed it now.

Do you want our answers to show our thought process as we work through the problem or only show the answer unless directly asked to show all work?  I am working on question 10 to derive the spatio-temporal relations for 3 time intervals and am figuring out that my attempt at the solution is incomplete and need to add to it in order to get the complete answer.

::Some short explanations should be ok, but I designed question not to have subjective long answers. Not exactly sure what are you asking on Q10.

I'm having a bit of trouble understanding what I need to do for Q3. It seems to me that the first part, Q3, and the third part, Q3b, are asking the same thing. Can you clarify?

:: Q3a – just go with the flow, show what the values within each internal nodes (blank boxes) should be.

Q3b – now show which branches will be pruned off because of alpha-beta pruning, which calls will not be made within DFS (going from left through right). I changed the wording on 3b a little bit now.

I have a confusion in the first question. Is it possible that the letters could be repeated or there will only be unique letters in the word?

If the letters could be repeated then the number of leafs will be 64, and I cannot fit all the nodes on one sheet. Is it OK if I draw the search tree like the one attached.

::not necessarily unique. no need to the draw whole tree if you cannot, i need to see the understanding more than accuracy.

for the (a) part do you want us to list down all the words, or just explain the algorithm?

:: use actual dictionary to list the words

I have a question about Q12. In Q12, what is the meaning of the comma between (A overlap B during C) and (A overlap-inv D during C), does it mean "or" or "and"?

::There is really no meaning! I want you derive A-->C from given constraints.

::Consistency algorithms have no concern for finding any solution (satisfying assignment on nodes)

Q1. Input: a set of letters {a,b,c,t}, and a function dictionary(s) that returns T/F to check if a string s exists in the English dictionary; Output: all valid words constructed out of the input sets.

Task: (a) construct words up to size 3 by Depth First Search. [8]

(b) Draw the search tree.

(c) How many possibilities exist (# leaf nodes)?

(d) What is the worst-case or asymptotic complexity of the search, for n letters and d maximum size of all words?

(e) Can you suggest a way to prune the search tree?

Q2. Modify the following graph with [g(Rimmnicu-Pitesti)=110, and g(Pitesti-Bucharest)=110], (g is actual distance traveled along the road between the pair of nodes). Draw the A* search tree for traveling from Arad to Bucharest (with the heuristic function f=g+los, los is the line of sight distances as on the table on the right hand side). [5]

[pic]

Q3. Adversarial search: On the minimax game tree below cross out the branches removed by alpha-beta pruning assuming left to right traversal. [Ref: UCB, F-2014-2c] [6]

Q3a. Write the value at each internal node without alpha-beta pruning.

Q3b. Show pruned branches with alpha-beta pruning turned on.

Q4. Intelligent Search: If f(s), g(s) and h(s) are admissible heuristics, then which of the following are also guaranteed to be admissible heuristics: [Ref: UCB, F-2014-2a] [8]

a. f(s) + g(s) + h(s)

b. f(s)/6 + g(s)/3 + h(s)/2

c. max(f(s), g(s), h(s))

d. min(f(s), g(s), h(s))

e. f(s)/3 + g(s)/3 + h(s)/3

f. f(s)*g(s)*h(s)

g. min(f(s), g(s) + h(s))

h. max(f(s), g(s) + h(s))

Q7. Is the following network Arc-consistent? Path-consistent? [2]

Q8. Run the PC-2 algorithm over the following network to make it Path-consistent. Show the Queue from each iteration starting with the initial Queue. [5]

Hint: Initial Q =(triangles are (A,D,C), (A,B,C), (A,B,D), (B,D,C)}

Note: The queue may have just the ids of nodes as 3-tuples;

3-Tuples are directed as per the PC-2 algorithm, i.e., how ik and jk are used to filter the arc on ik;

Absent arcs do have constraints - they implicitly have all possibilities, e.g., AC initially (on input) has {() , (), (), ()}, comma means OR here;

Hope you understand means A=1;

PC algorithms filter only arcs not domains, although PC-2 uses domain of intermediate node (k) domain;

First step of PC-2: = pop(Q);

Next step: use constraints on AD, domain of D, constraints on DC to filter constraints on AC;

Queue now is, Q = {(A,B,C), (A,B,D), (B,D,C)};

Has AC changed from it was before? Yes, then push all its associated triangles to Q, they are (A,D,C) and (A,B,C), but (A,B,C) is already there, so, do not push it in;

Queue now is, Q ={(A,B,C), (A,B,D), (B,D,C), (A,D,C)}

….

I am primarily asking you to show me the Queue status from each iteration, but a few more details on actions, e.g., picture of the network from each iteration will elucidate your steps.

Q9. Suppose an AC iteration makes a node empty. Instead of stopping if it runs to the end (until nothing changes any more) what will happen? [1]

Grad Q10. Compose time-interval relations Overlap and During, showing graphically (with three time-intervals) the resulting relations of composition. Feel free to use my slides or materials on the Internet. [2]

Grad Q11. Explain in one sentence, why Arc Consistency is inapplicable in time-interval network. [1]

Grad Q12. Derive step-by-step the relation(s) between a pair of time-intervals A and C in a 4-node time-interval network {A overlap B during C, A overlap-inv D during C, A ?? C}. Feel free to use my slides or materials on the Internet. [5]

-----------------------

-

-

-

-

-

-

-

-

-

-

-

-

-

-

15

13

2

11

8

1

5

4

0

6

7

3

{r,b}

B

A`" B

B`" C

{r}

{r}

C

A

{4, 8}

()

()

{1,5}

D

A

()

()

()

(A≠ B

B≠ C

{r}

{r}

C

A

{4, 8}

()

()

{1,5}

D

A

()

()

()

()

{3,7}

D C

{2,6}

()

()

B

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download