Problem 1: Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. Example your dictionary is the set {I,like.applespeaches, Professor,Genna then the string "Ilikecherries" does not work while the string IlikeProfessorGennaro" works. Given the run- ning time of your algorithm Problem 2: Given a n x n matrix where all nu nbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1. You can move in 4 directions fron a given cell (i, j), .., we can move to (i + Lj) or (i, j +1) or (i-1,j) or (i,j-1) with the condition that the adjacent cells have a difference of 1. Problem 3: Given two strings strl and str2, find the shortest string that has both str1 and str2 as subsequences