75/ Arad C 118 71 Oradea Zerind 140 Timisoara 111 70 75 Dobreta 151 Lugoj Sibiu Me hadia 120 80 99 Rimnicu Vilcea 97 Fagaras 146 138 Cralova Pitesti 211 101

Neamt Q 85 87 90 Giurgiu Bucharest lasi 92 142 Urziceni 98 Vaslui Hirsova 86 Eforie Straight-line distance b Bucharest Arad Bucharest Craiova Dobreta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind 366 160 242 161 176 77 151 226 244 241 234 3.80 10 193 253 329 80 199 374 1. (100 points, undergraduate student) Please use the uniform cost search method to find a path from Oradea to Bucharest in Romania Map shown in the following figure. Major tree expansion steps must be shown clearly in detail. (10 bonus points, undergraduate student) Please make your new search method to find a path from Oradea to Bucharest in Romania Map shown in the following figure. Major steps must be shown clearly in detail.