as an exampleif we are searching for the pattern "textbookwith at most three mismatches in the string "data structures txtborpk"we find match (insert an echange an to an odelete pgive an (mnalgorithm to solve the approximate string matching problemwhere |pand |sone form of the knapsack problem is as followswe are given set of integersa an and an integerk is there subset of whose sum is exactly ka give an algorithm that solves the knapsack problem in (nktime why does this not show that npyou are given currency system with coins of (decreasingvalue cn cents give an algorithm that computes the minimum number of coins required to give cents in change give an algorithm that computes the number of different ways to give cents in change consider the problem of placing eight queens on an (eight-by-eightchess board two queens are said to attack each other if they are on the same rowcolumnor (not necessarily maindiagonal give randomized algorithm to place eight nonattacking queens on the board give backtracking algorithm to solve the same problem implement both algorithms and compare the running time in the game of chessa knight in row and column may move to row < < and column < < (where is the size of the boardprovided that either | and | or and | | knight' tour is sequence of moves that visits all squares exactly once before returning to the starting point if is oddshow that knight' tour cannot exist give backtracking algorithm to find knight' tour consider the recursive algorithm in figure for finding the shortest weighted path in an acyclic graphfrom to why does this algorithm not work for general graphsb prove that this algorithm terminates for acyclic graphs what is the worst-case running time of the algorithmlet be an -by- matrix of zeroes and ones submatrix of is any group of contiguous entries that forms square design an ( algorithm that determines the size of the largest submatrix of ones in for instancein the matrix that followsthe largest submatrix is four-by-four square