Once the suffix array is constructed, the short routine shown in Figure 12.50 canbe invoked from Figure 12.32 to create the longest common prefix array.a. In the code, what does rank[i] represent?b. Suppose that LCP[rank[i] ] = h. Show that LCP[rank[i+1] ] h 1.c. Show that the algorithm in Figure 12.50 correctly computes the LCP array.d. Prove that the algorithm in Figure 12.50 runs in linear time.1 /*2 * Create the LCP array from the suffix array3 * @param s the input array populated from 0..N-1, with available pos N4 * @param sa the already-computed suffix array 0..N-15 * @param LCP the resulting LCP array 0..N-16 */7 public static void makeLCPArray( int [ ] s, int [ ] sa, int [ ] LCP )8 {9 int N = sa.length;10 int [ ] rank = new int[ N ];1112 s[ N ] = -1;13 for( int i = 0; i < N; i++ )14 rank[ sa[ i ] ] = i;1516 int h = 0;17 for( int i = 0; i < N; i++ )18 if( rank[ i ]>0)19 {20 int j = sa[ rank[ i ] - 1 ];2122 while( s[ i + h ] == s[ j + h ] )23 h++;2425 LCP[ rank[ i ] ] = h;26 if( h > 0 )27 h--;28 }29 }Figure 12.50 LCP array construction from suffix array
Week 5 2/8/16 energy (ch.3) o great idea: the many different forms of energy are interchangeable, and the total amount of energy in an isolated system is conserved o the great chain of energy scientifically speaking energy related to force Work o force over distance o formula: W = Fd o Units: joules Energy o Ability to do work Power o Rate at which work is done o Equation: P = W/t or (E – f)/ti o Units: watts Basic ideas Energy can be provided/stored in various forms Food is one way to store energy. Our bodies store energy in the form of fat, which can be converted back in terms of low availability of food Other units for energy A calorie is the energy needed to increase the temperature of 1 gram of water be 1 degree Celsius (4.2 J) A kilocalorie (aka food calorie) is the energy needed to increase the temperature of 1kg of water by 1 degree Celsius, this is exactly 1000 small calories
