Algorithms and run time

1. Give an efficient algorithm for computing each of the following measures, with a proof of correctness and analysis of the running time in each case. (a) Longest common subsequence. A subsequence of a string is obtained by taking a subset of its characters without changing their order. (For example, ART is a subsequence of ALGORITHM.) A common subsequence of a pair of strings x and y is a string that is a subsequence of both x and y. Consider the length of a longest common subsequence of x and y. (b) Edit distance. The edit distance between x and y is the smallest number of single-character insertions, deletions, or substitutions that suffice to change x into y. (c) Edit distance with transpositions. The edit distance with transpositions between x and y is the smallest number of single-character insertions, deletions, or substitutions, or transpositions of two adjacent characters, that suffice to change x into y. (For example, the edit distance with transpositions between NOSE and ONCE is 2, whereas their edit distance is 3.)

2. Processing sheet metal. You run a company that processes sheet metal. You have a price list indicating that a rectangular piece of sheet metal of dimensions xi × yi can be sold for vi dollars, where i ∈ {1, 2, . . . , n}. Starting from a raw piece of sheet metal of dimensions A×B, you would like to make a sequence of horizontal or vertical cuts, each of which cuts a given piece into two smaller pieces, to produce pieces from your price list (and possibly some additional worthless scrap pieces). Design an algorithm that maximizes the total value of the pieces obtained by some sequence of cuts. Your algorithm should return both the maximum value that can be obtained and a description of the cuts that should be made to achieve it. Assume that the numbers A, B, and xi , yi , vi for i ∈ {1, 2, . . . , n} are all positive integers. Demand for everything on your price list is high, so you can produce any number of copies of any of the pieces. Prove that your algorithm is correct and analyze its running time.

I am currently working through a self taught algorithm book and have NO idea how to start these problems. Any help is welcome