Skip to main contentCal State San Bernardino / [CNS] / [Comp Sci Dept] / [R J Botting] >> [CSci202] >> algorithms
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Contact] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Wed May 2 07:55:58 PDT 2007

Contents


    Sample Algorithms written in pseudo-code/structured English

      Algorithm to swap the values of x and y using a temporary variable t

       set t = x
       set x = y
       set y = t

      Algorithm to print out a file called n.

       Open the file with name n for input
       if(the file couldn't be opened)
       	report the error
       	return
       //end if
      
      
       while( get the next character)
       	output the next character
       //end while
      
      
       Close the file
      
      
       End Algorithm
      Can you translate the above algorithm into a program in C++?

      Algorithm to print out a file called n with double spacing of the lines.

       Open the file with name n for input
       if(the file couldn't be opened)
       	report the error
       	return
       //end if
      
      
       while( get the next line)
       	output the next line
       	output a blank line
       //end while
      
      
       Close the file
      
      
       End Algorithm
      Can you translate the above algorithm into a program in C++?

      Binary Search for the square root of a number a

       if(a<0 or e<=0)
       	throw an error
       //end if
      
      
       set x=0.5*a.
       set y=0.  // here y <= sqrt(a) <= x
       while( abs(x-y)>e )
           // here y <= sqrt(a) <= x
       	  set m = (x+y)*0.5
       	  if( m*m < a)
           // here m <= sqrt(a) <= x
             set y=m
          else
           // here y <= sqrt(a) <= m
             set x=m
          //end if
       //end while
      
      
       return y.
      
      
       //end Newton's algorithm
      Try the above algorithm, by hand, with a=50 and e=0.001.

      Can this algorithm find the cube root of a number?

      Newton's algorithm to calculate the square root of a with error less than e.

       if(a<0 or e<=0)
       	throw an error
       //end if
      
      
       set x=0.5*a.
       set y= (x*x + a)/(2*x).
       while( abs(x-y)>e )
       	set x=y.
       	set y= (x*x + a)/(2*x).
       //end while
      
      
       return y.
      
      
       //end Newton's algorithm
      Try the above algorithm, by hand, with a=50 and e=0.001.

      Can you code the above algorithm as a C++ function with header double newt(double a, double e) ?

      Algorithm to multiply positive integers x and y by using addition and subtraction only.

       if( x < 0 or y < 0)
       	throw an error
       	exit
       //end if
      
      
       set integer z = 0.
       for( integer i = 1 to y)
       	set z = z + x.
       //end for
      
      
       return z.
       //end algorithm
      
      Does the above algorithm work?
      

      Can you code it into C++? Should you code it in C++? Explain your answer!

      The Bubble Sort algorithm for sorting a vector or array of items into increasing order.

       Set n to the number of items in the vector or array.
       Repeat the following n times.
       	for each item in turn, except the last one
       		if the item is bigger than the next one
       			swap the two items
       		//end if
       	//end for
       //end repeat
      
      
       //end bubble sort algorithm
      What algorithm, on this page, does the above algorithm use?

      Are there any improvements you could make to the above algorithm?

      The selection sort algorithm

       Find the biggest item in the unsorted data.
       Swap the biggest item with the last item of the unsorted data
      
      
       Repeat the above steps with the unsorted data reduced by one
      
      
       //end algorithm
      
      Can you write an algorithm that finds the biggest item in some unsorted data?
      

      Can you write the above so it is easier to understand and code?

      The insertion sort algorithm

      Exercise for the reader....

    . . . . . . . . . ( end of section Sample Algorithms written in pseudo-code/structured English) <<Contents | End>>

    Abreviations

  1. TBA::="To Be Announced", something I have to do.
  2. TBD::="To Be Done", something you have to do.
  3. Dia::="A free Open Source Diagramming tool for Linux, Windoze, etc. ".

End