Computer Science 15-110, Spring 2011
Class Notes:  1d Lists Practice (Problem-Solving)

1. The Locker Problem
2. Anagrams
3. Sieve of Eratosthenes and the Prime Counting Function pi(n)
4. Sample Solutions
   

1. The Locker Problem
   In this example, we see how we can write a short Python program to help us gain some insights into what many students might find to be a somewhat inobvious math problem.  Say that 2000 students lined up outside a school that, happily, has 2000 lockers, one for each student.  Both students and lockers are numbered from 1 to 2000.  At first, all the lockers are closed.  Then, each student in turn goes through the halls, where student 1 visits every locker, student 2 visits every 2nd locker, student 3 visits every 3rd locker, and so on (so, for example, student 8 visits lockers 8, 16, 24, 32, ...).  When a student visits a locker, if the locker is open they close it, and if it is closed they open it.  When all the madness is over, which lockers are open?  Write the function lockerProblem that takes the number of students as a parameter, and returns a list of the lockers that are open at the end.
   
   
2. Anagrams
   Write the function areAnagrams that takes two strings and returns True if they are anagrams and False otherwise, where two strings are anagrams if they are composed of the same letters (without regard to case).  For example, "steelers" and "treeless" are anagrams.  Here are some test cases for you:
       assert(areAnagrams("", "") == True)
       assert(areAnagrams("abCdabCd", "abcdabcd") == True)
       assert(areAnagrams("abcdaBcD", "AAbbcddc") == True)
       assert(areAnagrams("abcdaabcd", "aabbcddcb") == False)
   Hint:  You may wish to use the upper method.  For example, "Abc".upper() is "ABC".
   
   
3. Sieve of Eratosthenes and the Prime Counting Function pi(n)
   Write the function sieve(n) that takes an integer n and returns a list of all the prime numbers up to and including n.  Your function should do so by implementing the Sieve of Eratosthenes.   Here are some test cases for you:
       assert(sieve(10) == [2, 3, 5, 7])
       assert(sieve(31) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])
   To see where this can be useful, we'll continue this problem by computing the Prime Counting Function pi(n), which is the number of prime numbers less than or equal to n.  Do this two ways:  first, by repeatedly calling isPrime for every number from 2 to n.  Second, call sieve(n) and simply compute the length of the list it returns.  Finally, time how long it takes to compute pi(one million) each way.  If you'd rather cut to the chase, see the solution below for details.
   
   
4. Sample Solutions
1. The Locker Problem
2. Anagrams
3. Sieve of Eratosthenes and The Prime Counting Function pi(n)

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem