Objective: To deepend the understanding of time and space complexity in search algorithms and deciding on suitable algorithms for a given problem.
Type your answers, but you can draw any illustrations by hand (if so you can send the scanned document).
1) 30pts –Answer the following using the general Tree Search algorithm (remove front node from the fringe/queue – goal test – expand).
Reminder: You can use the following equality for compactness:
1 + b + b2 + … bd = (bd+1-1)/(b-1)
a) 15pt - How many nodes are visited (chosen from the queue, goal tested and expanded) in the worst case using Breadth-First search, when the solution is at depth d, and the branching factor is b, and the depth of the maximum branch is m?
Give a formula.
…………………………………………………………………………………………..
b) 15pt- How many nodes are generated (added to the queue as a result of expanding the parent) in the worst case using Breadth-First search, when the solution is at depth d, and the branching factor is b, and the depth of the maximum branch is m?
…………………………………………………………………………………………..
2) 45pt – You are given the problem of finding whether 6-degrees of separation holds between a particular 2 people in the world. E.g. given two people – say you and your favorite celebrity - the software should decide whether they are connected in at most 6 friendship edges (e.g. you-f1-f2-f3-f4-f5-celebrity).
Let`s assume you have the list of all friendships for all people in the world and that everyone has exactly b=100 friends and that there are 6 billion people in the world.
18pts) State whether the following algorithms are complete (if there is a up to 6-degree path, does it find it?) and optimal (defined here as ‘does it find the shortest path connecting two people’) for this problem.
12pts) If an algorithm is BOTH complete AND optimal, comment on its time and space complexity with a one line summary about its suitability (e.g. “will take too much time/space: O(b^d)” ). If an algorithm would take too much time or space to be feasible, indicate as such; if it is suitable but is an overkill, you should indicate that also.
Algorithm
Complete
(answer as Yes or No)
Optimal
(answer as Yes or No)
Feasibility
(add a one line comment)
Breadth first search
Depth first search without repeated state checking
Depth first search with repeated state checking
Depth limited search DFS with a depth limit of …………
Iterative deepening DFS
Bidirectional search
15pts) Which blind search algorithm (among the ones listed above) would be best for this problem? Explain your answer. Consider space, time complexities and completeness and optimality.
If two algorithms are the same or similar, you may choose the one which is easier to implement or state that they are both as good / suitable.
