[go: up one dir, main page]
Scribd
Upload
34 views3 pages

Sol - As1 Spring 2024 - CS607

Solution of assignment #1 spring 2024 CS607 Artificial Intelligence

Uploaded by

engr.anwarkhaliq
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views3 pages

Sol - As1 Spring 2024 - CS607

Solution of assignment #1 spring 2024 CS607 Artificial Intelligence

Uploaded by

engr.anwarkhaliq
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Artificial Intelligence (CS607) Total marks = 20

Assignment # 01 Deadline
th
29 of April 2024
Spring 2024

Question No 01
Marks (10)

Consider the following tree, use simple search algorithm (given on page# 24 of handouts) and apply the

Depth First Search (DFS) strategy. The starting node is 1, and the goal node is 7. You are required to fill

out only the given Table.

SOLUTION:

Sr No Q - List Visited List

1 1 1

2 2, 3 1, 2, 3

3 4, 5, 3 1, 2, 3, 4, 5

4 5, 3 1, 2, 3, 4, 5

5 7, 8, 3 1, 2, 3, 4, 5, 7

6 8, 3 1, 2, 3, 4, 5,7

This is just one possible traversal order for DFS. Depending on how the DFS algorithm is implemented

(e.g., exploring left or right child first), the order of visiting nodes might differ slightly. However, all

nodes will eventually be visited in a DFS of a binary tree.


Question No 02
Marks (10)

Breath First Search (BFS) is a memory hungry search strategy which means it requires a lot of memory
whiling processing a problem even having a reasonable and moderate complexity. It is primarily due to
the branching factor that increase the number of ways to search for the solution (goal/target).
Now, consider that we have a tree width the branching factor of 4 and depth (or height) 12, while each
node requires 16 bytes storage. If the Breath First Search (BFS) is applied to this tree, then calculate the
memory required for this search.

Note: Provide complete steps while calculating the memory storage.

SOLUTION:

1. Total Nodes: We have a tree with branching factor (b) of 4 and depth (d) of 12. The total
number of nodes (N) can be approximated using the formula for a geometric series:
 N ≈ (b ^ (d+1)) - 1 / (b - 1)
 N ≈ (4 ^ 13) - 1 / 3 ≈ 6143

2. Memory per Node: Each node requires 16 bytes of storage.

3. Maximum Memory Usage: BFS needs to keep track of unexpanded nodes at the deepest level
(level 12 in this case).
 Memory ≈ Number of nodes at level 12 * Memory per node
 Memory ≈ 4 ^ 12 * 16 bytes/node ≈ 262,144 bytes (assuming very large numbers)

Therefore, the maximum memory required by BFS for this tree is approximately 262,144 bytes.

You might also like