CompSciWeek1

Required reading for this week is Beginning Python, chapters 1-4. Be sure to try out the examples in python, not just read.

Class 1

1. Pretest
2. Basic Shell Usage
   • pwd, ls, directory structure
3. Access to Resources
   • Logging into the lab computers
     • Explanation of dual boot, OS evolution
   • opening terminals, and terminals through terminals
   • Logging into circe.rc.usf.edu
   • Moving files
   • Running python on your own machine
     • Windows: Python Idle + easy_install ()
     • alt: Cygwin
     • OSX / Linux: Package managers (OSX: fink, Debian (deb): apt-get, RH (RPM): yum)
4. First-order data types:
   • int(1.1), float(-3), string(4) [essentially all languages]
   • (and 2nd order) tuple([5]), list((6,)), dict([(6,7)]) [python-specific]

Class 2

1. What is a Turing machine?
2. The infinite loop and other control structures.
3. First algorithms (Horner, Euclid, Babylonian)
4. Code walk-through for a poorly designed Euclids algo.
5. The KISS, DRY, and incremental principles
6. Higher-order constructs:
   • functions
   • functional code

Homework I

This assignment will be due in 2 weeks, on Monday, Sept. 8.

1. Create a program that reads in strings with raw_input() until a string containing a single '.' is sent. After that, the program should print out the strings it has read in reverse order (hint: use list.pop()).
2. Implement the Babylonian/Heros method to approximate the square root of 2 using 10 iterations. Plot the error in the approximation against iteration number. Is there a good way to automatically guess when to stop iterating?
   • Edit 9/5/14 A printed list of the error at each iteration can be included in place of a plot.
3. Imagine Bassetts Ice Cream has a data set of daily ice cream sales for 3 different flavors stretching back to 1893. Write pseudocode for an algorithm that finds the largest and smallest sales over daily, weekly, monthly, and yearly time-scales. Use steps like `add together 7 days sales` and `get the smallest number in the list`. If each test or addition step for each number takes 0.1 microseconds (10^-7 seconds), estimate how many microfortnights (1 microfortnight = 1.2096 s) the code will take to run?
   • Edit 9/5/14 One final result should be output for each timescale. For the monthly timescale, for example, the result would be the (flavor, month number) pair with the highest and lowest numbers. -- Congrats to Christine McNiff for forcing a formal specification of the result. Ambiguities like this are a common source of conflict in programming vs. specifications...
4. Obfuscation challenge: Write (in the most complicated unreadable way you can stand) a code that prints out the first 20 or so prime numbers. The code is limited to 100 lines, cannot use external packages, and must always finish running in less than 1 minute.

Answer to Bassett's Ice Cream Problem (both pseudocode and code) <source lang="python"> days = (2014-1893)*365.25 # for "starting this day in 1893"

1. 1. find max/min over days
2. 2. create weekly sums
3. - find max/min over weekly sums
4. 3. create monthly sums
5. - find max /min over monthly sums
6. 4. create yearly sums
7. - find max/min over yearly sum

1. combination!
2. 2-4: create sums over subsets
3. - find max/min over sum
4. this also covers 1 (with n = 1)

1. input - daily sales data array (days, 3)
2. - length scale (combined data size)
3. output min/max over subset
4. def subset_stat(sales, starts, extents):
5. 0, 31, 31+28, ...
6. run-time cost = f(L, n) = 3*L adds, 6*L/n comparisons
7. 3*L + 6/n *L = (3+6/n) * L -- linear time.

def subset_stat(sales, n):

       L = len(sales)
       sub = []
       for i in range(0, L, n): # loop over all subsets L/n
               y = sum(sales[i:i+n], 0) # access whole subset (n)
               sub.append(y)
       # L*3 additions
       sub = array(sub)
       # 6* L/n min/max
       return max(sub[:,0]), max(sub[:,1]), max(sub[:,2]), \
       min(sub[:,0]), min(sub[:,1]), min(sub[:,2])

1. max : [number] -> number

subset_stat(sales, 1) subset_stat(sales, 7) subset_stat(sales, 30) subset_stat(sales, 365) </source>