Computing Insights for Teachers

Some Practice Problems

Please consider the following problems. They are meant to test familiarity with some language features.

If you have any questions about the quiz, primes or any programming language features (ie if statements, loops, procedures/functions, recursion etc.) please let me know and we can point you to some background material to get you warmed up.

Implement the following functions/procedures/methods using the programming language of your choice You must use the suggested algorithm/approach.

1. IsPrime(integer n)

   Background: An number n > 1 is prime if and only if its only divisors are 1 and itself.
   Input: n an integer which is greater than 1
   Output: returns true if n is a prime number and false otherwise
   Example:

   • IsPrime(3) returns true
   • IsPrime(4) returns false
   • IsPrime(5) returns true
   • IsPrime(6) returns false
   • IsPrime(7) returns true
   • IsPrime(8) returns false
   
   
   
2. AllPairs(integer n)
   Input: n an integer, n >= 0
   Output: prints out

   	(0,0)
   	(1,0)(1,1)
   	(2,0)(2,1)(2,2)
   	(3,0)(3,1)(3,2)(3,3)
   	...
   	(n,0)(n,1)...(n,n-1)(n,n)
   	

3. Buyable(integer n)

   Background: At McDonalds, you can only purchase 6,9 and 20 packs of McNuggets. Call an amount of McNuggets buyable if it is possible to purchase some number of 6,9 and 20 packs and total the target amount.

   For example 0, 6, 15, 18 are all buyable. 10 and 11 are not buyable.
   Input: n an integer
   Output: returns true if n is a buyable amount, false otherwise
   Example:

   • Buyable(0) returns true
   • Buyable(6) returns true
   • Buyable(15) returns true
   • Buyable(18) returns true
   • Buyable(10) returns false
   • Buyable(11) returns false
   
   Algorithm: Implement the following recursive algorithm

   	if n < 0 then n is not buyable
   	if n=0 then n is buyable
   	if one of n-6, n-9 or n-20 is buyable then so is n