# CMU 15-112: Fundamentals of Programming and Computer Science Class Notes: 1d Lists: Worked Examples

1. The Locker Problem
def lockerProblem(lockers): isOpen = [ False ] * (lockers+1) students = lockers for student in range(1,students+1): for locker in range(student, lockers+1, student): isOpen[locker] = not isOpen[locker] openLockers = [ ] for locker in range(1, lockers+1): if isOpen[locker]: openLockers.append(locker) return openLockers print(lockerProblem(2000))

2. Anagrams
def letterCounts(s): counts = [0] * 26 for ch in s.upper(): if ((ch >= "A") and (ch <= "Z")): counts[ord(ch) - ord("A")] += 1 return counts def isAnagram(s1, s2): # First approach: same #'s of each letter return (letterCounts(s1) == letterCounts(s2)) def isAnagram(s1, s2): # Second approach: sorted strings must match! return sorted(list(s1.upper())) == sorted(list(s2.upper())) def testIsAnagram(): print("Testing isAnagram()...", end="") assert(isAnagram("", "") == True) assert(isAnagram("abCdabCd", "abcdabcd") == True) assert(isAnagram("abcdaBcD", "AAbbcddc") == True) assert(isAnagram("abcdaabcd", "aabbcddcb") == False) print("Passed!") testIsAnagram()

3. The Sieve of Eratosthenes
# Sieve of Eratosthenes # This function returns a list of prime numbers # up to n (inclusive), using the Sieve of Eratosthenes. # See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): isPrime = [ True ] * (n+1) # assume all are prime to start isPrime[0] = isPrime[1] = False # except 0 and 1, of course primes = [ ] for prime in range(n+1): if (isPrime[prime] == True): # we found a prime, so add it to our result primes.append(prime) # and mark all its multiples as not prime for multiple in range(2*prime, n+1, prime): isPrime[multiple] = False return primes print(sieve(100))

4. The Prime Counting Function
# Sieve of Eratosthenes # More complete example, showing one reason why we might # care to use the sieve rather than the simple isPrime function # we already learned how to write. # We'll be computing the prime counting function, pi(n): # See http://en.wikipedia.org/wiki/Prime-counting_function # We'll do it two different ways: once using the simple isPrime # function, and again using the sieve. We'll time each way # and see how it goes. #################################################### ################### ## sieve(n) ################### # This function returns a list of prime numbers # up to n (inclusive), using the Sieve of Eratosthenes. # See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): isPrime = [ True ] * (n+1) # assume all are prime to start isPrime[0] = isPrime[1] = False # except 0 and 1, of course primes = [ ] for prime in range(n+1): if (isPrime[prime] == True): # we found a prime, so add it to our result primes.append(prime) # and mark all its multiples as not prime for multiple in range(2*prime, n+1, prime): isPrime[multiple] = False return primes # Here we will use the sieve to compute the prime # counting function. The sieve will return a list # of all the primes up to n, so the prime counting # function merely returns the length of this list! def piUsingSieve(n): return len(sieve(n)) ################### ## piUsingisPrime(n) ################### # Here we will use the isPrime function to compute # the prime counting function. def piUsingIsPrime(n): primeCount = 0 for counter in range(n+1): if (isPrime(counter)): primeCount += 1 return primeCount def isPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False for factor in range(3, 1+int(round(n**0.5)), 2): if (n % factor == 0): return False return True #################################################### ################### ## test code ################### # Before running the timing code below, let's run # some test code to verify that the functions above # seemingly work. Test values are from: # http://en.wikipedia.org/wiki/Prime-counting_function def testCorrectness(): print("First testing functions for correctness...", end="") assert(piUsingSieve(10) == 4) assert(piUsingIsPrime(10) == 4) assert(piUsingSieve(100) == 25) assert(piUsingIsPrime(100) == 25) assert(piUsingSieve(1000) == 168) assert(piUsingIsPrime(1000) == 168) print("Passed!") testCorrectness() #################################################### ################### ## timing code ################### # Finally we can time each version for a large value of n # and compare their runtimes import time def testTiming(): n = 1000 # Use 1000 for Brython, 1000*1000 for Python print("***************") print("Timing piUsingIsPrime(" + str(n) + "):") startTime = time.time() result1 = piUsingIsPrime(n) endTime = time.time() time1 = endTime - startTime print(" result = " + str(result1)) print(" time = " + str(time1) + " sec") print("***************") print("Timing piUsingSieve(" + str(n) + "):") startTime = time.time() result2 = piUsingSieve(n) endTime = time.time() time2 = endTime - startTime print(" result = " + str(result2)) print(" time = " + str(time2) + " sec") print("***************") print("Comparison:") print(" Same result: " + str(result1 == result2)) print(" (time of isPrime) / (time of sieve) = " + str(time1 / time2)) print("And this only gets worse, and quickly, for larger values of n.") testTiming()