Driving N on the Dalton Highway… (though it feels like it!) Welcome to Programming Practicum Waiting for the snow enveloping you on Route 5 N to melt “Putting the C into CS” exploring martian soil On the 405, in traffic, being chased by police (and TV) helicopters. Pittsburgh Victorville, for DARPA's Urban Granc Challenge University of St. Petersburg Engineering dept. Denver, CO or Minneapolis, MN You aren’t here Worldcom Headquarters Krispy Kreme’s drive-through writing clinic reports Waiting in line to vote in the Florida primaries… rebooting knuth (or turing or…) coding chunky strings Teaching Honors English for Janice Barbee at Pomona High School 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 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 ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with Java’s libraries OR your choice of language Research/prototype programming Unofficial course name: CS -70 "reasonable" 2007 ACM regionals - results http://www.socalcontest.org/history/2007/results-2007.shtml CSLB SDSU Pomona CPSLO http://icpc.baylor.edu/icpc/ '09 world finals: Stockholm, Sweden 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 problems given out per week… Class Organization Feedback from prior semesters… • there should be an opportunity to start coding “cold” • make individual vs. team-based work clear, lectures vs. labs • problems are, in general, individually completed -- except • those done during the lab "mock contest" sessions • provide the code to all team members • you may or may not choose to work as a team afterwards • submit for each person (email me if there are problems…) • 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! Course Organization Sep 2 Welcome! Review of dynamic programming: 4 problems Sep 9 Lab/Mock contest session: 4 problems Sep 16 Discussion session on graph problems: 4 problems Sep 23 Lab/Mock contest session: 4 problems Sep 30 Discussion session on geometry problems: 4 problems Oct 7 No class (I'll be out of town…) Oct 14 Lab/Mock contest session: 4 problems Oct 21 No class… Fall break! Oct 28 Mock ACM contest, 9pm – 1:00am, 6 problems Nov 4 Regional participants' -- preparation meeting Nov 11 Discussion and wrap-up for the semester You may submit problems until the end of exams… Sat. Nov. 8 may be the regional contest Course webpage references problem statements and sample data problems you have solved administrative info Grading CS 189 is graded individually... (it’s 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 <file> to submit • try things out ! the reason for ACM! Problem multipliers Problems are worth double if • You solve them during the 4:15 - 5:30 lab sessions the team gets credit, up to 3 people • It's one of the "extra difficult" problems, which will be determined as we go… These multipliers may be accumulated… • The new-language bonus is only in the spring term! Language Choice? • Any standard language is OK -- but do keep in mind that the competition allows only Java, C, and C++ . Other "standard" languages: C#, python, ruby reasonable alternatives will also be considered… Ask about our 2 extra-credit projects! web-updating and web-jotto Spring 2008 summary 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 (+16) 15 (+14) (+4) number of 2x scores Tallies per problem and per language (thus far)… 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 Dynamic programming! Jotto! A word-guessing game similar to mastermind… Sophs Jrs Srs Profs pluot 1 pluot 0 pluot 1 pluot 2 Dynamic programming When a seemingly intractable problem has lots of repeated substructure, go DP! Build a table of partial results. For example: Replace computation with table look-up when possible 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 the binary-decimal problem, for example: 2 6 3 19 0 Input Numbers, N, up to 106 0 marks the end of the input Output 10 1110 111 11001 the smallest decimal multiple of N with only the digits 0 and 1 ! Ideas? One way… Count up to the solution, starting from 1… Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 1 # of digits in answer 2 3 4 1 2 3 4 5 Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 1 # of digits in answer 2 3 4 1 1 2 3 4 5 Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 # of digits in answer 1 1 1 2 1 3 4 2 3 4 5 10 11 Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 # of digits in answer 1 1 1 2 1 3 1 4 2 110 3 111 4 5 10 11 10 11 Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 # of digits in answer 1 2 3 4 5 10 11 1 1 2 1 3 1 110 111 10 11 1 110 111 10 11 4 1110 DP! Only checking values for which a remainder has not yet been used… Fast Another example binary-as-decimal problem "pebbles" problem (2007 ACM regionals) Input 3 7 4 8 9 6 6 1 1 Square array, up to 15x15, of integers from 1 to 99 Idea 3 7 4 8 9 6 6 1 1 place "pebbles" on integers, trying to maximize total, but no two pebbles may be adjacent… vertically, horizontally, or diagonally maximum possible sum 14? Output Pebbles DP Idea consider all possibilities for pebbling each row they only depend on the previous row's best scores! Subset chosen (pebbles) 000 Input 8 9 6b 6 1 1c Square array, up to 15x15, of integers from 1 to 99 010 011 100 101 110 0 Row # 3 7 4a 001 1 2 Store the BEST score available for each possible subset. 111 Pebbles DP Idea consider all possibilities for pebbling each row they only depend on the previous row's best scores! Subset chosen (pebbles) Input 8 9 6b 6 1 1c Square array, up to 15x15, of integers from 1 to 99 Row # 3 7 4a 0 000 001 010 011 100 101 110 111 0 6 8 x 3 9 x x 1 2 Store the BEST score available for each possible subset. Pebbles DP Idea consider all possibilities for pebbling each row they only depend on the previous row's best scores! Subset chosen (pebbles) 000 001 010 011 100 101 110 111 0 0 6 8 x 3 9 x x 1 0+9 1+3 9+0 7+6 8+0 x x 3 7 4a 8 9 6b 6 1 1c Square array, up to 15x15, of integers from 1 to 99 Row # Input 9 4 9 x 13 8 2 Store the BEST score available for each possible subset. Pebbles DP Idea consider all possibilities for pebbling each row they only depend on the previous row's best scores! Subset chosen (pebbles) 000 001 010 011 100 101 110 111 0 0 6 8 x 3 9 x x 1 0+9 1+3 9+0 2 0+13 c+13 3 7 4a 8 9 6b 6 1 1c Row # Input 9 4 9 x 7+6 13 8+0 8 x x b+9 x a+9 ? x x Store the BEST score available for each possible subset. Square array, up to 15x15, of integers from 1 to 99 running time? Pebbles binary-as-decimal problem "pebbles" problem (2007 ACM regionals) Input 71 85 92 23 64 24 50 96 61 33 95 74 23 31 32 56 94 71 30 95 Square array, up to 15x15, of integers from 1 to 99 54 28 10 46 89 Idea 71 85 92 23 64 24 50 96 61 33 95 74 23 31 32 56 94 71 30 95 54 28 10 46 89 place "pebbles" on integers, trying to maximize total, but no two pebbles may be adjacent… maximum possible sum 572 Output Scanner sc = new Scanner(System.in); even a bit easier! This sure is sum code… to the max Martijn is VERY shifty! Martijn is shifty! Where is the table? Thanks, Martijn! Problem Set #0 (4 problems) In teams of 2~3, read over these… I need a picture of Farmer Ran! Problem Set #0 (4 problems) In teams of 2~3, read over these. • Where does the structure of the problem depend on similar (but smaller!) substructure? • How might you build up a table of values toward an overall solution? • Think of your next 5-letter jotto word… ! See you next Tuesday! bring a laptop, if you have one… Jotto! A word-guessing game similar to mastermind… Sophs Jrs Srs Me pluot 1 pluot 0 pluot 1 pluot 2 Problem Set #1 Input 4 4 tow cat row care ... .#. ... .## 0 0 (6 probs, 3 wks) # of words in the puzzle (to follow) # of rows in the puzzle (after the words) the words the puzzle this indicates the end of the input… Problem Set #1 (6 probs, 3 wks) Input 4 4 tow cat row care ... .#. ... .## 0 0 Problem 1 either the solution OR a cat statement that it can't be solved… a#o row e## Problem 2: no layout is possible. Output Problem Set #1 Input 6 5 1 # of empty boxes on the form # of clerks in the office (three lines each) the box(es) CHECKED clerk #0 the box(es) ERASED 1 2 2 3 4 4 5 1 3 2 (6 probs, 3 wks) the clerks who get a copy clerk #1 0 1 2 3 5 the form clerk #2 clerk #3 1 4 2 1 0 0 0 4 clerk #4 this indicates the end of the input… Problem Set #1 Input 6 5 1 # of empty boxes on the form # of clerks in the office (three lines each) the box(es) CHECKED clerk #0 the box(es) ERASED 1 2 2 3 4 4 5 1 3 2 (6 probs, 3 wks) the clerks who get a copy clerk #1 0 1 2 3 5 the form clerk #2 let's try it… clerk #3 1 4 2 1 0 0 0 4 clerk #4 this indicates the end of the input… Problem Set #1 Input 6 5 1 # of empty boxes on the form # of clerks in the office (three lines each) the box(es) CHECKED clerk #0 the box(es) ERASED 1 2 2 3 4 4 5 1 3 2 (6 probs, 3 wks) the clerks who get a copy clerk #1 0 1 2 3 4 5 the form clerk #2 clerk #3 1 4 2 1 0 0 0 1 3 4 5 clerk #4 Output the boxes checked the last time it leaves clerk #0's desk… this indicates the end of the input… Problem Set #1 Input (6 probs, 3 wks) list of traits, R == "recessive" D == "dominant" D traits are passed if EITHER parent has them RDDR Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 *** R traits are passed if BOTH parents have them all of the parents, gender, and traits the baby shrews… Deduce their possible parents! Problem Set #1 Input (6 probs, 3 wks) list of traits, R == "recessive" D == "dominant" D traits are passed if EITHER parent has them RDDR Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 *** R traits are passed if BOTH parents have them all of the parents, gender, and traits the baby bunnies… Deduce their possible parents! Frisky by Jumper-Slowpoke or Jumper-Speedy or ______ Sleepy by _________ Output Problem Set #1 Input (6 probs, 3 wks) list of traits, R == "recessive" D == "dominant" D traits are passed if EITHER parent has them RDDR Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 *** R traits are passed if BOTH parents have them all of the parents, gender, and traits the baby bunnies… Deduce their possible parents! Frisky by Jumper-Slowpoke or Jumper-Speedyor Sleepy by Shadow-Slowpoke Shadow-Speedy Output Problem Set #1 (6 probs, 3 wks) Read these three problems… then Decide which problem is the easiest and which one is the hardest … (to code, not to compute!) Problem Set #1 my estimates… hardest easiest (6 probs, 3 wks) important heuristic: I’m always wrong See you next Tuesday in the CS labs… ! Driving N on the Dalton Highway… (though it feels like it!) Welcome to Programming Practicum Waiting for the snow enveloping you on Route 5 N to melt “Putting the C into CS” Pittsburgh University of St. Petersburg Engineering dept. exploring martian soil On the 405, in traffic, being chased by police (and TV) helicopters. You aren’t here Worldcom Headquarters Krispy Kreme’s drive through writing clinic reports rebooting knuth (or turing or…) coding chunky strings Teaching Honors English for Janice Barbee at Pomona High School 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 What is this course about? • A chance to “improve” your programming skills What Algorithm analysis and insight Program design and implementation optimizing coding time ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with Java’s libraries OR your choice of language Research/prototype programming Unofficial course name: CS -70 1-4 / team 3 per team 2/team 2 per team Course Organization Jan 16 Jan 23 Jan 30 Feb 6 Feb 13 Feb 20 Feb 27 Mar 6 Mar 20 Mar 27 Apr 3 Welcome! Random teams of 3: 6 problems, 3 weeks Lab session to work on problems (Beckman B102 or 105) Discussion session on the first set of problems Lab session with new problems: 4 problems, 2 weeks Discussion session on the second set of problems Lab session with new problems: 6 problems, 3 weeks Discussion session on the third set of problems No class - Fall break Mock ACM contest, 9pm – 1am, teams of 3, 6 pr, 4 hours No class (out of town) Discussion session on the mock contest + Finale! You may submit problems until the end of exams… 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 should use 1 terminal per person (only the mock contest adheres to ACM rules) • these problems count for each member of the group • sometimes new problems, other times with known ones • ~1 problem per week per person… Course webpage reference links problem statements and test data problems your team has solved administrative info Grading CS 189 is graded individually... (it’s possible to take it P/F, too) 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 <file> to submit • try things out ! the reason for ACM! Choose your language… Java is almost the universal choice for the competition… • extensive library of data structures and algorithms available • I/O made simpler with 1.5’s Scanner and printf Input from stdin Output to stdout the C in CS! Choose your language… Python is nice C# Whatever language you choose def floyd_warshall(W, infinity): needs to be able to run on the n = matrix.get_num_rows(W) Macs in the CS labs (and D = matrix.clone(W) DD = matrix.make(n,n) preferably knuth, as well…) for k in xrange(n): for i in xrange(n): for j in xrange(n): DD[i][j] = min(D[i][j], D[i][k] + D[k][j]) DD, D = D, DD return D I’ll likely need your help to get things set up for testing… Others ? Marty: prolog! Problem Set #1 Input 4 4 tow cat row care ... .#. ... .## 0 0 (6 probs, 3 wks) # of words in the puzzle (to follow) # of rows in the puzzle (after the words) the words the puzzle this indicates the end of the input… Problem Set #1 Input 6 5 1 # of empty boxes on the form # of clerks in the office (three lines each) the box(es) CHECKED clerk #0 the box(es) ERASED 1 2 2 3 4 4 5 1 3 2 (6 probs, 3 wks) the clerks who get a copy clerk #1 0 1 2 3 4 5 the form clerk #2 clerk #3 1 4 2 1 0 0 0 1 3 4 5 clerk #4 Output the boxes checked the last time it leaves clerk #0's desk… this indicates the end of the input… Problem Set #1 Input (6 probs, 3 wks) list of traits, R == "recessive" D == "dominant" D traits are passed if EITHER parent has them RDDR Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 *** R traits are passed if BOTH parents have them all of the parents, gender, and traits the baby shrews… Deduce their possible parents! Frisky by Jumper-Slowpoke or Jumper-Speedy or ______ Sleepy by _________ Output Problem Set #1 (6 probs, 3 wks) Read these three problems… then Decide which problem is the easiest and which one is the hardest … (to code, not to compute!) Coaches’ Room Choose your language… Java/Cthe universal choice for the competition… • extensive library of data structures and algorithms available • I/O made simpler with 1.5’s Scanner and printf Input from stdin Output to stdout the C in CS! Choose your language… Python is nice def floyd_warshall(W, infinity): n = matrix.get_num_rows(W) D = matrix.clone(W) DD = matrix.make(n,n) for k in xrange(n): for i in xrange(n): for j in xrange(n): DD[i][j] = min(D[i][j], D[i][k] + D[k][j]) DD, D = D, DD return D Postscript! Ruby :-) Marty: prolog! Driving N on the Dalton Highway… (though it feels like it!) Welcome to Programming Practicum Waiting for the snow enveloping you on Route 5 N to melt “Putting the C into CS” Pittsburgh Victorville, for DARPA's Urban Granc Challenge University of St. Petersburg Engineering dept. exploring martian soil On the 405, in traffic, being chased by police (and TV) helicopters. You aren’t here Worldcom Headquarters Krispy Kreme’s drive-through writing clinic reports Waiting in line to vote in the Florida primaries… 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 What is this course about? • A chance to “improve” your programming skills What Algorithm analysis and insight Program design and implementation optimizing coding time ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with Java’s libraries OR your choice of 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 should use 1 machine per person (only the mock contest adheres to ACM rules) • these problems count for each member of the group • sometimes new problems, other times with known ones • ~3 problems per week per person… Class Organization Feedback from prior semesters… • there should be an opportunity to start coding “cold” • make individual vs. team-based work clear, lectures vs. labs • problems are, in general, individually completed, except • those done during the lab "mock contest" sessions • provide the code to all team members • you may or may not choose to work as a team afterwards • submit for each person (or email me…) • problems per person per week? • ~2 in the fall • ~3 in the spring • snacks and jotto! Course Organization Jan 29 Feb 5 Feb 12 Feb 19 Feb 26 Mar 4 Mar 11 Mar 18 Mar 23 Mar 25 Welcome! Review of dynamic programming: 4 problems Lab/Mock contest session: 4 problems Discussion session on geometry problems: 4 problems Lab/Mock contest session: 4 problems Lab/Mock contest session: 4 problems Discussion session on search problems: 4 problems No class… need to be away No class - Spring break Mock ACM contest, 9pm – midnight, 6 problems Discussion and wrap-up of the semester You may submit problems until the end of exams… Sat. Mar 8 and Sat. Apr 19 external competitions… Competition Options www.ccsc.org/southwestern/2008/contest.html Sat. Mar 8 and Sat. Apr 19 external competitions… www.ieee.org/web/membership/students/scholarshipsawardscontests/ieeextreme.html Course webpage references problem statements and test data problems you have solved administrative info Grading CS 189 is graded individually... (it’s possible to take it P/F, too) 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 <file> to submit • try things out ! the reason for ACM! Problem multipliers Problems are worth double if • You solve them during the 4:15 - 5:30 lab sessions the team gets credit, up to 3 people • You are the first person to use a particular language - though there is an additional responsibility here: to set up the testing system to handle that language! languages already used: python 56 c++ 11 c# ruby 12 perl 2 haskell 1 java postscript 2 6 prolog • It's one of the "extra difficult" problems, which will be determined as we go… 8 c 5 php 1 2 These multipliers may be accumulated… Dynamic programming When a seemingly intractable problem has large amounts of repeated or redundant substructure, DP can sometimes provide an efficient solution. Build a table of partial results. For example: 2 6 3 19 0 Replace computation with table look-up when possible Output Input Numbers, N, up to 106 0 marks the end of the input 10 1110 111 11001 the smallest decimal multiple of N with only the digits 0 and 1 ! Ideas? One way… Count up to the solution, starting from 1… Dynamic programming Storing intermediate results in a table for fast look-up: input N = 6 possible remainders upon dividing by N (6) 0 # of digits in answer 1 2 3 4 5 10 11 1 1 2 1 3 1 110 111 10 11 1 110 111 10 11 4 1110 DP! Only checking values for which a remainder has not yet been used… Problem Set #1 (4 problems) - divide up with one problem per group - In teams of ~3, think about - how would you solve this problem? - is it a dynamic programming problem? - how could you most simplify the programming ? - think of a 5-letter jotto word… ! Competition Options www.ccsc.org/southwestern/2008/contest.html Sat. Mar 8 and Sat. Apr 19 external competitions… www.ieee.org/web/membership/students/scholarshipsawardscontests/ieeextreme.html

Descargar
# CS 60 Slides - HMC Computer Science