/ [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

# 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`

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?