# 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()

5. Sorting (selection, bubble, merge, builtin sorts) (Moved to Efficiency Week!)
Sorting videos:
• selectionsort
• bubblesort
• mergesort
• sorting timing
# sorting.py import time, random #################################################### # swap #################################################### def swap(a, i, j): (a[i], a[j]) = (a[j], a[i]) #################################################### # selectionSort #################################################### def selectionSort(a): n = len(a) for startIndex in range(n): minIndex = startIndex for i in range(startIndex+1, n): if (a[i] < a[minIndex]): minIndex = i swap(a, startIndex, minIndex) #################################################### # bubbleSort #################################################### def bubbleSort(a): n = len(a) end = n swapped = True while (swapped): swapped = False for i in range(1, end): if (a[i-1] > a[i]): swap(a, i-1, i) swapped = True end -= 1 #################################################### # mergeSort #################################################### def merge(a, start1, start2, end): index1 = start1 index2 = start2 length = end - start1 aux = [None] * length for i in range(length): if ((index1 == start2) or ((index2 != end) and (a[index1] > a[index2]))): aux[i] = a[index2] index2 += 1 else: aux[i] = a[index1] index1 += 1 for i in range(start1, end): a[i] = aux[i - start1] def mergeSort(a): n = len(a) step = 1 while (step < n): for start1 in range(0, n, 2*step): start2 = min(start1 + step, n) end = min(start1 + 2*step, n) merge(a, start1, start2, end) step *= 2 #################################################### # builtinSort (wrapped as a function) #################################################### def builtinSort(a): a.sort() #################################################### # testSort #################################################### def testSort(sortFn, n): a = [random.randint(0,2**31) for i in range(n)] sortedA = sorted(a) startTime = time.time() sortFn(a) endTime = time.time() elapsedTime = endTime - startTime assert(a == sortedA) print("%20s n=%d time=%6.3fs" % (sortFn.__name__, n, elapsedTime)) def testSorts(): n = 2**8 # use 2**8 for Brython, use 2**12 or larger for Python for sortFn in [selectionSort, bubbleSort, mergeSort, builtinSort]: testSort(sortFn, n) testSorts()