Just the programing question, not the theory part.
A4_W20 University of Regina CS 340 Assignment #4 Written Part: Graph Algorithms [22pts] Exercise 1 : exercise 10.3 page 456 (10.3 page 518 on 4th ed.)[6pts] A file contains only colons, spaces, newlines, commas, and digits in the following frequency :colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217). Construct the Huffman code. Exercise 2 : exercise 10.28 page 457 (10.29 page 520 on 4th ed.)[4pts] What is the optimal way to compute A1 A2 A3 A4 A5 A6, where the dimensions of the matrix are : A1: 10 x 20, A2: 20 x 1, A3: 1 x 40, A4: 40 x 5, A5: 5 x 30, A6: 30 x 15. Exercise 3 : exercise 10.29 page 457 (10.30 page 520 on 4th ed.)[6pts] Show that none of the following greedy algorithms for chained matrix multiplication work. At each step 1. Compute the cheapest multiplication 2. Compute the most expensive multiplication 3. Compute the multiplication between the two matrices Mi and Mi+1 such that the number of columns in Mi is minimized (breaking ties by one of the rules above). Exercise 4 : exercise 10.46 page 459 (10.47 page 522 on 4th ed.)[6pts] The one-dimensional circle packing problem is as follows. You have N circles of radius r1, r2, ..., rn. These circles are packed in a box such that each circle is tangent to the bottom of the box, and are arranged in the original order. The problem is to find the order of circles that will lead to the optimal (minimum) width of the minimum-sized box. The figure below (left picture) shows an example with circles of radius 2, 1, 2 respectively. The minimum-sized box has width 4 + 4 SQRT(2). Hint: Use the Pythagorean theorem to compute the distance between the centers of two consecutive circles (see the above right figure). Programming Part: Search Algorithms Applied to the 8-Puzzle [78pts] Write a program that, given the following user input: • an initial configuration, • and a search strategy, returns: • a series of states (path) from the initial to the goal configuration, • and the number of generated nodes (states). The following strategies should be implemented: • depth first search. • breath first search. • best first search with each of the following heuristics : o depth in the search space + number of tiles out of place. o depth in the search space + minimum number of moves to reach the goal state. o depth in the search space + the heuristic H defined below. H is a combination of two mesures: 1. totdist: the "total distance" of the eight tiles in Pos (Pos is a board position) from their "home squares". We use the Manhattan distance (see below for the definition of the Manhattan distance) to calculate the distance of each tile from its home square. For example, in the starting position of the puzzle (a) in the figure below, totdist = 4. 2. seq: the "sequence score" that measures the degree to which the tiles are already ordered in the current position with respect to the order required in the goal configuration. seq is computed as the sum of scores for each tile according to the following rules: o a tile in the centre scores 1; o a tile on a non-central square scores 0 if the tile is, in the clockwise direction, followed by its proper successor. o such a tile scores 2 if it is not followed by its proper successor. For example, for the starting position (a) of the puzzle in the figure below, seq = 6. The heuristic estimate, H, is computed as: H = totdist + 3*seq The "Manhattan distance" between 2 squares S1 and S2 is the distance between S1 and S2 in the horizontal direction plus the distance between S1 and S2 in the vertical direction. We want to minimize the length of solutions. Therefore, we define the cost of all the arcs in the state space to equal 1. Three examples starting positions are defined as follows. Three starting positions for the eight puzzle: (a) requires 4 steps; (b) requires 5 steps ; (c) requires 18 steps. We assume that the goal position is the following: Marking Scheme: total = 78% 1. Readability (program style) : 6% o Program easy to read, o well commented, good structured (layout, indentation, whitespace, ...) and designed(following the top-down approach). 2. Compiling and execution process : 6% o program compiles w/o errors and warnings o robustness : execution w/o run time errors 3. Correctness : 66% o code produces correct results (output)