class01-black-16-intro

Download this Presentation

0

Presentation Transcript

  • 1.The CS5 Times Eager Penguins Invade Computer Lab Claremont (AP): The first-day offering of Harvey Mudd’s popular CS5 laboratory was disrupted when a large flock of penguins took every seat in the room. “They’re cute,” complained a distraught student, “but they smell like fish and there’s no room for us.” Professors attempted to drive the penguins away by repeatedly shouting “Shark!”, but the penguins were unmoved. Handouts (read them all!): Today’s lecture notes A preprinted blank "worksheet” Light reading? ;^) Prof. Geoff Kuenning, Olin 1255 http://www.cs.hmc.edu/~geoff/geoff-schedule.html (Official course alien)
  • 2.Overview Weeks 1-3: Thinking functionally Weeks 4-6: Computer organization Weeks 7-10: Oops! (Object oriented programs) Weeks 11-14: Theoretical foundations Capstone Project! 14 weeks of action-packed excitement!
  • 3.Programming Languages… * A+ * A++ * A# * A-0 programming language * ABAP * ABC * ABC ALGOL * ABLE * ABSET * ABSYS * ACC * Accent * ACT-III * ATOLL - Acceptance, Test Or Launch Language * Action! * ACS * ActionScript * Actor * Ada 2000 languages omitted * YAFL * Yellow - Rejected prototype for Ada * Yorick * Y Language * Z notation - A program specification language, like UML * ZOPL. * ZPL * ZUG * ZZT-oop
  • 4.Python Relatively “nice” syntax Emerging as language of choice in many fields Packages for graphics, audio, scientific computing, … Befunge class HelloWorld { static public void main( String args[] ) { System.out.println( "Hello World!" ); } } Java print(“Hello World”) Python Prof. Geoff takes on Python…
  • 5.Hello World… #include main() { cout << "Hello World!" << endl; return 0; } C++ Ook
  • 6.Some Things You’ll Do This Semester… Sequence alignment ATTATCG ACATTC Distance is 4 ATTAT-CG A-CATTC- ATTATCG -> A TATCG -> A CAT_CG -> A CATTCG -> A CATTC Delete T Change T to C Insert T here Delete G
  • 7.Spel Cheking…
  • 8.Huffman Data Compression
  • 9.Connect 4 AI
  • 10.The Alien's Life Advice SMILE! It makes people think you’re fun to be with.
  • 11.Picobot area already covered area not covered (yet!) walls Goal: whole-environment coverage with only local sensing… Picobot! Murata Girl Roomba This language is not Turing-Complete. I guess that makes it “unreasonable”! DEMO! Reading: Chapter 1 in the book (http://www.cs.hmc.edu/csforall/)
  • 12.Environment in the NEWS! Picobot can only sense things directly to the N, E, W, and S For example, here its surroundings are NxWx N E W S N E W S Surroundings are always in NEWS order.
  • 13.How many distinct surroundings are there? N E W S xxxx Nxxx xExx xxWx xxxS NExx NxWx NxxS xEWx xExS xxWS NEWx NExS NxWS xEWS NEWS (won’t happen) == 16 possible … 24 Surroundings
  • 14.State Picobot's memory is a single number, called its state. State is the internal context of computation. State and surroundings represent everything the robot knows about the world Picobot always starts in state 0. I am in state 0. My surroundings are xxWS.
  • 15.Rules Picobot moves according to a set of rules: state surroundings 0 xxWS 0 N direction new state If I'm in state 0 seeing xxWS, Then I move North, and change to state 0. Aha! I should move N. I should enter state 0. A capital “X” here means “Don’t Move” I am in state 0. My surroundings are xxWS.
  • 16.Wildcards Asterisks * are wild cards. They match walls or empty space: 0 x*** 0 N state surroundings direction new state and EWS may be wall or empty space I am in state 0. My surroundings are xxWS. Aha! This matches x*** N must be empty
  • 17.What Will This Set of Rules Do to Picobot? 0 x*** 0 N 0 N*** 0 X state surroundings direction new state Picobot checks its rules from the top each time. Only one rule is allowed per state and surroundings. When it finds a matching rule, that rule runs. -> -> Add some code here to make Picobot go up and down in the same column forever! A capital “X” here means “Don’t Move”
  • 18.0 x*** 0 N 0 N*** 1 X 1 ***x 1 S 1 ***S 0 X state surroundings direction new state Picobot checks its rules to find one that applies Only one rule is allowed per state and surroundings. When it finds a matching rule, that rule runs. -> -> -> -> What Will This Set of Rules Do to Picobot?
  • 19.This Week! Write rules that will always cover these two rooms. (separate sets of rules are encouraged…) Lab Problem Problem 2 our best: 4 states, 8 rules our best: 3 states, 7 rules (but Cam Zhou had 6) Your “program” can be slow but it should work for any starting location and for any wall-connected maze! DEMO!
  • 20. What’s the Point? Simple syntax can support “powerful” computation: The picobot language syntax is very simple, yet it can control a robot in a complex environment. Computer scientists examine limitations of languages: Are there environments that the picobot language cannot navigate? If so, what features could be added to give the language more “power”?
  • 21.How About “General” Rooms? Picobot has 100 states, but the “room” could be arbitrarily big and weird!
  • 22.Python and the Command Line Python makes it easy to experiment! I goofed here No worries, just try again This way I don’t have to say math.pi
  • 23.Python and the Command Line Python makes it easy to experiment!
  • 24.Defining Your Own Functions! def dbl(x): return 2 * x dbl x 2 * x def dbl(myArgument): myResult = 2 * myArgument return myResult Notice the indentation. This is done using “tab” and it’s absolutely necessary! “Outdent” with shift-tab! Sublime often indents for you!
  • 25.def dbl(x): ”””This function takes a number x and returns 2 * x””” return 2 * x Docstrings! This is sort of like teaching your programs to talk to you!
  • 26.# Doubling program # Author: Ran Libeskind-Hadas # Date: August 27, 2011 # Time Spent: 14 hours def dbl(x): ”””This function takes a number x and returns 2 * x””” return 2 * x Docstrings…and Comments
  • 27.Composition of Functions def quad(x): return 4 * x quad x 4 * x def quad(x): return dbl(dbl(x)) Doubly cool!
  • 28.# myFunc # Author: Ran Libeskind-Hadas # Date: August 27, 2011 def myFunc(x, y): “””returns x + 42 * y“”” return x + 42 * y Multiple Arguments... myFunc x, y x + 42 * y That’s a kind of a funky function!
  • 29.def dbl(x): “””returns 2 * x“”” return 2 * x >>> list(map(dbl, [0, 1, 2, 3, 4])) [0, 2, 4, 6, 8] def evens(n): myList = range(n) doubled = list(map(dbl, myList)) return doubled Mapping with Python... def evens(n): return list(map(dbl, range(n))) Alternatively….
  • 30.from functools import reduce def add(x, y): """returns x + y""" return x + y >>> reduce(add, [1, 2, 3, 4]) 10 reduce-ing with Python... add add add
  • 31.Google’s “Secret” This is what put Google on the map!
  • 32.Try This… Write a function called span that returns the difference between the maximum and minimum numbers in a list… >>> span([3, 1, 42, 7]) 41 >>> span([42, 42, 42, 42]) 0 min(x, y) max(x, y) These are built in to Python!
  • 33.Try This... Write a python function called gauss that accepts a positive integer N and returns the sum 1 + 2 + … + N 2. Write a python function called sumOfSquares that accepts a positive integer N and returns the sum 12 + 22 + 32 + … + N2 You can write extra “helper” functions too!