CS104 Week 8 Lab

Week 8 Lab:

Part 1: Function to Find Max Increase in a List of Numbers

Step 1: Setup Eclipse

Open Eclipse, switch to your workspace (should be S:\workspace) and create a new folder in your CS104 project called lab8. In this folder, create a file maxdiff.py.

Put this code into your file, verbatim:

# Top comment block here # which includes your name, etc. # imports here# Constants here (if any) # Function declarations here (if any) # main code here.

This is a template for you to fill in.

Step 2: Create the function findMaxDiff()

In the "Function Declarations here" section, write a function that does this:

Name	findMaxDiff
Input Parameter	a list of numbers in non-decreasing order
Return value	the maximum increase between each pair of consecutive numbers

Examples: if the input parameter is [0, 1, 3, 9, 12] the result should be 6 because the biggest increase between consecutive numbers is 6 (when the jump is made from 3 to 9).

Recommendations: 1) use index-based for loop. 2) make sure you test your code on an input where the largest jump is the first pair, and where the largest jump is the last pair.

Note that your code should NOT use input() anywhere -- you will not get input values from the user when you run the program. Instead, your main code just calls your function with a list that you "hard-code" in the code. E.g.,

print( findMaxDiff ( [3, 10, 12, 13, 22, 28] ) )

Write any testing code in the "main code" part of the file. Leave the code there, for grading.

Make sure you put your names, etc., in your file in a comment at the top.

To submit your final version of maxdiff.py, you’ll need to use Windows Explorer.

Open the Windows Explorer (shortcut: WindowsKey - e)
Find your maxdiff.py file down in your workspace\CS104\lab8.
Copy maxdiff.py.
Now, navigate to T:\CS104\current\<yourid>\.
Create a folder there called lab8. (Do NOT call it lab8 or lab 8 or Lab 8 or ThisisTheDayThatTheLordHasMade. Call it lab8.)
Look again at the folder you just created. Is it called lab8? If not, give your professor a dollar, and then rename the folder lab8.
Paste the file into that folder.

Grading Rubric: 3 points total

2 points: program that runs correctly, with good test cases.
1 point: code is clean and neat and uses good comments and variable names. I.e., the code is hospitable. NOTE: you code should have a comment above any line of code whose purpose is non-obvious to the common reader.

OPTIONAL Part 2: Find indices of a pattern in a string (You may do this for Extra Credit)

In your lab8 Folder, create a new file count.py. Copy and paste the template code given in Part 1 into this file.

Write the following function:

Name	indices
Input Parameter	two strings: a string to search, s, and a pattern string, p
Return value	a list of indices where the pattern p was found in string s

Write a function that finds the locations of string p in string s, putting these locations in a list.

Example:

indices("abcabc", "abc") returns [0, 3], because "abc" was found at index 0 and at index 3 in "abcabc".
indices("aaa", "aa") returns [0] because "aa" was found at index 0, only. It does not find it at index 1 because character at index 1 is still part of the match at index 0.

To reiterate: when you find a match, you start searching for the next match at the end of the first match.

Hints:

use a while loop. Draw some pictures for yourself and make sure you get the boolean expression correct. You don't want to compare "off the end" of the string s.
use the accumulator pattern, where you initialize your results list to [] and append to it each time you find a matching location
use slicing to create slices of string s to compare for equality to p.

Put a few test cases in the "main part" of the file. Submit the code with those test cases in it.

Submit as above in part 1.

Grading rubric is as above.

Part 3: Testing Goldbach's conjecture

From Wikipedia:

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and in all of mathematics. It states: Every even integer greater than 2 can be expressed as the sum of two primes.[1]

In this lab, we'll write code to test this conjecture.

Step 1: Write code to compute if a number is a prime

In your lab8 folder, create a file lab8.py.

Put this code into your file, verbatim:

# Top comment block here # which includes your name, etc. # imports here# Constants here (if any) # Function declarations here (if any) # main code here.

This is a template for you to fill in.

In the "main code" section, write code to do this:

Ask the user for a number which is stored in a variable num. Make sure this num is an integer.
Write this code: print(num, "is prime?: ", isPrime(num))
Those are the only lines in the main section.

Step 2: Create the function isPrime()

In the Function Declarations section, create a function called isPrime(n). This function returns True if n is prime, and False otherwise. Put this information into the function's docstring.

You can tell if a number is prime if it cannot be perfectly divided by any number from 2 to n // 2 + 1. (Hint: "perfectly divided by" means the remainder is 0). Here is the algorithm for figuring out if an integer n is a prime number:

for each divisor from 2 to n // 2 + 1
- if divisor is a factor of n -- i.e., if dividing n by divisor leaves a remainder of 0 -- then n is not a prime number: return False immediately.
return True -- we've tried all possible divisors and found none of them divide n exactly, so n must be prime.

Now, run your code repeatedly and see if isPrime() produces the correct result for some known prime numbers, and some numbers known not to be prime.

Step 3: Generate a list of primes up to the value entered by the user

Replace your input() call in the main section to ask the user to enter a number, below which you will (eventually) test all even numbers, to see if Goldbach's Conjecture holds. Store the result in variable maxVal now. You'll want to convert the string that input() returns into an integer before having maxVal refer to it.

Below that code, write this code:

primesList = genPrimesList(maxVal)
print("Prime numbers up to", maxVal, "are", primesList)

Now, in the Function Declaration section, add a function declaration for genPrimesList(topVal).

The code in genPrimesList() does this:

"""Docstring explaining what this function does."""
create an empty list
for each integer from 2 to topVal (inclusive),
- if the integer is a prime, (Hint: we have a function that will tell us this)
  - add it to the end of the list.
return the list.

(The observant student will say to themselves, "Look at that! This is the accumulator pattern that keeps popping up! Cool!")

Run your code with the number 50, and see if it prints only prime numbers up to 50. Try it with a larger number, perhaps, 2000.

Step 4: Test Goldbach's Conjecture, finally

Now, that we have code that generates a list of primes, add code in your main code section to test if each even number from 4 up to maxVal is the sum of two primes.

The algorithm is basically this (be careful of the indentation below. You have to do it just like I've shown.):

initialize a counter to 0 (you'll see below what this is for).
for each even number, e, from 4 up to and including maxVal:
- create a variable found = False
- for each number p in primesList:
  - # a comment here explaining what the next line means
  - see if (e - p) is in primesList. If it is,
    - set found to True
    - If you want, you can add this line of code here:
      print("Found", e, "is the sum of primes", p, "and", e - p)
    - break out of this for loop: you've found that e is the sum of 2 primes. (i.e., type break)
- if found is False,
  - you were not able to find any prime p and its corresponding e - p that add up to e. So, e is not the sum of two primes. Print that you've proven Goldbach's Conjecture false for e. Make this a nice readable output.
  - increment a counter of how many even numbers you've found that show the conjecture is wrong.
if the counter is 0, print a statement about how Goldbach's conjecture holds for all even numbers up to maxVal.

Step 5: Submit

Clean up your code so that no testing/debugging output is generated anymore. Your code should just get a value from the user, and print out results -- the numbers that thwart Goldbach's Conjecture, or the statement saying that Goldbach's conjecture seems true for all tested numbers.

Put your standard information at the top of your file.

To submit your final version of lab8.py, you’ll need to use Windows Explorer.

Open the Windows Explorer (shortcut: WindowsKey - e)
Find your lab8.py file down in your S:\workspace\CS104\lab8.
Copy lab8.py.
Now, navigate to T:\CS104\current\<yourid>\lab8\.
Paste the file into that folder.

Grading Rubric: 9 points total

7 points: program runs correctly.
2 points: code is clean and neat and uses good comments and variable names. I.e., the code is hospitable. NOTE: you code should have a comment above any line of code whose purpose is non-obvious to the common reader.