CSE 110   Fall 2009

                                 Solutions to Ex-1



   (1) (a) N (b) N (c) Y (d) Y  (e) PC

   (2)    Get n // n > 0                          We gave full credit if you
          set sum = 0, set i = 4                  wrote a correct Java Program
          while (i <= n) do
             sum = sum + i                        This works with i = 0 as well.
             i = i + 4
          end-of-while
          print sum

   (3) (i) Here begin = 1, and end = 9, so mid = (1+9)/2 = 5 (integer division)
        So Sally would be first compared to name Marsha.

       (ii) Since Sally is after Marsha in the alphabetical order, we search the
       right half. Here begin = 5+1 = 6, and end = 9. mid = (9+6)/2 = 15/2 = 7.
       So the next step would compare Sally to name Sue. No credit for two answers.

   (b) Do outer loop of selection sort once, input list is 25, 1, 12, 4, 8, 17, 20

       First pass: swap 25 and 20;   List is:     20, 1, 12, 4, 8, 17, 25
       
       (i) First pass does 6 comparisons (find largest)

       (ii) Zero (0) in_place swaps are done.

   (4) (a) An algorithm that does not have a conditional (an if statement)
        AND an iteration (e. g. while loop) is a straight-line algorithm.
        Or the one with just input, output and assignment statements.
        
       (b) Assignment statement

       (c) do-while, repeat-until or any post-test loop

       (d) Memory space or storage space
     
       (e) theta (2^n), we gave credit to n! as well.

   (5) (a) 7, 15 (b) Initially, i = 0 and and n > 0. So we do the first
       iteration.  It is easy to see that during every iteration of the loop
       i goes up just by 1, but n goes up by 2.  So n will always be > i.
       So the condition of while-loop will never become false, and loop
       will be executed for ever (will not end).

       (c) A situation where we do a lot of searches. A lot means thousands.
       It pays to have the data sorted in the long run.

   (6) (i) theta (nlogn) (ii) theta (n^3) (iii) theta (n)   Theta is required.

       (b) Here we have to choose one of the above 3 functions. Although this
       was not explicitly said, usually it is understood when it is part of the
       same question.   The slowest growing function is n + 25000.

   (7) (a) N (b) No matter where minimum is on the list, we still have to go
        through the entire list, comparing minimum_found_so_far to other
        elements of the list.
      
        Confusion: Some students assumed the list is in order. Here we are
        modifying the find_largest algorithm. The input is assumed to be NOT
        sorted. We do not need an algorithm to find the minimum of a sorted
        list.  Also n = 1, or n = 2 is not the best case, as we cannot assign
        any specific value to n. Best case should be for general/any  n.

       (c) Worst case complexity is theta(n). We need to look at entire list.

   (8) (a) (i) 3 (ii) True (c) 4.5 (d) 1.0  (partial credit for 1)

       (b) (int)(x) + y There is only one expression. If you wrote additional
       answers, 1 point was deducted.

       (c) (i) There is no error. This is a case of nested if statements.
               These two if's can be on the same line.

           (ii) @ is a special character not allowed in an identifier.

           (iii) There is no or in Java. It should be ||.

   (9) This program uses a boolean variable found. It can be given one of two
       values, true or false. This should be in lower case. found = Yes or No
       is not correct. This is a program, not  pseudo-code. We must follow
       all restriction of Java language. Also some students used found = 0;
       Not correct. Next they did, found = found + 1; Again not correct. This
       is a boolean variable. You cannot use it in addition operation.

       At the end, some students wrote, System.out.println(found); This is
       not correct either. We want answer Yes or No. It must be an if-else
       statement. We gave a lot of partial credit for all these mistakes.

       The question has been graded twice. We are not going to regrade it.
       Please do not ask for it.

      // Exam-1 Java program.  Oct 9, 2009

           public class Exam_1

            {
               public static void main (String[ ] args)
         
                  {
                     int count, input, i; boolean found;

                     i = 0; found = false  // it should be in small letters.
                     // This is a Java program. found = No is not correct.
                        found = 0; is not correct either.

                     count = Console.readInt ("Type in number of integers: ");
                                              // Prompt string is required.

                     while ((i < count) && (!found))

                        { 
                          input = Console.readInt ("Type in an integer: ");

                          if (input == 0) found = true;  // small case.

                          i = i+1;
                        }
                                          
                     if (found) System.out.println ("Yes");
                       else System.out.println ("No");
                  }
          }