Transcript Drafting Behind Akamai (Travelocity

EECS 110: Lec 2:
What is Programming?
Aleksandar Kuzmanovic
Northwestern University
http://cs.northwestern.edu/~akuzma/classes/EECS110-s09/
CS
!=
programming
What is computer science (CS)?
Take EECS 101
CS
!=
programming
What is computer science (CS)?
Take EECS 101
"not equal to"
CS
!=
programming
programming : CS ::
machining : engineering
grammar : literature
Programming
equations : mathematics
CS
a vehicle, not a destination
4
CS == computing science
Study of complexity (or complex things?)
How can it be done?
How well can it be done?
Can it be done at all?
CS == computing science
Study of complexity (or complex things?)
How can it be done?
How well can it be done?
Can it be done at all?
"equal to"
Information
What information does Google work with?
What technical problems does Google face?
Information
What information does Facebook work with?
What technical problems does Facebook face?
Information
What information does the iPhone work with?
What technical problems does the iPhone face?
Computer Science and Information
Information is life’s fundamental building block
CS is a set of fundamental techniques for
understanding and leveraging this information
10
Python and Idle
Editor window: code
Shell window: running code
Here, you can save and change
programs. Hitting F5 runs your
program over in the shell
Here, you can try things out at
the command prompt >>>
11
The foreign language of Python…
name = raw_input('Hi... what is your name? ')
print
# prints a blank line
if name == 'Ionut':
# is it Ionut?
print name, '??'
print ‘You must be a TA!'
elif name == ‘Aleksandar': # is it Aleksandar?
print ‘You must be an instructor!'
else:
# in all other cases...
print 'Welcome to Python,', name, '!'
hw0pr1.py
Homework 0, problem 112
What is programming?
Programming as learning a foreign language
1) Expect it to be different!
2) Don’t feel you need to memorize it
3) Immersion == Experimentation
13
The foreign language of Python…
syntax?
How it looks
semantics?
What it does
intent?
What it should do
name = raw_input('Hi... what is your name? ')
print
# prints a blank line
if name == 'Ionut':
# is it Ionut?
print name, '??'
print ‘You must be a TA!'
elif name == ‘Aleksandar’:
# is it Aleksandar?
print ‘You must be an instructor!'
else:
# in all other cases...
print 'Welcome to Python,', name, '!'
14
Flowchart
15
The foreign language of Python…
syntax?
How it looks
semantics?
What it does
intent?
What it should do
name = raw_input('Hi... what is your name? ')
print
# prints a blank line
if name == 'Ionut':
# is it Ionut?
print name, '??'
print ‘You must be a TA!'
elif name == ‘Aleksandar’:
# is it Aleksandar?
print ‘You must be an instructor!'
else:
# in all other cases...
print 'Welcome to Python,', name, '!'
16
The foreign language of Python
syntax?
How it looks
semantics?
What it does
intent?
What it should do
• how punctuation is used
• the language keywords that are used
• use of whitespace
• peculiarities of formatting
• how behavior is affected …
17
HW 0, Problem 2
syntax?
How it looks
semantics?
What it does
intent?
What it should do
• Save hw0pr1.py under a new name, hw0pr2.py
• Change hw0pr2.py to play rock-paper-scissors.
It does not have to play fair!
Feel free to add to the dialog, if you wish…
• Submit your hw0pr2.py in the usual way.
Stepping back from Python for a moment…18
Homework problems 3 and 4
Picobot
walls
Picobot
area not
covered
(yet!)
area
already
covered
Goal: whole-environment coverage
with only local sensing…
inspiration?
19
Picobot
walls
Picobot
area not
covered
(yet!)
area
already
covered
iRobot's Roomba vacuum
inspiration!
Goal: whole-environment coverage
with only local sensing…
20
Surroundings
Picobot can only sense things
directly to the N, E, W, and S
N
E
W
S
For example, here its surroundings are
NxWx
N E W S
Surroundings are
always in NEWS order.
21
Surroundings
How many distinct
surroundings are there?
N
E
W
S
24 == 16 possible …
xxxx
Nxxx
xExx
xxWx
xxxS
NExx
NxWx
xEWx
xExS
xxWS
NEWx
NExS
NxWS
xEWS
NxxS
NEWS
(won’t happen)
State
I am in state 0.
My surroundings
are xxWS.
Picobot's memory is a single
number, called its state.
State is the internal context of
computation.
Picobot always starts in state 0.
State and surroundings represent
everything the robot knows about the world
Rules
I am in state 0.
My surroundings
are xxWS.
Aha!
I should move N.
I should enter state 0.
Picobot moves according to a set of rules:
state
0
surroundings
xxWS
If I'm in state 0
seeing xxWS,
direction
new state
N
0
Then I move North, and
change to state 0.
Wildcards
I am in state 0.
My surroundings
are xxWS.
Aha! This matches x***
Asterisks * are wild cards.
They match walls or empty space:
state
0
surroundings
x***
direction
new state
N
0
here, EWS may be wall or empty space
What will this set of rules do to Picobot?
state
surroundings
0
0
x***
N***
1
1
***x
***S
direction
new state
->
->
N
X
0
1
->
->
S
X
1
0
Picobot checks its rules from the top each time.
When it finds a matching rule, that rule runs.
Only one rule is allowed per state and surroundings.
To do
Write rules that will always cover these two rooms.
(separate sets of rules are encouraged…)
hw0, Problem #3
hw0, Problem #4 (Extra)
but your rules should work regardless of Picobot's starting location
Alter these "up & down" rules so
that Picobot will traverse the empty
room…
the empty room
Ideas for the maze?
the maze