Assignment 1
Instructions:
● You can do this assignment individually or in a team of two. If you are doing it in a
group, only one submission per group is required. Self enrolled groups are available
on canvas.
● You may submit multiple times until the deadline. Grade penalties will be
imposed for late submissions (see the course outline for the details).
● Always plan before coding.
● For coding questions - Use function-level and inline comments throughout your
code. We will not be specifically grading documentation. However, remember that
you will not be able to comment on your code unless sufficiently documented. Take
the time to document your code as you develop it properly.
● We will carefully analyze the code submitted to look for plagiarism signs,
so please do not do it! If you are unsure about what is allowed, please talk
to an instructor or a TA.
● Make sure that in your answers, you clearly indicate the exact section you are
answering.
● You will submit one .zip file.
o For theoretical questions - Your submission must be formatted as a single
PDF file; other types of submissions (non-pdf, multiple files, etc.) will not be
graded. Your name(s) and student number(s) must appear at the top of the
first page of your submission.
o Please put all your files (pdf + code) in one folder. Compress these into a
single archive named a1.zip and submit it on Canvas before the due date
listed there.
Question 1 [25 marks]: Search Algorithms
Consider the problem of finding the shortest path from a1 to a10 in the following directed
graph. The edges are labelled with their costs. The nodes are labelled with their heuristic
values. Expand neighbours of a node in alphabetical order, and break ties in alphabetical
order as well. For example, suppose you are running an algorithm that does not consider
costs, and you expand a; you will add the paths