Preface:Magic in the StoneCS105: Great Insights in Computer ScienceWelcome!• CS105: “Great Insights in Computer Science”.• Somewhat experimental course.• Instructional technologies- Using online course support (sakai)- iClickers for in-class interaction- Programs for out-of-class interaction- Podcasting (including music videos)Survey• Do you have a clicker?A. yesB. noAbout Me• 1996: PhD, “Algorithms for Sequential Decision Making” (AI).• 1996-1999: Professor at Duke.• 2000-2002: (Back) to NJ, AT&T Labs Research.• 2002–: Rutgers: heading “Rutgers Laboratory for Real-Life Reinforcement Learning” (RL3).My Course Goals• Cool facts, cool ideas. Ideas are “how to” facts. Shoot for one or two per lecture.• People (my parents, say), don’t understand how I have a PhD in CS and can’t help them when their Windows box crashes.• If it’s not about XP, what else is there?- That’s what I want to tell you...Introduction to CS101s• Target audience: Undergrads, as a first (possibly only) computer-science course.• Seminar in Computers and Society: What impact have computers had on the world?• Introduction to Computer Science: How do I learn to create my own software?• Introduction to Computers and Their Application: What do I need to know about computing technology?Course Goals: Questions• What is Computer Science?• Why is it fun/interesting?• How is it different from software engineering?• What are the insights that make computer science its own academic discipline?Textbook• Not too daunting or detailed.• Inspiring and informative.• Pattern on the Stone, the simple ideas that make computers work, Danny Hillis, Basic Books, 1998.• Enjoyable to read; not really a textbook at all.• I will add meat to the wonderful skeleton he creates.Clickers• Available at several bookstores.• Can keep them (most popular clicker at Rutgers) or sell them back.• We’ll use them for attendence, reading comprehension quizzes, straw polls.• I’ve created some interactive demos, hope to expand the set.http://www.iclicker.com/Clicker Rules• Bring clicker to class.• Each time you do (and you make it in time for at least one question), 10 points toward class participation (CP).• Each right answer you give during class nets you another 0.2 points.• Even wrong answers are worth 0.1 points.• Perfect CP score if attend all but 3 classes. (Can be more than perfect!)• Don’t bother asking for additional slack...Syllabus: Chapters 0-2Preface: Magic in the Stone• What does the title mean?Chapter 1: Nuts and Bolts• From physics to bits.Chapter 2: Universal Building Blocks• From logic gates to a computer.Grading• Class participation (CP): 20%• Biweekly HWs: 25%• Midterm: 25%• Final (cumulative): 30%Exam questions modeled on HWSyllabus: Chapters 3-5Chapter 3: Programming• Giving the computer instructions.Chapter 4: How Universal Are Turing Machines?• How many kinds of computation are there?Chapter 5: Algorithms and Heuristics• Solving some (hard?) problems.Syllabus: Chapters 6-7Chapter 6: Memory: Information and Secret Codes• Bits as messages.Chapter 7: Speed: Parallel Computers• Computers working together.Syllabus: Chapters 8-9Chapter 8: Computers That Learn and Adapt• Can computers exceed their programming?Chapter 9: Beyond Engineering• Programs that evolve.They Are Everywhere!• 1977: “There is no reason for any individual to have a computer in his home.”• Today: Cell phone? PDA? Computers at home? Laptop? Video games? Digital camera?Survey• How many computers are with you right now? Laptop, handheld game, cell phone, GPS device, PDA, mp3 player, ...A. 0B. 1C. 2D. 3E. 4 or morePreviously UnthinkableLife After Death?One-Word Summary• If I had to summarize the intellectual contribution of computer science in one word, it would be “reduction”.• Computer scientists solve problems by reducing them to simpler problems.• We’ll see this same idea played out over and over again in different settings...Levels of Complexity• Networking (OSI Layers): application, presentation, session, transport, network, data link, physical.• Vision (Marr): computational, algorithmic, implementation.• Computing: application, high-level language, machine language, logic blocks, logic gates, physical.• Storage hierarchy: offline-storage, hard disk, RAM, cache, registers.What Does The Title Mean?• Read the preface.• Come back next time and tell me what you found out!Today’s Idea• I will start with the textbook next time, introducing bits and some simple gates.• Please read the Preface and Chapter 1.• But, I want to give you something to chew on to get those gears turning...Your Choice• Babbage’s Difference Engine- Simple computation for sequences• How do UPC barcodes work?- Hierarchy of codesA. Difference EngineB. UPC barcodesCharles Babbage: Facts• Charles Babbage lived in England in the 1800s. A polymath, he solved problems from Astronomy to Zoology.• Invented: cowcatcher, flat-rate postage, Operations Research, standard RR gauge.• Held Newton’s chair at Cambridge, but spent his last years railing against organ grinders.• His design for the analytical engine presaged much of the design of modern digital computers.The Difference Engine• Originally a “computer” was a job description of a person who created numerical tables. Useful, if tedious.• Babbage had a scheme to automate table creation using “finite differences”.• 25,000 parts, 15 tons, 8 feet high, never built!• His redesigned Difference Engine No. 2 was built in 1990 and actually worked!Difference Engine: IdeasLet’s play a game:• 0,1,2,3,4,__?• 3,5,7,9,11,__?• 1,4,9,16,25,__?• 1,3,6,10,15,__?Generating the Evens2 4 6 8 10 122 22 2 2Instructions:1. Start with 2.2. To get the next one, add 2 to the previous one.Generating Squares1 4 9 16 25 363 5 7 9 11Instructions:1. Start with 1.2. Start the increment with 3.3. To get the next one, add the increment.4. To get the next increment, add 2 to the previous one.2 2 2 24 6 8 10 124 9 16 25 361Naming The Sequences325 7 9 112 2 2The Squares2222 2 2The EvensSequence: 1,4, 9, 16, 25, 36, ...Program:1,3,2Programming the “DE”• So, to produce the Evens, we enter “2 2” into the Difference Engine and turn the crank.• The Squares are “1 3 2”.• The Triangle numbers are “1 2 1”.• Try:- Odds?- Count by 5s?- Cubes?• What do these