COS 116: The Computational UniverseInstructor: Sanjeev AroraCOS 116: The Computational Universe! Instructor: Sanjeev Arora (arora@cs)! Head TA: J. Alex Halderman (jhalderm@cs)! Preceptors: " Umar Syed (usyed@cs)" David Xiao (dxiao@cs)! Labs will be held in (Friend 005)" Mon 7-10, Tues 7-10, Wed 1:30-4:20! This week: Take-home labAncient dream of man: “Breathe life into matter”Robot(Karel Capek, 1921)Frankenstein (Mary Shelley,1818)“Automata”, (South Germany or Spain, c. 1560) Also,chessautomataGolem (Jewish mythology)“Breathe life into matter” –Another perspective“Breathe life into matter” –A 20thcentury perspective! “Matter”: Atoms, molecules, quantum mechanics, relativity …! “Life”: Cells, nucleus, DNA, RNA, …! “Breath life into matter”: ComputationOne interpretation: Make matter do useful, interesting things on its ownComputational UniverseSome important distinctionsComputer Science vs. Computer Programming(Java, C++, etc.)Notion of computationvs. Concrete Implementations of Computation (Silicon chips, robots, Xbox, etc.)No programming in this course!! Not necessary for conceptual understanding! Gives us more time for a broader coverage of computer science (broader than COS126!)! No advantage to those who have prior programming experienceBrief history of computers / computation! Technological:" Clocks" Clockwork “Automata”" Mechanized looms, steam engines" Vacuum tubes, electronic calculators (1910-1930’s)" ENIAC (1945)" von Neumann Computer(1949, Princeton)Brief history of computers / computation (cont’d)! Intellectual" Ancient Greeks, philosophers (“How to formalize thought?”)" Boolean logic (G. Boole, 1815-1864)" Crisis in math! Hilbert: Call to axiomatize math! Gödel: Incompleteness theorem" Lambda calculus (A. Church, 1936)" Turing machines (A. Turing, 1937)Both at Princeton;First clear notion of “What is computation?”Computer Science:A new way of looking at the worldExample 1:Example 2: Public closed-ballot elections! Hold an election in this room" Everyone can speak publicly (i.e. no computers, email, etc.)" At the end everyone must agree on who won and by what margin" No one should know which way anyone else voted! Is this possible?" Yes! (A. Yao, Princeton)Example 3: Computational BiologyOld Biology New BiologyMicroarraysPathwaysCOS 116 : Course structure! First 10 lectures:" Cool things computers do and how! Next 8 lectures:" What’s inside computers, Internet, silicon chips! Last 6 lectures:" Complexity, cryptography, viruses, search engines, artificial intelligenceThis week’s lab: Blogs & HTML(Take-home Lab; pick up “manual” today)TextThis week:skim Chapter 1, read pp 12-21, pp 32-51.Lab in Weeks 2 and 3: Scribbler. What determines its behavior?(Each student getsone robot)Bureaucratic details! 3 hour lab sessions:" M 7-10, Tu 7-10, W 1:30-4:30" Not assigned a session yet? Come see us today after class!! 1 hour “optional” precept:" No new material, will explain lecture, help with HW/labs" Time will be decided today! This week’s lab is take-home: Start your blogGrading! Final (in-class): 35%! Lab reports (including answering questions): 35%! Participation (in class, on blog): 15%! Midterm (take-home): 15%! Attendance at lectures is expected:" Homeworks / lab assignments are handed out and due in
View Full Document