CSC 180 Notes for Tutorial #1 To be given week of 16th September Monday 16 Sept Wednesday 18 Sept ============ Notes for the tutorial ============================================ DERIVE AN ALGORITHM FOR PRIMALITY TESTING ========================================== Problem that we want to write an algorithm to solve: ======== Given an integer n, determine whether or not n is a prime number. Recall that a positive integer n is prime if it has exactly two positive integer divisors, itself and 1. (Solving this problem is important in cryptography, the study of codes.) examples: 23 is prime because its only integer divisors are 1 and 23. 35 is not prime because it can be divided evenly by 5 and 7. 1 is not prime because it has only 1 divisor. Attempt One at an algorithm: (They may try to get you to do something more complex than this, but try to get them to start with something as simple as the following.) idea: count all of the numbers between 1 and n that divide evenly into n if at the end the count is 2, n is prime. This leads us to write: Algorithm One: set numberOfDivisors to 0 for each number i between 1 and n if i divides n exactly then add 1 to numberOfDivisors end if end for if numberOfDivisors is 2 then print a message indicating that n is prime otherwise print a message indicating that n is not prime end if (You can assume that the "processor" of this algorithm knows how to answer the question "does i divide n exactly" so that we don't have to deal with this subproblem.) Try to convince them that this algorithm is correct. Ask them to make some observations about the algorithm and try to get at the following issues: observations: - it is very inefficient. o If n were 1 000 000, the repetition would test 1 million numbers before making the final verdict. But you know that 1 000 000 is not prime because it is an even number! So test whether or not n is even before going through the repetitions. o Once you have found 1 divisor between 1 and n, you know that n is not prime. You need not look at other divisors. o In fact, we don't have to look at all of the numbers up to n. If n is evenly divisible by some integer d_1, then, by the definition of divisibility, n / d_1 is therefore an integer that we can call d_2. What can you say about the size of d_1 and d_2 ? Since d_1 X d_2 = n, you know that one of d_1,d_2 is <= sqrt(n) and the other one is >= sqrt(n). Thus, if n has any divisors, one of them must be <= sqrt(n). Hence, we need only repeat from 1 to sqrt(n). In fact, we don't need to test 1, since we know that 1 divides all integers evenly. And we are going to test divisibility by 2 separately. This suggests that we can write: Algorithm Two: if n is exactly divisible by 2 then print a message indicating that n is not prime otherwise set the numberOfDivisors to 1 for each number i between 3 and sqrt(n), counting by 2 if i divides n exactly then print a message indicating that n is not prime add 1 to the numberOfDivisors end if end for if numberOfDivisors is 1 then print a message indicating that n is prime end if end if Does anyone notice any errors in this algorithm? - it gets the wrong answer for n = 1 According to our definition, 1 is not prime, but this algorithm says that 1 is prime. - it gets the wrong answer for n = 2 According to our definition, 2 is prime, but this algorithm says that 2 is not prime. How can we avoid these difficulties without ruining our otherwise good looking algorithm? Add tests for these two special cases at the beginning of the algorithm. Considering special cases at the start of an algorithm is a very common practice. Algorithm Three: if n is 1 then print a message indicating that n is not prime otherwise, if n is 2 then print a message indicating that n is prime otherwise, if n is evenly divisible by 2 then print a message indicating that n is not prime otherwise set the numberOfDivisors to 1 for each number i between 3 and sqrt(n), counting by 2 if i divides n exactly then print a message indicating that n is not prime add 1 to the numberOfDivisors end if end for if numberOfDivisors is 1 then print a message indicating that n is prime end if end if Try to convince yourselves that this program is correct. (But it is not very efficient when n is large. Recent progress has been reported in the newspapers about primality testing.) DERIVE AN ALGORITHM FOR PLAYING THE GAME "21" ============================================== The Game "Twenty-one" --------------------- Develop an algorithm for the game "twenty-one" (which is explained below), with your class. Do not write C-code but instead express your algorithm in a pseudo-code. Make sure this is very interactive. I have included a suggested algorithm, but you needn't follow it exactly. As you go, trace bits of the algorithm with the class to see if they're correct. The Game Twenty-One ------------------- First explain the game, which is played as follows: The game involves two players, and proceeds as follows. The players take turns choosing numbers from one to three and each number chosen is added to a running total. The player who brings the running total to 21 is the winner. For example, a game might proceed as follows: Number Running Move Who's Turn Chosen Total 1 player A 1 1 2 player B 3 4 3 player A 1 5 4 player B 2 7 5 player A 3 10 6 player B 3 13 7 player A 3 16 8 player B 3 19 9 player A 2 21 Player A wins this game. An algorithm ------------ Let's assume that the computer is going to play the user, and that the computer moves first. So the computer has to decide its own move, and the user must type theirs in. For a first version of the algorithm, use a not clever method for the computer's move: have it always pick 1. Later, if you have time, you can develop a better strategy (also described below.) But don't rush the first version so that you have time for the fancy one. Take plenty of time developing the algorithm interactively. Here's my algorithm. Try to get them to derive something like this. Try to derive it in a "top-down" fashion and not get "bogged-down" in too many details at the start. Try to identify "sub-problems" that you can solve separately from the main problem. (Don't feel as if you have to write out the verbose "subproblem" comments given below. That may take too much time.) /* * The Twenty-One Algorithm. * This algorithm plays the number game "twenty-one" once with a user. The * computer always moves first. */ =============================================================================== /* * "goal" indicates the number to be reached to win, i.e. 21 * "max_move" indicates the maximum value allowed for a valid move, i.e. 3 * "running_total" keeps track of the total reached so far */ /* Say hello to the user and start the running_total off at zero. */ print introduction to user set running_total to 0 % Repeatedly handle moves by the computer and user, until one of them wins. repeat as long as no one has won the game /* Do a move by the computer and if it wins, tell the user so and */ /* end the game. */ do a computer move, changing running_total if computer has won then print appropriate message leave the repeat-loop end if /* Get a move from the user and if he or she wins, indicate this and */ /* end the game. */ do a user move, using goal and max_move and changing running_total if user has won then print appropriate message leave the repeat-loop end if end repeat /* Say goodbye to the user. */ print a good-bye message to the user ------------------------------------------------------------------------------- /* Instructions for doing a computer move. The move chosen by the computer */ /* is added to the running total, and the user is notified of the computer's */ /* move. */ To do a computer move, changing running_total: /* The computer always moves by one (not a very clever approach). */ /* Add this move to the running total, and print a message about the move. */ add 1 to running_total print message about this move -------------------------------------------------------------------------------- /* * Instructions for doing a user move. The move is read in from the user. * If not valid, the user is repeatedly asked for another move until he or * she gives a valid one. Once a valid move has been given, it is added * to the running total, and the user is notified of the result of the move. */ *** IT MAY TAKE THEM A WHILE TO APPRECIATE THE NEED FOR THE COMPLEXITIES OF *** THE DETAILS IN THE LOOP. TRY TO GET THEM TO "DERIVE" THE DETAILS, *** ONE STEP AT A TIME. To do a user move, using goal and max_move and changing running_total: /* Keep asking for a move until a valid one is given. At this point, */ /* process it. */ repeat until the user makes a valid move /* First, ask the user for a move, and read it. */ print message asking user for next move read in next_move /* If the move is valid, process it. If not, print a message */ /* indicating the user's error. */ if next_move is between 0 and max_move (inclusive) then if next_move will take the total beyond the goal amount then print a message indicating this otherwise, % the move is valid, so add next_move to running_total print message about this move leave the repeat-loop otherwise print message saying the move is not valid end if end repeat A better strategy for the computer's move --> Do this only if you have time ----------------------------------------- (You may want to just talk about this.) The computer (or whoever moves first) can always win by making it their goal to be first to reach 17. Then no matter what number the other player chooses, the first player to 17 can reach 21 on their next move (verify this). Now, how can the first player must make sure she reaches 17 first? She can think of this as a new game -- ``The Game of Seventeen''. The player makes it their goal to be the first player to reach 13. Again, no matter what number the other player chooses, she can reach 17 on their next move. The first player now thinks of the new game ``The Game of Thirteen''. The next goal the first player establishes is 9 (``The Game of Nine'') and then 5 (``The Game of Five'') and finally 1 -- that is, the first player wants to reach 1. In general, the sequence of Running Totals that the first player wants after their turn is 1,5,9,13,17,21. Thus, the target for the nth computer move is 1+(n-1)*(3+1). Therefore, the number chosen by the computer for the n^{th} move is: (1+(n-1)*(3+1))-(running total) Modify the algorithm for generating a computer move to use this new strategy. Notice that this version needs to use the value n. (There is another formula that doesn't use n, but it's probably not worth getting into that. (21 - running_total) mod (3 + 1) It's just one more wrinkle, and it uses "mod", which they haven't seen yet.) Exercise - for the students -------- Suggest to your students that they should try to generalize the above strategy for different final targets and maximum move amounts. Can the first player always be guaranteed a win? (Try ``The Game of Twenty'' with maximum move amount 3.)