the exam is online and starts at 11:15am on feb 7th
BMIS 530 BMIS 530 Given L=[1,3,4,4,5,7,9,11,14], make a quick conclusion that a PDP answer can never be found. DO NOT apply skiena's algorithm. Given L = [1,1,1,2,2,3,3,3,4,4,5,5,6,6,6,9,9,10,11,12,15], 1. Provide detailed discussion and exact calculation of search space (expression only, no actual number) when a naive brute force is proposed, i.e. try every possible value between 1 to 15. 2. Provide same analysis when a 'smart' brute force is proposed, i.e. only try valid values. Looking the Longest Common Substring Problem: Given two strings X and Y, find the length of the longest common substring. For example X="abcd" Y="bbc", answer is "bc". 1) Propose a 'fast derived' algorithm. Find the size of the search space. Provide Big O. 2) Propose an improved version of (1) Provide Big O. Page 2 of 2 Page 2 of 2