CSE 130  Fall 2009

                               Home Work 2


  0. Final will be a cumulative exam. You  are  supposed  to  know  all
  topics that we studied so far. Go over class notes and study all exam-
  ples. We will do some more examples before Final.

     Whatever we do on Linked Lists will be included in topics for
     final exam.

  1. [3 points] Write a function to calculate the least common  multiple
  of  two  integers  u  and v. You may use the function gcd (see program
  8.6, page 127, or as discussed in class) in this process. The  follow-
  ing identity will come handy.

  lcm(u, v) = (u * v)/gcd(u, v)

  2. [3 points] We studied calculation of square root of x  (a  floating
  point  number)  in class. The same program is given on page 132 of the
  text.  Assuming that function float squareRoot(float x)  is  available
  to you, right a function that calculates and returns fourth (4th) root
  of x.

  3. We studied several sorting algorithms in class.
  (i) [3 points each] Let the unsorted list or array be 7, 1,  9,  10,
  2, 3. Execute bubblesort, selection sort and insertion sort algorithms
  on this list, sorting array in increasing order. Show the array  after
  every  pass.  A pass is one iteration of the outer loop of these algo-
  rithms.
  (ii) [1 points] Are there any in-place swaps done  by  selection  sort
  algorithm? An in-place swap is done when we swap a number with itself.

  4. [4 points] See the recursive  binary  search  algorithm/program  in
  class  notes.  It is not complete, in the sense that it needs a proper
  header with parameters, and correct  return  statements.  Complete  it
  (rewrite  it)  such  that  it can be called from another function with
  appropriate parameters such as binarySearch(A[], 0, N-1, value).  Here
  array  A is the sorted array, 0 is the index of the first element, N-1
  is the index of the last element, and value is a number  that  we  are
  looking  for. This function returns the index of the element, if it is
  on the list else it returns -1.

  5. [2+2 points] Execute the binary search  program/algorithm  for  the
  sorted  array  4, 8, 19, 20, 32, 67, 71, looking for number (i) 19 and
  (ii) 68. Show all steps, calculation  of  midpoint/index,  success  or
  failure at the end, etc.

  6. [3 points] Declare a enumerated type called japCars. The members of
  this type are: Toyota, Honda, Nissan, Suzuki, Subaru and Isuzu.  Use a
  typedef statement to name this type JC.  Declare  a  variable  car  of
  type JC, and initialize it to value Honda.

  SKIP Q7 (below). We did not do this in class.

  7. [4 points] Execute the Towers of Hanoi algorithm for n  =  4  (this
  means  4  discs).  Use A, B, and C for Tower names. Your answer should
  follow the recursive algorithm that we  studied  in  class.  For  your
  answer follow the given format, and write all moves.
  Format: Move disc (number) from Tower (name) to Tower (name).

  8. [6 points] Consider a structure time given as follows.

  struct time
  {
      int hours;
      int minutes;
      int seconds;
  };

  Write a function elapsed_time(time1, time2) which returns the  elapsed
  time  as  a  structure,  by  subtracting time1 from time2. Assume that
  time2 as after time1, and instead of AM/PM we use  0-23  hour  system.
  Both  time1  and  time2  belong to the same day. No change over to the
  next day.

  9. [4 points] Execute the following program  with  pointer  variables.
  What values are printed by two printf statements. Trace this manually.
  If a similar question is asked on the exam, you will have to trace it
  manually. You will not have an option of running it on a computer.

  #include <stdio.h>

  int main(void){
          int x = 12, y, z;
          int *pointerOne, *pointerTwo;

          pointerOne = &x;
          pointerTwo = pointerOne;
          y = *pointerTwo/2;
          printf("x = %d, y = %d\n", x, y);

          *pointerOne = 0;
          pointerTwo = &y;
          z = *pointerTwo + *pointerOne + 4;
          printf("z = %d\n", z);

          return 0;
  }