CW Exams

[kris manohar]

Hey All,

Finally got my hands on some cw exams. Better late than never. I think we should start posting up solutions we get so we can check with each other to see if we're going okay.

Regards,

Kris

--
If you want it, then  go get it!

[Kyle E. deFreitas]

Guessing no one had solutions to post.

hmmm

--
Kyle deFreitas
St Vincent and the Grenadines
Contact #: 1-784-454-4037
or
1-868-722-5346

[Irwin Williams]

These are some questions and answers I had started compiling:
(and attached are more exams/solutions that we came across).

1. Maximum sum in any contiguous subvector
/* Precondition: x[1..n] is an array of floating-point (real) numbers. */
procedure MaxSumContigVector (x[1..n]: float)

// Returns the maximum sum of a continuous subarray drawn from x.

MaxSoFar := 0.0

MaxEndingHere := 0

i := 1

while i ≠ n + 1 do

MaxEndingHere := max(0.0, MaxEndingHere + x[i])

MaxSoFar := max(MaxSoFar, MaxEndingHere)

i := i + 1

end

return MaxSoFar

source
2. Minimum cost train
//init array
for (int i=0;i<=n;i++)

C[i,0] = INF;

for (int j=1; j<=m;j++)

C[i,j] = j * p[j];

for (int i=2;i<= n;i++){
for (int j=1; j<=m;j++){

if ( j >= D[i] && C[i-1, j] > C[i, j-D[i]] + P[i])

C[i, j] = C[i, j-D[i]] + P[i];

else

C[i, j] = C[i-1, j];

}

}

//to print
void printDistance(int row, int col, int[][] C)
{

if (row ==0 || coll == 0)

return;

if (C[row-1, col] > C[row, col])

printDistance(row, col-D[row], C);

//println(D[row]);

else

printDistance(row-1, col, C);

}

3. Find the Order of the following:

int c=0, i, m, n;

read n

for i= 1 to n{

m = n/i;

for j= 1 to m

c++;

}

Answer: how long does the line “c++” run for? Well, the outer loop runs for n times; the inner loop runs, for n/1 + n/2 + n/3 + n/4 ...  This is equal to j=1n12j which is 2-12 n Thus the inner loop has an Order (1), so the function’s order is O(n).

4. f(n) and g(n) are two functions from the set of natural numbers to the set of non-negative real numbers.

• what is meant by “f(n) is big O g(n)”?

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

if and only if, for sufficiently large values of x, f(x) is at most a constant multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

source

• what s meant by “f(n) is little O g(n)”?

The relation f(x) is little-o of g(x)". Intuitively, it means that g(x) grows much faster than f(x). It assumes that f and g are both functions of one variable. Formally, it states

Or alternatively:

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

if and only if, for each positive constant M, f(x) is at most M multiplied by g(x) in absolute value, for each x, which is large enough. That is, f(x) = o(g(x)) if and only if, for every M > 0, there exists a constant x0, such that

f(n) < cg(n) for all n >= x0

• if the limit, as n tends to infinity of f(n)/g(n) is c, what is the exact asymptotic relationship between f and g if (i) c = 0 and (ii) c = 1

(i) f(n) is little o g(n)
(ii) f(n) is theta g(n)

5. Optimal matrix multiplication
C[i, j] = mini<k<j{C[i, k-1]+C[k, j] + rirkrj+1}

6. North east paths
int NEPaths(ax, ay, bx, by)
{
if (ax == bx || ay == by)
return 1;
else
return NEPaths(ax + 1, ay, bx, by)
+ NEPaths(ax, ay + 1, bx, by);
}

7. Add one to a prime
void addOne(int[] B, int n)
{
int j=n;
while (j > 0 && B[j] == 1)
B[j--] = 0;
if (j > 0) B[j] =1;
}

8. Flowers problem
- Let's assume that dp [i] [j] means the maximum sum of aesthetic values about first i flowers puts in first j vases. Then, since the only choice for the ith flower is whether put or not, the function is obvious: dp [i] [j] = max {dp [i] [j-1], dp[i-1] [j-1] + a [i] [j]}. Limitness is that i <j should be held and record the action "put".
for (i = 1; i <= f; i++)
{
for (j = 1; j <= v-f+i; j++)
{
dp[i][i - 1] =- 32767;
dp[i][j] = dp[i-1][j - 1] + a[i][j];
put[i][j] = false;
if (dp[i][j-1] > (dp[i-1][j-1] + a[i][j]))
{
dp[i][j] = dp[i][j-1];
put[i][j] = true;
}
}
}
//print
void putprint (int i, int j)
{
while (put [i][j]) j--;
if (i> 1)
putprint(i-1, j-1);
if (i == f)
printf ("% d \ n", j);
else printf ("% d", j);
}

9. Prove that the ranks of the nodes in the path from x to y form a strictly increasing sequence.

Let T be a tree resulting from a sequence of unions and finds using “union by rank” and “path compression”.  Let y be the root of T and x a leaf node in T.  
Prove that the ranks of the nodes in the path from x to y form a strictly increasing sequence.
//TODO

10. Strongly connected graph:
http://www.ics.uci.edu/~eppstein/161/960220.html#sca

11. Check for Majority Element in an array
//n^2 solution
int maxpos = 0;
int maxValue = 0;

for each item a in arr
{
   currentMax = 0;
   for each item b in arr
       if (a == b) currentMax++;
   if (currentMax > maxValue)
   {
       maxValue = currentMax;
       maxpos = a;
   }
}
//O(n) solution
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

/* Function to check if the candidate occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}
source

12. Djikstra’s
function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity ;              // Unknown distance function from source to v
       previous[v] := undefined ;         // Previous node in optimal path from source
   end for ;
   dist[source] := 0 ;                    // Distance from source to source
   Q := the set of all nodes in Graph ;
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[] ;
       if dist[u] = infinity:
           break ;                        // all remaining vertices are inaccessible from source
       fi ;
       remove u from Q ;
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) ;
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt ;
               previous[v] := u ;
           fi  ;
       end for ;
   end while ;
   return dist[] ;
end Dijkstra.

13. Floyd-Warshall
procedure FloydWarshallWithPathReconstruction ()
   for k := 1 to n
       for i := 1 to n
           for j := 1 to n
               if path[i][k] + path[k][j] < path[i][j] then
               path[i][j] := path[i][k]+path[k][j];
               next[i][j] := k;

procedure GetPath (i,j)
   if path[i][j] equals infinity then
       return "no path";
   int intermediate := next[i][j];
   if intermediate equals 'null' then
       return " ";   /* there is an edge from i to j, with no vertices between */
   else
       return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);

14. procedure BellmanFord(list vertices, list edges, vertex source)
  // This implementation takes in a graph, represented as lists of vertices
  // and edges, and modifies the vertices so that their distance and
  // predecessor attributes store the shortest paths.

  // Step 1: initialize graph
  for each vertex v in vertices:
      if v is source then v.distance := 0
      else v.distance := infinity
      v.predecessor := null

  // Step 2: relax edges repeatedly
  for i from 1 to size(vertices)-1:
      for each edge uv in edges: // uv is the edge from u to v
          u := uv.source
          v := uv.destination
          if u.distance + uv.weight < v.distance:
              v.distance := u.distance + uv.weight
              v.predecessor := u

  // Step 3: check for negative-weight cycles
  for each edge uv in edges:
      u := uv.source
      v := uv.destination
      if u.distance + uv.weight < v.distance:
          error "Graph contains a negative-weight cycle"

15. Car track problem
Suppose there are n identical cars on a circular track and among them there is enough gasoline for one car to make a complete loop around the track. Show that there is one car that can make it around the track by collecting all of the gasoline from each car that it passes as it moves.

Proof:
If there is a single car (n = 1), and that car has enough gas to make it around the loop, then it can make it around the loop, and we are done.

Assume the statement of the problem is true for n = k cars, and consider a situation with k + 1
cars on the loop.
If we can find a particular car C1 that has enough gas to make it to the next car
C2 then the situation is equivalent to transferring all of C2 ’s gas to C1 and eliminating C2 from the track. With one car eliminated, we know that there is a car that can complete the circuit from the induction hypothesis.

Suppose that no car has enough gas to make it to the next one. Then if each car drove forward as far as it could, there would be a gap in front of each one, so the total amount of gas would not be sufficient for one car to make it all the way around the track. Thus there must be a car that can make it to the next, and the proof is complete.
source

--
Irwin Williams
785-1268
________________________
*I am a software solutions developer.*
Do you see a man skilled in his work?
He will serve before kings; he will not
serve before obscure men.
Proverbs 22:29