CSC 512 Saudi Electronic Algorithm Analysis and Backtracking Technique Report i need anser my assiment in file attched by acadmic CSC 512 Algorithm Analysis and Design King Saud University
College of Computer and Information Sciences
Computer Science Department
CSC 512 Algorithm Analysis and Design
2019-2020
Assignment 3
Due Date: Thursday, December 12th, 2019.
Question 1:
15=8+7
Let us consider the algorithm OptimalBST(P[1..n]) that finds an Optimal Binary Search Tree by
dynamic programming. Prove the following:
1. the time efficiency of OptimalBST is cubic
2. the space efficiency of OptimalBST is quadratic
Question 2
33=10+4+3+3+3+10
A chess rook can move horizontally or vertically to any square in the same row or in the same column
of an n by n chessboard. The problem is to find the number of shortest paths by which a rook can
move from one corner of a chessboard to the diagonally opposite corner by using dynamic
programming. The length of a path is measured by the number of squares it passes through,
including the first and the last squares. We assume that the rows of the chessboard are numbered
from 1 to n bottom up and the columns are numbered from 1 to n left to right. We assume that the rook
is initially located in the lower left corner of a chessboard (that is square (1, 1)).
Let P(i, j) be the number of the rook’s shortest paths from square (1,1) to square (i, j) in the ith row and
the jth column, where 1 ≤ i, j ≤ n. Any such path will be composed of vertical and horizontal moves
directed toward the goal.
1. Give the recurrence on P(i, j), 1 ≤ i, j ≤ n and its initial condition(s)
2. What are the time and space efficiencies of your algorithm?
3. Can the values of P(i, j), 1 ≤ i, j ≤ n, be computed row by row?
4. Can the values of P(i, j), 1 ≤ i, j ≤ n, be computed column by column?
5. Can the values of P(i, j), 1 ≤ i, j ≤ n, be computed diagonal by diagonal?
6. Consider now the instance n=4. Give the table P, that is all entries P(i, j) for 1 ≤ i, j ≤ n.
Question 3 15=10+5
Consider the following Graph:
1. Apply the backtracking technique to find a Hamiltonian circuit of this graph
2. What is the worst complexity of the backtracking algorithm?
Question 4 15=10+5
Consider the Subset Sum problem and the following instance A={1, 3, 4, 5} and d=11
a. Apply backtracking to solve this instance of the subset sum
b. Will the backtracking algorithm work correctly if we consider just one of the
inequalities to terminate a node as non-promising?
Question 5 20=8+12
Consider the traveling salesperson problem (TSP) and the following graph:
a. Apply exhaustive search to find all shortest tours
b. Apply branch-and-bound to solve the TSP.
Purchase answer to see full
attachment