Difference between revisions of "CompSciWeek1"

From Predictive Chemistry
Jump to: navigation, search
(→‎Homework I)
(→‎Homework I)
 
(3 intermediate revisions by the same user not shown)
Line 37: Line 37:
 
# 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()).
  
# 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()).
 
# Implement the Babylonian/Hero''s 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?
  
# Implement the Babylonian/Hero''s 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.
 
# 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?
  
# 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...
  
#* 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...
 
# 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.
  
# 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">
  +
from numpy import *
  +
  +
days = (2014-1893)*365.25 # for "starting this day in 1893"
  +
test_sales = (random.random((days,3))*10000).astype(int) # test data
  +
  +
# 1. find max/min over days
  +
# 2. create weekly sums
  +
# - find max/min over weekly sums
  +
# 3. create monthly sums
  +
# - find max /min over monthly sums
  +
# 4. create yearly sums
  +
# - find max/min over yearly sum
  +
  +
# combination!
  +
# 2-4: create sums over subsets
  +
# - find max/min over sum
  +
# this also covers 1 (with n = 1)
  +
  +
# input - daily sales data array (days, 3)
  +
# - length scale (combined data size)
  +
# output min/max over subset
  +
#def subset_stat(sales, starts, extents):
  +
# 0, 31, 31+28, ...
  +
# run-time cost = f(L, n) = 3*L adds, 6*L/n comparisons
  +
# 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])
  +
# max : [number] -> number
  +
  +
subset_stat(test_sales, 1)
  +
subset_stat(test_sales, 7)
  +
subset_stat(test_sales, 30)
  +
subset_stat(test_sales, 365)
  +
</source>

Latest revision as of 13:17, 24 September 2014

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"> from numpy import *

days = (2014-1893)*365.25 # for "starting this day in 1893" test_sales = (random.random((days,3))*10000).astype(int) # test data

  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(test_sales, 1) subset_stat(test_sales, 7) subset_stat(test_sales, 30) subset_stat(test_sales, 365) </source>

Retrieved from "https://predictivestatmech.org/w/index.php?title=CompSciWeek1&oldid=215"