Some problem solving to revise COMP115/WCOM115

Problem 1: Determining if a given integer is prime

What is a prime number?A number more than 1 that is divisible only by 1 and itself.

1
2
3
4
5
6
Is 37 a prime number?
Is 37 divisible by 2? No. So we carry on
...
Is 37 divisible by 36? No. This means 37 is not divisible by
any integer besides 1 and 37.
Thus, 37 is a prime number.

1
2
3
4
5
6
Is 77 a prime number?
Is 77 divisible by 2? No. So we carry on
...
Is 77 divisible by 7? Yes. This means 77 is divisible by
another integer besides 1 and 77.
Therefore, it's not a prime number.

NOTE: You can see that this is a kind of violation algorithm, where we continuously look for a violation (existence non-trivial divisor) to the problem in context (primality). As soon as a violation is encountered, our algorithm can exit with failure (false) status. Only if no violations are found, can the algorithm exit with success (true)status. The algorithm is,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
INPUT: Integer n
PROCESS:
if n is less than 2
begin condition
	OUTPUT false (integers less than 2 are not primes)
end condition

for integer candidate from 2 to n-1
begin loop
	if n is divisible by candidate
	begin condition
		OUTPUT false (as a non-trivial divisor was found)
	end condition
end loop

The equivalent Java code would be,

Note: we really need to check only until square root of n instead of n-1.

The way we can call this function from another function (say main) is as follows,

Problem 2: Determining if a String contains any space

As opposed to the prime checking example, this is a validation algorithm, where we look for a validation, and as soon as one is found, we can return true. If there is no validation found, then, at the end, we can return false.

Problem 3: Calculating the total of all items of an integer array

This is an accumulation algorithm. We go through each item of the array, and add it to a variable that stores the total.

Once we know how to do this, we can apply this to other problems such as,

Finding total of all even numbers in an integer array

Define a method that when passed an array, returns the sum of all even numbers in the array

Solution

Finding total of all positive items in an integer array

Define a method that when passed an integer array, returns the sum of all positive numbers in the array. Solution is not provided for this problem.

Finding total of all items above a certain value in an integer array

Define a method that when passed an integer array and another integer (say val), returns the sum of all items numbers in the array that are more than val. Solution is not provided for this problem.

Finding total of negative items in the first half of the array

Define a method that when passed an integer array, returns the sum of all negative numbers in the first half of the array. For example, if array is {-6, -8, -1, -2, 9}, return -14, and if array is {-6, -5, -8, -12, -1, 9}, return -19.

Solution