COS 126General Computer ScienceFall 2010Robert Sedgewick2OverviewWhat is COS 126? Broad, but technical, introduction to computer science.Goals.•Demystify computer systems.•Empower you to exploit available technology.•Build awareness of substantial intellectual underpinnings.Topics.•Programming in Java.•Machine architecture.•Theory of computation.•Applications to science, engineering, and commercial computing. “ Computers are incredibly fast, accurate, and stupid; humans are incredibly slow, inaccurate, and brilliant; together they are powerful beyond imagination. ” ! Albert EinsteinLectures. [Sedgewick]RS office hours.Precepts. [Gabai · Ginsburg · Vertanen · Lee · Lee · Nagorna · Steiglitz· Jones · Stewart · Zhu ]•Tips on assignments / worked examples•Questions on lecture material.•Informal and interactive.Friend 016/017 lab. [Ugrad assistants]•Help with systems/debugging.•No help with course material.Reading period. No lectures; precepts Jan 4-5.3The BasicsSMTWTFS910111212112233456778891011everyone needs to meet me!See www.princeton.edu/~cos126for full details and preceptor office hours. 4GradesCourse grades. No preset curve or quota.9 programming assignments. 40%.2 exams (in class, 10/21-22 and 12/16-17). 50%.Final programming project (due Dean’s date - 1). 10%.Extra credit / staff discretion. Adjust borderline cases.you are hereparticipation helps, frequent absence hurtsSu Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 1819 20 21 22 23 24 2526 27 28 29 30 1 2 3 4 5 6 7 8 910 11 12 13 14 15 1617 18 19 20 21 22 2324 25 26 27 28 29 3031 1 2 3 4 5 6 7 8 9 10 11 12 1314 15 16 17 18 19 2021 22 23 24 25 26 2728 29 30 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 1819 20 21 22 23 24 2526 27 28 29 30 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 17 18 19 20 21 2223 24 25 26 27 28 2930 31JAN DEC NOV OCT SEPDue dates5Course MaterialsCourse website. [www.princeton.edu/~cos126]•Submit assignments, check grades.•Programming assignments.•Lecture slides.Required readings. Sedgewick and Wayne. Intro to Programming in Java: An Interdisciplinary Approach. Recommended readings. Harel. What computers can't do. print before lecture;annotate during lectureskim before lecture;read thoroughly afterwards6Programming AssignmentsDesiderata.•Address an important scientific or commercial problem.•Illustrate the importance of a fundamental CS concept.•You solve problem from scratch!N-body simulationestimate Avogadro's numberpluck a guitar string7Programming AssignmentsDesiderata.•Address an important scientific or commercial problem.•Illustrate the importance of a fundamental CS concept.•You solve problem from scratch!Due. Mondays 11pm via Web submission.Computing equipment.•Your laptop. [OS X, Windows, Linux, iPhone, … ]•OIT desktop. [Friend 016 and 017 labs]8What's Ahead?Lecture 2. Intro to Java.Precept 1. Meets today/tomorrow.Not registered? Go to any precept now; officially register ASAP.Change precepts? Use SCORE.Assignment 0. [www.princeton.edu/~cos126/assignments.php] •Due Monday 11PM.•Read Sections 1.1 and 1.2 in textbook.•Install Java programming environment + a few exercises.•Lots of help available, don't be bashful.END OF ADMINISTRATIVE STUFFsee Colleen Kenny-McGinley in CS 210if the only precept you can attend is closed90. Prologue: A Simple Machine10Secure Chat with a One-Time PadAlice wants to send a secret message to Bob•Sometime in the past, they exchange a one-time pad.•Alice uses the pad to encrypt the message.Key point: Without the pad, Eve cannot understand the message.Secure Chat 1.0 [alice][alice]: Hey, Bob [bob]: Hi, Alice![alice]: SENDMONEYEncrypt SENDMONEY with yT25a5y/SSecure Chat 1.0 [bob][alice]: Hey, Bob [bob]: Hi, Alice![alice]: gX76W3v7K “use yT25a5y/S if I ever send you an encrypted message”11Encryption MachineGoal. Design a machine to encrypt and decrypt data.S E N D M O N E YdecryptS E N D M O N E Yencryptg X 7 6 W 3 v 7 K12Encryption MachineGoal. Design a machine to encrypt and decrypt data.Enigma encryption machine.•"Unbreakable" German code during WWII.•Broken by Turing bombe.•One of first uses of computers.•Helped win Battle of Atlantic by locating U-boats.S E N D M O N E YdecryptS E N D M O N E Yencryptg X 7 6 W 3 v 7 K13A Digital WorldData is a sequence of bits. [bit = 0 or 1]•Text.•Programs, executables.•Documents, pictures, sounds, movies, …Copyright 2004, Sidney Harris http://www.sciencecartoonsplus.comimage courtesy of David Augustthousands of bits billions of bits14A Digital WorldData is a sequence of bits. [bit = 0 or 1]•Text.•Programs, executables.•Documents, pictures, sounds, movies, …Ex. Base64 encoding of text. •Simple method for representing A-Z, a-z, 0-9, +, /•6 bits to represent each symbol (64 symbols)000000 A 001000 I 010000 Q 011000 Y 100000 g 101000 o 110000 w 111000 4000001 B 001001 J 010001 R 011001 Z 100001 h 101001 p 110001 x 111001 5000010 C 001010 K 010010 S 011010 a 100010 i 101010 q 110010 y 111010 6000011 D 001011 L 010011 T 011011 b 100011 j 101011 r 110011 z 111011 7000100 E 001100 M 010100 U 011100 c 100100 k 101100 s 110100 0 111100 8000101 F 001101 N 010101 V 011101 d 100101 l 101101 t 110101 1 111101 9000110 G 001110 O 010110 W 011110 e 100110 m 101110 u 110110 2 111110 +000111 H 001111 P 010111 X 011111 f 100111 n 101111 v 110111 3 111111 /Secure Chat with a One-Time PadFirst challenge: Create a one-time pad.Good choice: A random sequence of bits (stay tuned).Note: any sequence of bits can be encoded as characters15one-time pad110010 010011 110110 111001 011010 111001 100010 111111 010010y T 2 5 a 5 y / Sencoded as characters16decchar binaryBase64 EncodingA 0 000000B 1 000001… … …M 12 001100… … …One-Time Pad EncryptionEncryption.•Convert text message to N bits.messageS E N D M O N E Ybase64010010 000100 001101 000011 001100 001110 001101 000100 01100017One-Time Pad EncryptionEncryption.•Convert text message to N bits.•Use N random bits as one-time pad.messagebase64010010 000100 001101 000011 001100 001110 001101 000100 011000S E N D M O N E Yone-time pad110010 010011 110110 111001 011010 111001 100010 111111 010010y T 2 5 a 5 y / S18messagebase64S E N D M O N E Y010010 000100 001101 000011 001100