COMP341 Assignment 1 Solution

Introduction to Artificial Intelligence
Make sure you read and understand every part of this document
Important: Make sure you go over all the submission instructions at the end of this document before submission. Once you upload your submission, download it to make sure it is not corrupted and it has your latest report/code. You are only going to be graded by your blackboard submission.
Grading
You are given two options about submitting your homework: (1) both code and report, and (2) only report. The second option is given to you in case you are not able to implement the programming part. These options will be graded differently:
Code and Report: The code part and the report will have 2:1 weight ratio in your submission (programming 2/3, report 1/3).
Only Report: The report part will be treated as 1/2 of the total grade. You must credit the code you used and must not submit a code part.
Part 1: Programming
Hints
Always read the comment sections of the given code before starting your implementation. These comments are very useful and they will save you precious time later on.
Part 2: Report
This part includes answering the following questions based on your programs’ output on the given pacman tests. Look specfically at bigMaze and the openMaze for stark comparisons.
Create a PDF file named report.pdf containing your answers for submission. Write your name and your number on the report as well!
Written Q1:
What are some differences between DFS and BFS in terms of path cost and number of expanded nodes?
When and why would you prefer BFS over DFS? When and why would you prefer DFS over BFS?
Written Q2:
What are some differences between UCS and A* in terms of path cost and number of expanded nodes?
When and why would you use UCS over A*? When and why would you prefer A* over UCS?
Written Q3:
Comment on your choice of state in the finding all the corners problem. Why does it allow you to solve the problem?
Written Q4:
Comment on your choice of heuristic in the finding all the corners problem.. Why did you settle on that heuristic? Why is it admissible and consistent?
Written Q5:
Comment on your choice of heuristic in the eating all the dots problem. Why did you settle on that heuristic? Why is it admissible and consistent?
Written Q6:
What are some practical differences between a consistent and an inadmissible heuristic, in terms of path cost and number of expanded nodes? When and why would you prefer an inadmissible heuristic over a consistent one? When and why would you prefer a consistent heuristic over an inadmissible one?
Submission
You are going to submit a compressed archive through the blackboard site. The file should extract to a folder which only contains report.pdf, search.py and searchAgents.py. Other files will be deleted and/or overwritten. Do not submit any code if you only want us to only grade your report.
Submission Instructions
You are fine as long as the compressed archive has the required files within 4 folder levels.
Once you are sure about your assignment and the compressed file, submit it through Blackboard. Do not submit code that does not terminate or that blows up the memory.
Important: Download your submission to make sure it is not corrupted and it has your latest report/code. You are only going to be graded by your blackboard submission.
Best of luck and happy coding!