Transcript Everything Else You Should Know

Lecture 23:
Everything
Else You Should
Know (but won’t see
on Exam 2)
CS201j: Engineering Software
University of Virginia
Computer Science
David Evans
http://www.cs.virginia.edu/evans
Menu
• Course Evaluations
• 101 Things Every Computer Scientist
should know
• Course Charge
20 November 2003
CS 201J Fall 2003
2
Course Pledge You Signed
I will provide useful feedback. I realize this
is an experimental course and it is important
that I let the course staff know what they need
to improve the course. I will not wait until the
end of the course to make the course staff
aware of any problems. I will provide feedback
either anonymously (using the course feedback
form) or by contacting the course staff directly.
I will fill out all course evaluation surveys
honestly and thoroughly.
20 November 2003
CS 201J Fall 2003
3
Two Surveys Required
• Official SEAS Survey
– You receive email about it
– Administrators read it to determine whether or not
to fire me
• CS201J Specific Survey: handed out today
– Specific questions to help improve future editions
of CS201
• I do read all of the surveys completely
• Department head and curriculum committee
will read SEAS survey
20 November 2003
CS 201J Fall 2003
4
101 Questions
000 What is Computer Science?
001 What problem did the first electronic programmable
computer solve?
010 What are the world’s most complex programs?
011 How do Computer Scientists manage complexity?
100 What is and is not computable?
101 Who invented the Internet?
20 November 2003
CS 201J Fall 2003
5
0. What is
Computer Science?
20 November 2003
CS 201J Fall 2003
6
Let AB and CD be the two given numbers
not relatively prime. It is required to find the
greatest common measure of AB and CD.
If now CD measures AB, since it also
measures itself, then CD is a common
measure of CD and AB. And it is manifest
that it is also the greatest, for no greater
number than CD measures CD.
Euclid’s Elements, Book VII, Proposition 2 (300BC)
20 November 2003
CS 201J Fall 2003
7
The note on the inflected line is
only difficult to you, because it is so
easy. There is in fact nothing in it, but
you think there must be some grand
mystery hidden under that word
inflected!
Whenever from any point without
a given line, you draw a long to any
point in the given line, you have
inflected a line upon a given line.
Ada Byron (age 19), letter to Annabella
Acheson (explaining Euclid), 1834
20 November 2003
CS 201J Fall 2003
8
What is the
difference
between
Euclid and
Ada?
“It depends on what your
definition of ‘is’ is.”
Bill Gates (at Microsoft’s antitrust trial)
20 November 2003
CS 201J Fall 2003
9
Geometry vs. Computer Science
• Geometry (mathematics) is about
declarative knowledge: “what is”
• Computer Science is about
imperative knowledge: “how to”
– Ways of describing imperative
Language
processes (computations)
– Ways of reasoning about (predicting)
Logic
what imperative processes will do
20 November 2003
CS 201J Fall 2003
10
Was CS201J a Computer
Science Course?
• No!
– Only about 30% of CS201J is computer
science.
– Most of it is software engineering.
If you want to take a Computer Science course,
Consider taking CS200 in the Spring
20 November 2003
CS 201J Fall 2003
11
1. What problem did the first
electronic programmable
computer solve?
20 November 2003
CS 201J Fall 2003
12
Colossus
First Programmable Computer
• Bletchley Park, 1943
• Designed by Tommy
Flowers
• 10 Colossi in operation at
end of WWII
• Destroyed in 1960, kept
secret until 1970s
• 2 years before ENIAC –
calculating artillery tables
20 November 2003
CS 201J Fall 2003
13
Colossus’ Problem
• Decode Nazi high
command messages
from Lorenz Machine
• XOR encoding:
Ci = Mi  Ki
– Perfect cipher, if K is
random and secret
20 November 2003
CS 201J Fall 2003
14
Why perfectly secure?
For any given ciphertext, all plaintexts are
equally possible.
Ciphertext:
Key:
Plaintext:
20 November 2003
0100111110101
1
1100000100110
B
1000111010011
= “CS”
0
CS 201J Fall 2003
15
Breaking Lorenz
• Operator and receiver need
same keys
• Generate key bits using rotor
machine, start with same
configuration
• One operator retransmitted a message (but
abbreviated message header the second
time!)
• Enough for Bletchley Park to figure out key –
and structure of machine that generated it!
• But still had to try all configurations
20 November 2003
CS 201J Fall 2003
16
Colossus
• Read ciphertext and Lorenz wheel
patterns from tapes
• Tried each alignment, calculated
correlation with German
• Decoded messages (63M letters by 10
Colossus machines) that enabled Allies
to know German troop locations to plan
D-Day
20 November 2003
CS 201J Fall 2003
17
2. What are the world’s most
complex programs?
20 November 2003
CS 201J Fall 2003
18
Complex Programs
• Apollo Guidance Software
– ~36K instructions
• F-22 Steath Fighter Avionics Software
– 1.5M lines of code (Ada)
• 5EEE (phone switching software)
– 18M lines
• Windows XP
– ~50M lines (1 error per kloc ~ 50,000 bugs)
• Anything more complex?
20 November 2003
CS 201J Fall 2003
19
Human Genome
Produces
60 Trillion Cells (6 * 1013)
50 Million die every
second!
20 November 2003
CS 201J Fall 2003
20
DNA
• Sequence of
nucleotides: adenine
(A), guanine (G),
cytosine (C), and
thymine (T)
• Two strands, A must
attach to T and G must
attach to C
20 November 2003
CS 201J Fall 2003
G
C
T
A
21
Codons
• Three nucleotides
encode an amino acid
• Sequence of amino
acids makes a protein
• But, there are only 20
amino acids, so there
may be several
different ways to
encode the same one
From http://web.mit.edu/esgbio/www/dogma/dogma.html
20 November 2003
CS 201J Fall 2003
22
Central Dogma of Biology
(Crick, 1957)
Translation
Transcription
DNA
RNA
Protein
Image from http://www.umich.edu/~protein/
• DNA makes RNA
• RNA makes proteins
• Proteins make us
20 November 2003
CS 201J Fall 2003
23
Shortest (Known) Life Program
• Nanoarchaeum equitans
– 490,885 bases (522 genes)
= 490,885 * ¼ * 21/64 = 40,268 bytes
– Parasite: no metabolic capacity,
must steal from host
– Complete components for information processing:
transcription, replication, enzymes for DNA repair
http://www.mediscover.net/Extremophiles.cfm
KO Stetter and Dr Rachel Reinhard
• Size of compiling C++ “Hello World”:
Windows (bcc32): 112,640 bytes
Linux (g++):
11,358 bytes
20 November 2003
CS 201J Fall 2003
24
The Make-Human Program
• 3 Billion Base Pairs
– Each nucleotide is 2 bits (4 possibilities)
– 3B bases * 1 byte/4 pairs = 750 MB CD = 650 MB
– Highly redundant encoding (21/64) ~ 250 MB
• Only 5% is transcribed (exons) ~ 12 MB
– 95% junk (intons): genomes from viruses
reverse transcribed into human genome, but
inactive
Wal-Mart’s database
is 280 Terabytes
20 November 2003
CS 201J Fall 2003
25
Expressiveness of DNA
• Genetic sequence for 2 humans differs
in only 2 million bases
– 4 million bits = 0.5 MB
1/3 of a floppy disk
<1% of Windows 2000
20 November 2003
CS 201J Fall 2003
26
3. How do Computer
Scientists manage
complexity?
20 November 2003
CS 201J Fall 2003
27
Abstraction
Adapted from Gerard Holzmann’s FSE Slides
20 November 2003
CS 201J Fall 2003
28
Abstraction in CS201J
• Abstraction by Specification
– Abstract away how details by saying what a procedure
does
• Data Abstraction
– Abstract away representation details by specifying
what you can do with something
• Subtyping
– Abstract away actual type details by allowing many
types to be used in the same way (?)
• Concurrency
– Abstract away when details (?)
20 November 2003
CS 201J Fall 2003
29
4. What is and is not
computable?
20 November 2003
CS 201J Fall 2003
30
Halting Problem
Input: a procedure P
Output: true if P halts (finishes
execution), false otherwise.
Is it possible it implement a procedure that
correctly implements halts and always
terminates?
20 November 2003
CS 201J Fall 2003
31
Halts is not Computable
boolean contradictHalts (Program P)
if (halts “contradictHalts (P);”)
while (true) ;
else
return true;
If contradictHalts halts, the if test is true if enters
the while loop - it doesn’t halt!
If contradictHalts doesn’t halt, the if test if false,
and it evaluates to true. It halts!
20 November 2003
CS 201J Fall 2003
32
Learned Discussion on
Computability
(Video)
Ali G Multiplication Problem
• Input: a list of n numbers
• Output: the product of all the numbers
Is it computable?
Yes – a straightforward algorithm
solves it.
Can real computers solve it?
20 November 2003
CS 201J Fall 2003
34
Ali G was Right!
• Theory assumes ideal computers:
– Unlimited memory
– Unlimited power
– Unlimited (finite) time
• Real computers have:
– Limited memory, time, power outages, flaky
programming languages, etc.
– There are many decidable problems we cannot
solve with real computer: the numbers do matter
20 November 2003
CS 201J Fall 2003
36
5. Who Invented the Internet?
skip
20 November 2003
CS 201J Fall 2003
37
What is a Network?
A group of three or more connected
entities communicating indirectly
Ancient Greeks had beacon chain
networks on Greek island mountaintops
20 November 2003
CS 201J Fall 2003
38
Chappe’s Semaphore Network
First Line (Paris to Lille), 1794
20 November 2003
Mobile Semaphore Telegraph
Used in the Crimean War 1853-1856
CS 201J Fall 2003
39
internetwork
A collection of multiple networks
connected together, so messages can be
transmitted between nodes on different
networks.
20 November 2003
CS 201J Fall 2003
40
The First Internetwork
• 1800: Sweden and Denmark worried about
Britain invading
• Edelcrantz proposes link across strait
separating Sweden and Denmark to connect
their (signaling) telegraph networks
• 1801: British attack Copenhagen, transmit
message to Sweden, but they don’t help.
• Denmark signs treaty with Britain, and stops
communications with Sweden
20 November 2003
CS 201J Fall 2003
41
First Use of The Internet
• October 1969: First packets on the
ARPANet from UCLA to Stanford.
Starts to send "LOGIN", but it crashes
on the G.
• 20 July 1969:
Live video (b/w) and
audio transmitted from
moon to Earth, and to
several hundred million
televisions worldwide.
20 November 2003
CS 201J Fall 2003
42
Licklider and Taylor’s Vision
Available within the network will be functions and services to
which you subscribe on a regular basis and others that you
call for when you need them. In the former group will be
investment guidance, tax counseling, selective dissemination
of information in your field of specialization, announcement of
cultural, sport, and entertainment events that fit your
interests, etc. In the latter group will be dictionaries,
encyclopedias, indexes, catalogues, editing programs,
teaching programs, testing programs, programming systems,
data bases, and – most important – communication, display,
and modeling programs. All these will be – at some late
date in the history of networking - systematized and
coherent; you will be able to get along in one basic
language up to the point at which you choose a
specialized language for its power or terseness.
20 November 2003
J. C. R. Licklider and Robert W. Taylor, The Computer
as a Communication Device, April 1968
CS 201J Fall 2003
43
The Modern Internet
• Packet Switching: Leonard Kleinrock (UCLA),
Donald Davies and Paul Baran, Edelcrantz’s
signaling network (1809)
• Internet Protocol: Vint Cerf, Bob Kahn
• Vision, Funding: J.C.R. Licklider, Bob Taylor
• Government: Al Gore (first politician to promote
Internet, 1986; act to connect government networks
to form “Interagency Network”)
20 November 2003
CS 201J Fall 2003
44
Charge 1
• Exam 2
– Out today
– Due Friday at 3:55PM
– Turn in to folder outside my office
20 November 2003
CS 201J Fall 2003
45
Charge 2
• Course Evaluations
– SEAS Survey: follow the email instructions
– Course Specific survey
• Handed out today
• Turn in to folder outside my office when you turn in
your exam
20 November 2003
CS 201J Fall 2003
46
Charge 3
Change the
World!
Caveat: before worrying about changing the
world, make sure you turn in your exam Friday!
20 November 2003
CS 201J Fall 2003
47
Small, Simple Programs
that Changed the World
eBay (P. Omidyar)
WorldWideWeb
VisiCalc
(Tim Berners-Lee)
(Dan Bricklin and Bob Frankston)
Smalltalk
(Adele Goldberg, Alan
Kay, Dan Ignalls)
Altair BASIC
(Bill Gates and Paul Allen)
Napster
(Shawn Fanning
and Sean Parker)
Tetris
(Alexey Pazhitnov)
20 November 2003
CS 201J Fall 2003
?
(CS201J Student)
48
Lawn Lighting:
7pm Thursday
Never doubt that a small group of
thoughtful, committed people can
change the world.
Indeed, it is the only thing that ever has.
Margaret Mead