CS 60 Slides

CS 60 Slides

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

Recently Viewed Presentations

  • The Aeneid: Roman Epic - Cuyamaca College

    The Aeneid: Roman Epic - Cuyamaca College

    Times Garamond Times New Roman Verdana Wingdings Arial Level The Aeneid: Roman Epic The Aeneid Narrative Structure The Roman Hero Book 1: Aeneas in Carthage The Wrath of Juno Arrival in Libya Venus' Appeal & Jupiter's Prophecy Dido and the...
  • Indiana Election Division - IN.gov

    Indiana Election Division - IN.gov

    Indiana Election Division will develop sheriff report form working with counties and Indiana Sheriffs' Association. 2017 Election Legislation:Vote History in One-Party Primary. If only Party A is holding a primary election, and there is no public question on primary ballot,...
  • Chapter 3: Christianity Section 5: Sacred Places and Sacred ...

    Chapter 3: Christianity Section 5: Sacred Places and Sacred ...

    Gothic. Romanesque. Byzantine. These are some of the most common examples of the different styles of architecture, but there are many more. Variance of Church Interiors. Altar in middle with pulpit on side. Catholic, Anglican, Orthodox, or Lutheran.
  • AAO-HNSF Clinical Practice Guideline (Update): Sudden Hearing ...

    AAO-HNSF Clinical Practice Guideline (Update): Sudden Hearing ...

    ENT PAC. Socioeconomic & Grassroots Committee. 2019 Highlights. New Academy Student Initiative - physicians at grassroots level participate in multiple student programs including high school and medical school observerships. This provides opportunities for early exposure and a better ...
  • On-Ramps for Formal Methods

    On-Ramps for Formal Methods

    On-Ramps for Formal Methods. I am not a formal methods expert.Or an AI expert.Or an automation expert. NASA Engineering and Safety Center (NESC) Action from Challenger and Columbia Recommendations "Red" or "Tiger" team support for engineering decisions.
  • Information Extraction

    Information Extraction

    Where is Citizen Kane playing in SF? Castro Theatre at 7:30. Do you want a ticket? The S&P500 jumped. Ambiguity makes NLP hard. Teacher strikes idle kids. Red tape holds up new bridges. Hospitals are sued by 7 foot doctors....
  • Two NC Community Colleges Prepare Non-Traditional ... - act.org

    Two NC Community Colleges Prepare Non-Traditional ... - act.org

    Closing the Education Attainment Gap in NC. Between 2009 and 2016. 757,160 public NC high school graduates. As of May, 2018, 72 percent of these students - 546,167 individuals - had enrolled in a two-or four-year postsecondary institution.
  • Boyer GP Template

    Boyer GP Template

    Tax updates - Load them AFTER closing payroll for the year ... Log into SL with a user that has initialize rights for vendor maintenance screen. ... Box 11 - Foreign Tax Paid is removed in field positions 28 -...