AI-2022spring

Homeworks

Homework 1 (part A) - Chapter 3 - Breadth-first search (BFS) tree

This is not a programming activity. Tracing the breadth-first search (BFS) algorithm for a problem results in a BFS tree. Here is an example BFS tree. Below is a map of India highlighting some of the international airports in the country. Nick wants to go to Amritsar from Chennai. In PAPER, draw a BFS tree for the graph of airport cities with starting node as Chennai (C).

Homework 1 (part B) - Chapter 3 - Implement the breadth-first search (BFS) algorithm

With the help of the code blocks provided below, implement the BFS algorithm (in Python) to find the shortest path from Sibiu to Bucharest in the following map. Note that in a standard BFS algorithm/implementation, we ignore the connection weights.

Queue basics in Python:

# Initializing a queue 
queue = []  
# Adding elements to the queue 
queue.append('a') 
queue.append('b') 
queue.append('c') 
# Print
print(queue) 
# Removing elements from the queue 
print("\nElements dequeued from queue") 
print(queue.pop(0)) 
print(queue.pop(0)) 
print(queue)

Representing a graph using dictionary (values are lists of neighbors):

graph = {}
graph['Sibiu'] = ['Fagaras', 'Rimnicu Vilcea']
graph['Fagaras'] = ['Sibiu', 'Bucharest']
graph['Rimnicu Vilcea'] = ['Sibiu', 'Pitesti', 'Craiova']
graph['Pitesti'] = ['Rimnicu Vilcea', 'Craiova', 'Bucharest']
graph['Craiova'] = ['Rimnicu Vilcea', 'Pitesti']
graph['Bucharest'] = ['Fagaras', 'Pitesti', 'Giurgiu']
graph['Giurgiu'] = ['Bucharest']

Shortest path using BFS:

def shortest_path_BFS(graph, start, goal):
  To Do:
  To Do:
   

# Call shortest_path_BFS
shortest_path_BFS(graph, 'Sibiu', 'Bucharest')

Expected output:

['Sibiu', 'Fagaras', 'Bucharest']

Homework 2 - Chapter 5 - Alpha-beta pruning

This is not a programming activity, you will solve it in paper (or in computer, if you prefer). For the following game tree show the values of α and β for all the non-leaf nodes (task 1) and show which nodes/sub-tree will be pruned (task 2) by the Alpha-Beta pruning algorithm. Assume that MAX plays first at node A.

Clarification: Please process nodes from left to right. Also show the values of v. Show how v, alpha, beta values are updated, i.e., do not directly write the values of alpha, beta, and v.

Homework 3 - Chapter 25 - Implement convolution operation

In this activity, you will implement the convolution operation. Your implementation will detect edges in an image. You are required to implement your convolution function and NOT use existing libraries. Please use the my-cat.csv as your input. Your task is to complete the convolution2D() function in the code below. Hint: You will need to multiply each input pixel (3x3 neighbor grid) of the input 2D array image2D with the input filter kernel3x3 to obtain the output 2D array convolved2D. Note: If you use existing libraries such as scipy.signal.convolve2d, you will not receive any points for your submission.

import seaborn as sns
import matplotlib.pyplot as plt
import numpy as np

def convolution2D(image2D, kernel3x3):
  convolved2D = np.zeros((len(image2D)-2, len(image2D)-2))
  # ToDo: Write your code here...

  return convolved2D

image2D = np.loadtxt('my-cat.csv', delimiter=',')
sns.heatmap(image2D, cmap='gray')
plt.title('Original image - Size = ' + str(image2D.shape))
plt.show()

edge_detect_filter_3x3 = np.array([[-1, -1, -1], [-1, 8, -1], [-1, -1, -1]])

for i in range(2):
  convolved_image = convolution2D(image2D, edge_detect_filter_3x3)
  sns.heatmap(convolved_image, cmap='gray')
  plt.title('Convolution iteration ' + str(i) + ' - Size = ' + str(convolved_image.shape))
  plt.show()
  image2D = convolved_image

Expected output: