Driving N on the Dalton Highway (though it feels like it!) Welcome to Programming Practicum Harbin! Waiting for the snow enveloping you on Route 5 N to melt Putting the C into CS Harbin! exploring martian soil On the 405, in traffic, being chased by police (and TV) helicopters. Victorville, for DARPA's Urban Granc Challenge
University of St. Petersburg DC for the inauguration Denver, CO or Minneapolis, MN You arent here On fire just W of here!! Pittsburgh Worldcom Headquarters Krispy Kremes drive-through
writing clinic reports rebooting knuth (or turing or) coding chunky strings Teaching Honors English for Janice Barbee at Pomona High School Waiting in line to vote in the Florida primaries
Being dragged off-course 18 miles into a marathon race by a crazed spectator clinic liaison phone call installing Debian 3.1 Leading a Gray Davis / Gary Coleman / Arnold T-800 Schwarzenegger gubernatorial fundraiser Massey University Palmerston North, NZ Mailing something at the
Claremont Post Office the dumpster Introductions! Zach Dodds Office Olin 1255 Email [email protected] fan of low-tech games fan of low-level AI Atari 2600 Adventure! What is this course about? What is this course about? A chance to improve your programming skills What
Algorithm analysis and insight Program design and implementation optimizing coding time, not running time ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with Javas libraries OR your choice of "reasonable" language Research/prototype programming Unofficial course name: CS -70 Class Organization
alternating format discussion sessions problem and program analysis discussion of strategy and coding tips deciding on functional decomposition, data structures, language facilities, and algorithms to use in teams of 2-3 lab sessions teams may use 1 machine per person (only the mock contest adheres to ACM rules) a team might want to practice with only 1 machine these problems count for each member of the group sometimes new problems, other times with known ones 4~5 problems given out per week
Class Organization Feedback from prior semesters there should be an opportunity to start coding cold (true in labs) make individual vs. team-based work clear problems can be done individually or in teams of 2 up to 3 people, during the lab "mock contest" sessions afterwards provide the code to all team members you may choose to work as a team afterwards, but don't have to each person submits their own problems per person per week? about 1-2, if you work on a team in lab... and consider all of the weeks of the term! snacks and jotto! better support for newcomers and for contest problems! Course Organization Sep 7 Sep 14 Sep 21
Sep 28 Oct 5 Oct 12 Oct 19 Oct 26 Nov 2 Nov 9 Nov 13 Nov 16 Welcome! and DP problems ~ 4.5 problems Lab session ~ 4.5 problems Discussion session on geometry problems ~ 4.5 problems Lab session ~ 4.5 problems (unless there is a clinic trip) Discussion on the ACM contest's history (Don Chamberlain) Discussion session on graph problems ~ 4.5 problems Lab & local ACM qualifying contest ~ 6 problems Discussion session on something you haven't seen? ~ 4.5 problems Lab session ~ 4.5 problems No meeting (organizing teams to Riverside...) (Sat.) ACM Regional contest (in Riverside...)
Final meeting (may be a make-up lab for 9/28) 36 problems total You may submit problems until the end of exams Last year's ACM regional contest Course webpage references problem statements and sample data problems you have solved administrative info Grading CS 189 is graded individually... (its possible to take it P/F, too) though not for CS elective credit Coding Guidelines problems can be done any time during the semester
discussion of algorithms always OK coding should be within teams you may use any references except an existing solution or partial solution one person should take the lead on each problem use /cs/ACM/acmSubmit to submit on knuth try things out ! the reason for CS 189! Problem credits Problems are worth double if You solve them during the 4:15 - 5:30 lab sessions the team gets credit, if in a team It's one of the "extra difficult" problems, which may be determined as we go Language Choice?
Any standard language is OK -- but do keep in mind that the competition allows only Java, C, and C++ . Other "standard" languages (so far): C#, Python, Ruby, Perl, PHP, Haskell, Lua, Clojure, Lisp reasonable alternatives will also be considered A prior term's summary: languages 17 8 4 (+2) 16 1
6 20 3 1 (+2) (+1) (+1) (+12) (+1) 1
2 11 1 17 4 (+1) (+1) (+9) (+2) (+2) 2
2 8 3 8 (+2) 2 (+2) 13 14 (+10)
(+9) 1 21 1 1 15 (+16) (+14) (+4) number of 2x scores
Tallies per problem and per language 1 number of 4x scores python 82 d 8 lua 2 java 60
ruby 6 awk 2 C++ 40 scheme 3 js 2 1 each
sql cobol basic x86 asm pascal mathematica sh, latex This week's problems Cows are the global theme of CS189's problems. These 3 problems are worth 0.5 points, but 1 point if solved "in lab." The ave problem Input MIX Farmer Alvarado's roman numeral
Output Ave, Ave, ... Ave, Ave, Mvnde! Mvnde! total of 1009 of these Mvnde! Mvnde! That number of "Hello, World"s in Latin. If it's not a valid roman numeral, output nocens numerus http://www.roesler-ac.de/wolfram/hello.htm
The Hello, world! collection i.e., bad number "Hello, World" of the day! from math import * sine & cosine functions! def f(x): return int(round(96.75 + -21.98*cos(x*1.118)\ + 13.29*sin(x*1.118)\ + -8.387*cos(2*x*1.118)\ + 17.94*sin(2*x*1.118)\ + 1.265*cos(3*x*1.118)\ + 16.58*sin(3*x*1.118)\ + 3.988*cos(4*x*1.118)\ + 8.463*sin(4*x*1.118)\ + .3583*cos(5*x*1.118)\ + 5.878*sin(5*x*1.118))) print "".join([chr(f(x)) for x in range(12)])
"Hello, World" of the day! Here is "Hello World" How does it work? http://www.korokithakis.net/node/89 Dynamic Programming When a seemingly intractable problem has lots of repeated substructure, go DP! Build a table of partial results. Replace computation with table look-up when possible Dynamic programming? Action!
Dynamic programming! The subseq problem Input Cow label sequence #1 (s1) THEQUICKBROWNCOW JUMPEDOVERADOG Output 3 Cow label sequence #2 (s2) The number of the longest common subsequence bewteen s1 and s2. what is it?
The subseq problem Input s1 = "THEQUICKBROWNCOW" Output LCS( i1, i2 ) = s2 = "JUMPEDOVERADOG" length of longest common subsequence of s1 up to i1 and s2 up to i2 overlapping subproblems Strategy (1) Write your solution recursively, in terms of these. (2) Make sure you don't call any subproblem more than once! The subseq problem
s1 = "THEQUICKBROWNCOW" Output LCS( i1, i2 ) = LCS( i1, i2 ) = s2 = "JUMPEDOVERADOG" length of longest common subsequence of s1 up to i1 and s2 up to i2 Recursive LCS import sys sys.setrecursionlimit(100000) def LCS( i1, i2 ): """ classic LCS: s1 up to i1 vs. s2 up to i2, inclusive """ if i1 < 0 or i2 < 0: return 0 result = Compute LCS recursively! return result
if __name__ == "__main__": s1 = raw_input() s2 = raw_input() result = LCS( len(s1)-1, len(s2)-1 ) print result Avoiding repeated calls... import sys sys.setrecursionlimit(100000) D = {} def LCS( i1, i2 ): """ classic LCS: s1 up to i1 vs. s2 up to i2, inclusive """ global D if i1 < 0 or i2 < 0: return 0 if (i1,i2) in D: return
D[(i1,i2)] result = Compute LCS recursively! D[(i1,i2)] = result # memoized!! return result if __name__ == "__main__": s1 = raw_input() s2 = raw_input() result = LCS( len(s1)-1, len(s2)-1 ) print result # memoized!! Memoize remember old calls &
don't recompute them Avoiding repeated calls... Memoize Dynamic Programming remember old calls & don't recompute them make each call once and store it in a table import sys sys.setrecursionlimit(100000) class memoize: def __init__(self, function): self.function = function self.memoized = {} def __call__(self, *args): try:
return self.memoized[args] except KeyError: self.memoized[args] = self.function(*args) return self.memoized[args] @memoize def LCS( i1, i2 ): # definition here Python's "function decorator" syntax! Avoiding repeated calls... Memoize Dynamic Programming remember old calls & don't recompute them make each call once and
store it in a table if __name__ == "__main__": s1 = raw_input() s2 = raw_input() D = {} # empty table for i1 in range(len(s1)): for i2 in range(len(s2)): D[(i1,i2)] = LCS implementation! print D[(len(s1)-1, len(s2)-1)] Jotto! A word-guessing game similar to mastermind Sophs Jrs
Srs Profs ?0 ?0 ?0 ?0 This term's winning team earns 1 problem (per person)... Try these... Fall '09 Jotto: tied for the longest game yet Sophs Jrs
Srs Others icily 0 strep 2 icily 0 strep 2 icily 1 strep 2 icily 1 strep 1 spork 1 spork 3 spork 0
spork 0 spend 2 peeps 2 spend 2 peeps 1 spend 2 peeps 2 spend 2 peeps 1 furls 1 furls 1 furls 0
furls 1 Ghost 2 Tanks 2 Gecko 2 Ghost 1 Tanks 1 Gecko 1 Ghost 1 Tanks 2 Gecko 1 Ghost 0 Tanks 1 Gecko 1 Dynamic programming? practice contest
Dynamic programming? Action! Excitement from the judges room Excitement from the judges room Harbin
