Driving N on the Dalton Highway… (though it feels like it!) Welcome to

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 Pittsburgh “Putting the C into CS” 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 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

What is this course about? A chance to “improve” your programming skills What Algorithm analysis and insight Program design and implementation optimizing coding time

What is this course about? A chance to “improve” your programming skills What Algorithm analysis and insight Program design and optimizing coding time implementation ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with C ’s STL or Java’s API options in the spring ) Research/prototype programming (more

What is this course about? A chance to “improve” your programming skills What Algorithm analysis and insight Program design and optimizing coding time implementation ACM programming contest Why Hands-on practice with algorithms and techniques Familiarity with C ’s STL or Java’s API options in the spring ) Research/prototype programming Unofficial course name: 70 CS - (more

2006 ACM Results http://socalcontest.acm.org/ http://icpc.baylor.edu/icpc/ Site for the regionals Site for the world finals

Class Organization Feedback from prior semesters lab sessions not considered best use of time more contest-like practice sessions there should be opportunities to start coding “cold” better to have the course graded individually continue to play jotto have better snacks -- need more feedback here

Course Organization Sep 4 Sep 11 Sep 18 Sep 25 Oct 2 Oct 9 Oct 16 Oct 23 Oct 30 Nov 6 Nov 10 Nov 13 Welcome! (topic: dynamic programming) Practice session to work on problems (here - laptops?) Discussion session (topic: graph algorithms) Practice session (here ) Discussion session (topic: search problems) Practice session (here ) Discussion session (topic: geometry/parsing) No class - Fall break Mock ACM contest, 9pm – 1am, teams of 3, in CS labs Brief meeting for the ACM contest participants Regional ACM contest in Riverside Wrap-up session for everyone

Problems and grades alternating format discussion sessions problem and program analysis strategy, coding tips 3 problems, count individually Problems can be done any time during the term. Problems solved during the lab sessions count as 2 problems before 6pm lab sessions 3 problems can be done by team or individually -- you decide meet here in this room (?) bring a laptop - I'll have some too. contest conditions: new problems one computer per team credit for the entire team

Course webpage reference links problem statements and example I/O people results!! 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 during lab "contests", you may only use C or Java API references anyother time, you may use any reference at all except an existing solution or partial solution use /cs/ACM/acmSubmit file to submit try things out ! the reason for

Java ! Not required (C is the alternative), but consider. extensive library of data structures and algorithms available I/O made simpler with 1.5’s Scanner and printf formatted output parsed input the C in

Problem Set #1: Dynamic Programming

Problem Set #1: Dynamic Programming Rob Gonsalves www.sapergalleries.com/Gonsalves.html

Problem Set #1: multiple.java 2 6 3 19 0 Input 0 marks the end of the input integers (N) with N 10000 change! 2

Problem Set #1: multiple.java 2 6 3 19 0 Input 0 marks the end of the input integers (N) with N 10000 2 change! Output 10 1110 111 11001 change! the smallest (decimal) multiple of N with only the digits 0 and 1 !

Problem Set #1: Ideas? Most naïve solution multiple.java 2 6 3 19 0 Input 0 marks the end of the input integers (N) with N 10000 2 change! how can we save time? Output 10 1110 111 11001 change! the smallest (decimal) multiple of N with only the digits 0 and 1 !

Dynamic programming Storing intermediate results in a table for fast look-up: multiple.ja va 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

Problem Set #1: Java Classes BigInteger LinkedList String int[] multiple.java 2 6 3 19 0 Input 0 marks the end of the input integers (N) with N 10000 2 change! Output 10 1110 111 11001 change! the smallest (decimal) multiple of N with only the digits 0 and 1 !

Coding tips: multiple.java import java.util.Scanner; import java.util.LinkedList; import java.math.BigInteger; class multiple { public static void pl(String s) { System.out.println(s); } public static void pld(String s) { /* pl(s); */ ; }

Coding tips: multiple.java import java.util.Scanner; import java.util.LinkedList; import java.math.BigInteger; class multiple { public static void pl(String s) { System.out.println(s); } public static void pld(String s) { /* pl(s); */ ; } public static void main(String[] argv) { Scanner s new Scanner(System.in); int[] remainders; LinkedList String LL; // for input // the DP table // a queue

Coding tips: multiple.java while (true) { LL new LinkedList String (); LL.addLast("1"); while (LL.size() 0) { String next LL.removeFirst(); // while there is input // new, empty queue // starting value // more data left? // dequeue from front the LinkedList class is a ready-made Deque

Coding tips: multiple.java the BigInteger constructor takes a String BigInteger r0 big (new BigInteger(next0)).remainder(input); int r0 r0 big.intValue(); if (r0 0) { pl(next0); break; } // // // // convert to an int we're done! print the answer go to next input

Coding tips: multiple.java the BigInteger constructor takes a String BigInteger r0 big (new BigInteger(next0)).remainder(input); int r0 r0 big.intValue(); if (r0 0) { pl(next0); break; } // // // // convert to an int we're done! print the answer go to next input // // // // have we seen this one? 42 marks it as seen for debugging put next0 on the queue our table if (remainders[r0] 0) { remainders[r0] 42; pld(" " next0 "," r0); LL.addLast( next0 ); }

Jotto! A word-guessing game similar to mastermind Sophomores Juniors fjord 3 fjord 0 Seniors fjord 1 Me fjord 2

Problem Set #1: bookcase.java 1 4 220 29 195 20 200 9 180 30 Input number of data sets number of books in this data set height and width of each book

Problem Set #1: bookcase.java 1 4 220 29 195 20 200 9 180 30 Input number of data sets number of books in this data set height and width of each book 220 Fit the books tightly onto a rectangular, 3-shelf bookcase: 29 200 20 9 180 30 30

Problem Set #1: bookcase.java 1 4 220 29 195 20 200 9 180 30 Input number of data sets number of books in this data set height and width of each book 220 Fit the books tightly onto a rectangular, 3-shelf bookcase: Output 29 200 20 9 180 30 What is the smallest total area for such a bookshelf? 30

Problem Set #1: Thoughts? bookcase.java 1 4 220 29 195 20 200 9 180 30 Input number of data sets number of books in this data set height and width of each book 220 Fit the books tightly onto a rectangular, 3-shelf bookcase: Output 29 200 20 9 180 30 What is the smallest total area for such a bookshelf? 30

Tracking width, height, and books Consider the books in order of height (decreasing) Key decisions will be given some number of books on the first two shelves, the width of the shelves and the height of the shelves 0 width of Shelf #1 0 how many of the tallest books in top two shelves 1 2 3 Contains: smallest possible height of shelf #2

See you next time!

Coaches’ Room