A Brief History of Computer Science William Klostermeyer Typical Conversation A: What do you do? B: Im a computer scientist. A: How come when Im on screen X in MS Y.Z I cant print file Q? Computer science is no more about

computers than astronomy is about telescopes. E. Dijkstra (1972 Turing Award winner) What is computer science? Sometimes called computing or computing science. Not so much about computers, but computing.

Areas of Computer Science Hardware/Architecture Building chips, machines, devices Software Building programs, systems, databases Theory Determines what is possible: underlies all other areas of computing.

History of computer science Pre-dates modern computers by more than 2000 years! Digital computers make it more practical to compute. Computer was a job title for people around time of WWII Computers

Electronic computers created because of need for them: Ballistics computations Codebreaking Census calculations

Algorithm Precise set of instructions to solve a problem. How to play blackjack: draw two cards; compute total while (total < 17) draw a card

add cards to total end Mathematics of Algorithms Hilbert (1928): Can every problem be solved by a mechanical procedure?

Turing (1936): NO! There exist problems no computer can solve. Alan Turing: developed model of computation Programs Computer programs implement

algorithms and are written in a computer language (Java, C, etc.) Interested in efficient (FAST) algorithms/programs Hard Problems Hilberts 10th problem (1900): Does there exist an algorithm to find integer solutions to Diophantine

equations? x + 2y2 = 0 (use quadratic formula) x6 + y 6 = z 6 Hilberts 10th problem

Matiyasevich proved in 1970 that no algorithm exists to solve arbitrary Diophantine equations. Some problems yield themselves to algorithms, some dont. Some yield themselves to EFFICIENT

algorithms! Computer science is the systematic study of algorithmic processes From an ACM study (1989) Ancient Algorithms

Babylonians knew how to approximate square roots (500 B.C.) Newtons method (1600s) generalizes this to find zeroes of polynomial Numerical algorithms Gaussian elimination

Euclids Algorithm 300 B.C. GCD(x, y) greatest common divisor of x & y Still in use today!

GCD Algorithm Euclid(12, 9) = Euclid(9, 3) = Euclid(3, 0) = 3 Euclid(a, b): if b=0 return b else return Euclid (b, a mod b)

Prime Numbers x is prime if nothing divides x evenly except 1 and x Some primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Big primes useful in cryptography Sieve of Eratosthenes 250 B.C. Algorithm to determine if x is prime: x=17. List all numbers from 2 to 16. Start with 2. If 2 does not divide 17, cross 2 and all multiples of 2 off list. Go to next uncrossed number on list and repeat.

If all numbers crossed off, then x is prime. Primality Testing Eratosthenes method not fast for LARGE numbers (hundreds of digits) Fast probabilistic methods developed in 70s, 80s (have a small chance of error)

Breakthrough! 2002: after centuries of searching, a fast algorithm found (polynomialtime algorithm, no chance of error) IIT professor and two undergrads: Uses of Prime Numbers

Large primes needed in cryptography (to securely send information over internet) RSA encryption algorithm based on assumption that factoring large integers into primes is difficult. RSA Algorithm 1.

2. 3. Find P and Q, two large (e.g., 1024-bit) prime numbers. Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime. E must be odd.

Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). RSA cont. The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer). 2. Your public key is the pair (PQ, E). Your private key is the number D. D used in

decrypting C back into T. No known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). 1. Factoring

RSA security based on assumption that FACTORING large integers is hard. Note that we can determine if an integer is prime or not quickly, but factoring seems to require more work In other words: can prove an integer is composite w/o showing factors Graph Algorithms

Euler 1736: Bridges of Konigsberg Konigsberg = Graph Graphs Concepts from graph theory may hold the key for everything Business Week, January 22, 2002

Shortest Routes Dijkstras Algorithm (1959): used by www.mapquest.com Faster algorithms found in 1990s Traveling Salesman

Salesman wants to visit N cities and return home Minimize total distance traveled TSP Algorithms?

No fast algorithm known to compute best route for salesman Computing optimal route for 1000 cities would take centuries on fast computer Must settle for near-optimal solutions: Can get very close to optimal if cities

are in Euclidean plane (Arora 1999) Map Coloring Can map be colored with 4 colors so neighboring regions have different colors (1850s) 4-color theorem

Yes! (Appel & Haken 1970s) Can be done quickly (1990s) But some maps require only 3 colors! Biological Problems

Find best match for criminals DNA sequence in a database: AATCCGATAGGAT ATTCCAGATCGAT TACCGATAGACAT GTACAGGCAATCA AAACCC GATACAAATCCGA Sequence Assembly

Assemble small overlapping sequences into single long sequence AAAATCGC, CGCATAAA, GCATCTCATT CGCATAAAATCGCATCTATT Can be hard if you start with lots of fragments Easy & Hard

Which is harder? Taking a test Grading a test Proving a theorem

Checking a proof Hilbert and von Neumann pondered this. P vs. NP P: problems that can be solved quickly (shortest route) NP: problems whose solutions can be checked quickly (TSP, 3coloring) Is this a 3-coloring?

P = NP? Believed P is not equal to NP $1,000,000 reward for proof: www.claymath.org Are certain problems intrinsically hard?

NP-complete problems Class of hard problems (unless P=NP) Occur in real world:

Scheduling problems, routing problems, Biological problems, etc. Optimal solutions take too long to compute (we believe, if P not equal to NP) Must settle for sub-optimal solutions. Complexity Theory

Interested in categorizing how hard (complex) problems are. Key concept is a proof that an object satisfies some conditions. How might we prove that 11 is prime? See that none of 2, 3, 5, 7 divide 11.

Checking Proofs How do we grade a test? How do we check a proof? xn + yn = zn, no solutions for n > 2

By reading it! By reading every word of it! PCP Theorem 1990s was found that proofs can be checked (with high probability)

by reading only a few characters. (Proof must be in a standard form) Holographic proofs: each symbol contains essence of proof Amazing connection PCP Theorem also tells us that for certain hard problems, finding suboptimal solutions quickly is hard!

Hard to quickly find a route that is close to the longest possible route between two cities! Conclusion Computer science is about: Algorithms to solve problems!