1. 0-1 Knap Sack Problem (algorithm to solve the Knap-Sack problem (sack size =K ) is given below to help you). Array S[ ] has the size of items available for selection. Given an integer K (the size of a knap sack) and n items of different sizes such that ith - item has an integer size S[i], find a selection of subset of items whose sizes sum to exactly K, or determine that no such subset exists. No fractional selection is permitted K=16//knapsacksize//itemsS[1]=1,S[2]=4,S[3]=6,S[4]=7,S[5]=8 able is given below to help you. In the table, Enter a ' l ' in the table if a solution exists for a sack size and includes the item. Enter a ' O ' in the table if a solution exists for a sack size and does not include the item. Enter a-- in the table if a olution does not exist for a sack size. First two rowa of the table have been ompleted to help you get started. 2. Find the Longest Increasing subsequence for the following sequence by completing the table (array) L[i] where the element L[i] has the value of the longest increasing subsequence terminating at number with index i. Highlight the numbers which are in the longest increasing subsequence. 3. Perform Depth-First Search for the following graph starting from vertex A. Whenever there is a choice of vertices pick the vertex which is alphabetically first. Classify each edge as a forward edge, back edge, tree edge, or cross edge. 4. Single Source Shortest Path Problem. Suppose Dijkstra's Algorithm is run on the following graph starting from the vertex A. Complete the table showing the intermediate distance values at each iteration