ECE4010 Homework 1

Part I: Programming [75 points]

Visit the blackboard page and download the zip archive.

You need to have Python 3.6 or above installed on your machine

This assignment requires you to complete the implementations of

1. Class StackFrontier

2. Class QueueFrontier

3. solve function defined in Class Maze

Once you’ve complete all the required functions, should be able to run python maze.py

mazeN.txt, where N denote the index of maze in the folder.

For each maze, run your code based on DFS and BFS, respectively. And posted the solution

that is stored in maze.png.

Part II: Written Problem [25 points]

Q1. [5 pts] Between depth first search (DFS) and breadth first search (BFS), which will

find a shorter path through a maze?

Q2. [5pts] The following question will ask you about the below maze. Grey cells indicate

walls. A search algorithm was run on this maze, and found the yellow highlighted path

from point A to B. In doing so, the red highlighted cells were the states explored but that

did not lead to the goal.

Of the four search algorithms discussed in lecture — depth-first search, breadth-first

search, greedy best-first search with Manhattan distance heuristic, and A* search with

Manhattan distance heuristic — which one (or multiple, if multiple are possible) could be

the algorithm used?

Q3. [5 pts] Why is depth-limited minimax sometimes preferable to minimax without a

depth limit?

Q4. [10 pts] The following question will ask you about the Minimax tree below, where the

green up arrows indicate the MAX player and red down arrows indicate the MIN player.

The leaf nodes are each labelled with their value.

a. [5 pts] What are the value of the nodes in the above figure, if we use Minimax?

b. [5 pts] If you are the MAX player, what is your best action (left, middle, or right)

based on the above figure