Introduction To Computer Science
Introduction to Computer ScienceCSCI 109China – Tianhe-2Andrew GoodneyFall 2019Lecture 1: IntroductionAugust 26, 2019
Purpose of this CourseuIntroduce computer science as a discipline, a body ofknowledge, and a domain of science/engineeringvvuuWhat is computing, a computer, science (and engineering)?How do computers work?vuComputers, architectures, data structures and algorithms,programming, operating systems, networks, abstract machines andtheory, artificial intelligence, robotics, human computer interaction, What is comprised within the domain of computing?vvuThe focus is on ideas and conceptsSignificant amounts of reading but no programming (see CSCI 103L)Comprehending its content and structureAppreciating its past, present and futureProvide a basis upon which you can build throughout theremainder of your computing education2
Purpose of this Course3
Course Outline4
1. How many college level computer classes have you completed?a. 0b. 1c. 2d. 3e. 4 or more2. How many years of computer programming have you done?a. 0b. 1c. 2d. 3e. 4 or more3. How many programming languages do you know?a. 0b. 1c. 2d. 3e. 4 or more4. Are you taking CS 103 concurrently with this class?a. Yesb. No5. Your reason for taking CS 109 isa. Required for your current major or minor.b. Not required for your current major or minor but is required for a major or minoryou want to add (or move to).c. Not required for your current major or minor nor for a major or minor you areconsidering but you are interested in learning about Computer d: CS109Fall2019ì5
Logisticsì6
Instructor and TAsuuuInstructor: Andrew GoodneyOffice: PHE 406Office Hour: See course websiteuContact Info:goodney@usc.eduMax Pfluegerpflueger@usc.eduOffice: TBDOffice Hour: TBDTeaching Assistants (TAs)Artem Molchanovmolchano@usc.eduOffice: TBDOffice Hour: TBDNote: Office hours start next week! See course website for details.7
Important InfouClassvLocation: SGM 123Days & Time: M 12:00-13:50uThere are no discussion or quiz sectionsuCo-requisite : CSCI 103LvuThere is no prerequisiteRequired TextbookvComputing for Ordinary Mortals, St. Amant, R. OxfordUniversity Press, 2013Syllabus is on http://bytes.usc.edu/cs109/u Slides will be posted on “bytes”u Other reading material will be made available thereu8
Homework (30%)Four homeworks (7.5% each)u Collaboration is welcome on the homeworkuvuYou are allowed a total of two late days on thehomeworkvvvuBut copying is not permittedOne homework may be 2 days late, or two may be 1 day late,with no penaltyOnce late days are used, one day late reduces the score by25%, two days late reduces the score by 50%, no credit is givenfor three or more days lateAll 4 homeworks must be submitted to earn a passing gradeAll homework submissions must be typed9
Quizzes (5%), Midterm (30%),Final (35%) 8 in-class quizzesu No collaboration is permitted on the quizzesu Best five scores will be retained so quizzes are worth 5%of your gradeuuu1 midterm: worth 30% of your overall grade1 final exam (cumulative): worth 35% of your overallgrade10
Quiz policyThere are absolutely no make up quizzes. If you need to be away fromclass to see a doctor, or to play on a sports team, the missed quizzes needto come from your quota of the two ‘allowed misses.’ Please plan on this.If you miss quizzes earlier in the semester because you don’t come toclass for no good reason and then are faced with a situation later in thesemester where you need to see the doctor, please do not request amedical exemption. You should marshal the quota of ‘allowed misses’carefully.The quizzes will be administered in class but it is impossible to predictexactly when during the lecture they will occur. If you come to class afterthe quiz for that day has been administered (or leave before it isadministered), you are not entitled to a make up or to have the quiz readministered for you.11
How is the final grade assigned?uEach homework, quiz and exam receives a raw numeric scoreuBest five quiz scores are retaineduuuWeighted combination of raw numeric scores produces total raw score(out of 100)The total raw score is normalized – i.e. each total raw score is dividedby the 95th percentile raw score in the class. Scores are NOT rounded.Recent semesters have seen the 95th percentile score be 95%vuGrade boundaries drawn to group similar normalized scores in samefinal gradevuThis means to calculate your normalized score you divide your raw score by .95Starting point for boundaries is: 93:A, 90:A-, 87:B , 83:B, 80:B-, 68:C, 65:C-, 63:D , 60:D, 55:D-If you “need” a particular grade for this course, the time to worry about12that is now!
Other Misc. ItemsuGrading disputes/reviewsvuDSP studentsvuIf you have an accommodation letter from DSP, please e-mail it to me as soon aspossible. Specific accommodations will be discussed in advance of the exams.CECS - CSvuWhen you homework is graded, please review it in a timely manner. If you wouldlike clarification or review of a graded item, you may do so in one of two ways: seethe TAs in office hours (preferred) or make an “instructors only” post on Piazza.Either way, you must make any requests within one week of the homework beingreturned.If you were a CECS student, and you are switching to pure CS, please let me 9/csci109/We use Piazza for a discussion board, please use it to ask for help with thehomework or other course related questionsThis lets all students see the responses more efficient than e-mail!13
What is a Computer?ì14
Computer or Not?15
Standard Definitions (dictionary.com)uuAn electronic device designed to accept data, perform prescribed mathematicaland logical operations at high speed, and display the results of these operationsA programmable machine that performs high-speed processing of numbers, as wellas of text, graphics, symbols, and soundvuAll computers contain a central processing unit that interprets and executes instructions;input devices, such as a keyboard and a mouse, through which data and commands enterthe computer; memory that enables the computer to store programs and data; and outputdevices, such as printers and display screens, that show the results after the computer hasprocessed dataAn electronic device that stores and manipulates informationvUnlike a calculator, it is able to store a program and retrieve information from its memoryuA machine that can be programmed to manipulate symbolsuA person who computes; computist.v1640s: “one who calculates”An information transformer16
Types of InformationuBits: 0/1, T/F, True/False, Yes/NovuAnd strings of bits, such as 010110Numbers: 5, 101, -3, 3.14159, i, πvAnd numeric expressions, such as (3 2)uStatements in logic: "x At(x,USC) Ù Person(x) Þ Smart(x)Letters, words, sentences, paragraphs, articles, booksAudio, image and video filesURLs (such as http://www/google.com) and web pagesData basesu uuuu17
BinaryuModern computers use binary arithmeticuExamples:vvv2410 16 8 24 23 1 * 24 1 * 23 0 * 22 0 * 21 0 * 20 1100029010 64 16 8 2 1 * 26 0 * 25 1 * 24 1 * 23 0 * 22 1 * 21 0 * 20 10110102101112 1 * 24 0 * 23 1 * 22 1 * 21 1 * 20 16 4 2 1 231018
Information TransformationuConvert one body of information to anothervuThat is, computeExample: Boolean algebravvInformation expressed in bits: 0/1 (or F/T)Operations transform input bits to yield output bitsuAND, OR, NOT, AND01OR01000001101111AND(0, 1) è 0OR(0, 1) è 1AND(1, 1) è 1OR(0, 0) è 0NOT01XOR011000111019
Information TransformationAND01OR01000001101111NOT0110What is the truth table for f(x,y) AND(OR(x, y), NOT(AND(x, y)))?xyOR(x, y)AND(x, y)NOT(AND(x, y))AND(OR(x, y), NOT(AND(x, y)))000010011011101011111100f0100111020
CS Topic: representing numbers withbinaryuuuuHere is our first “real” CS topic!Get comfortable with looking at binary numbers!No hard (easier?) than base 10Why binary?vvuuWe use electronic computers (99.99999999% of us anyway)Circuits can be on or off: two states - binary representationBoolean operations and algebra is one way of computingwith binary numbersFirst homework (and quiz) has you look at binary logic andtransforming numbers base 10 - base 221
More on Information TransformationuOther examplesvvvvvvvMathematical calculations – (10 2)/2 6 – and logical proofsSolving puzzlesSorting lists: 4, 2, 1, 3, 6, 5Computational thinkingTransforming data into insights (big data or analytics)Transforming knowledge into decisions about what actions to performLiterary, musical and artistic compositionuHardware enables implementing transformationsuSoftware (programs) control(s) transformationsuAlgorithms are abstract descriptions of transformations22
Computational Thinkingu“thought processes involved in formulating problems and theirsolutions so that the solutions are represented in a form that can beeffectively carried out by an information-processing agent” (Cuny, Snyder,Wing)vway of solving problems, designing systems, and understanding humanbehavior that draws on concepts fundamental to computer scienceuvvvTo flourish in today's world, computational thinking has to be a fundamental partof the way people think and understand the worldcreating and making use of different levels of abstraction, to understand andsolve problems more effectivelythinking algorithmically and with the ability to apply mathematical conceptssuch as induction to develop more efficient, fair, and secure solutionsunderstanding the consequences of scale, not only for reasons of efficiencybut also for economic and social reasonsHumans thinking (i.e., transforming information) to devise proceduresfor execution by information transformers (human and/or machine)23
Computer or Not?24
ImplicationsuDefining computers in terms of their functionality vStrips away ancillary attributes previously thought essentialuvuMachine, electronic, speed, explicit programmability, Enables appreciating the full scope of computers and computingFacilitates recognition of “natural” computersvvvvBrain: Thought is preeminently information transformationEmbryonic development: Based on instructions written in DNAEvolution: Combines and modifies information in DNAImmune system: Includes pattern recognizers, memory, David Baltimore: “How biology became an information science”Richard Dawkins: “The difference between life and non-life is amatter not of substance but of information”25
Computer HistoryìLooms, the discrete machine abstraction, and the first computer programs26
A History of Human-Built ComputersAlthough computers can (and have been) built using allkinds of hardware, modern computing really took offwith the invention of electronic computers which werepreceded by mechanical computersu A history of computing and the Jacquard Loomu Mechanical ComputersuvvuThe Difference and Analytical EnginesThe Hollerith MachineElectronic ComputersvReading:St. Amant: Introduction,Ch. 1 and Ch. 2From EDSAC to the Macbook27
Before Mechanical ComputersElectronic computers were preceded bymechanical computers and mechanical computerswere preceded by looms28
A Simple Mechanical LoomuPressing treadles causes harnesses to lift threadsuThe shuttle slides a cross thread under the lifted threadsuThen the threads are lowereduPressing treadles causes harnesses to lift threadsuThe shuttle slides a cross thread under the lifted threadsuThen the threads are lowereduPressing treadles causes harnesses to lift threadsuThe shuttle slides a cross thread under the lifted threadsuThen the threads are loweredu uWhat kind of patterns does this produce?29
Discrete Machines: StateuuuuHow does the loom behave as a function of time?At any given time a set of threads is raised and the restare loweredWriting down the sequence of raised (and lowered)threads tells us the steps the machine went through toproduce the cloth/tapestry/whateverThe pattern of raised (and lowered) threads is called thestate of the machine30
CS Topic: StateuState is a very common CS conceptuHere we have the state of a physical machineuIn CS we talk about the “state” of an objectvvvvvuOf a databaseOf a robotOf a “state-machine” (finite, Turing, etc )Of a system (physical or virtual) Then we need a way to describe the statevGives us the notion of an encoding31
CS Topic: Discrete Machines, State andEncodinguChoosing a state representation takes skill. The stateshould bevvParsimonious: it should be a “small” descriptor of what the machine isdoing at any given timeAdequate: it should be “big enough” to capture everything “interesting”about the machineThese are sometimes contradictory. They are alsoqualitative and depend on what behavior of themachine we want to describeu Usually you need a vocabulary (encoding) to describestate. In the case of a loom, state can be expressed as abinary pattern (1 for raised, 0 for lowered)u32
Discrete Machines: AbstractionuThe loom is a discrete machinevvuMore precisely, the loom can be usefully modeled as adiscrete machinevvuState is binary pattern – i.e. discreteThe notion of time is discrete – i.e. time is modeled as proceeding in steps orfinite chunksBecause of course being a physical device there is variation, nothing isexactly preciseBut modeling the machine as discreet is good enough and works for thispurposeThis is an example of an abstraction – a key concept inComputer Science33
CS topic: AbstractionuuOne of the fundamental “things” we do in CSReducing or distilling a problem or concept to the essentialqualitiesvuuSimple set of characteristics that are most relevant to the problemMany (most, all) of what we do in engineering and computerscience involves abstractionsHere the abstraction is modelling the loom as a simplediscreet state machinevvMakes it possible to understandAnd makes it possible to “program” the loom34
Weaving Complex PatternsuHow to produce more complex patterns?uEarly solution was human – the draw loomvMaster weaver calls out which threads to liftDrawboy lifts threadsMaster weaver threads the shuttleMaster weaver calls out which threads to liftDrawboy lifts threadsMaster weaver threads the shuttleMaster weaver calls out which threads to liftDrawboy lifts threadsMaster weaver threads the shuttlev vvvvvvvv35
The Jacquard Loom (1801): MechanismuMechanism:vvvvuThreads attached to spring-loaded rodsSprings make all threads want to liftunless stopped somehowA metal ‘card’ with holes is insertedinto the path of the threadsA hole in the corresponding placeallows a thread to lift. No hole arreststhe thread motion and stops it fromliftingThe Jacquard Loom (from theTeaching Palette via YouTube)36
The Jacquard Loom: ProgramminguWeaving becomes the process ofvvCreating cards with holes in them (punchedcards)Sequencing the cards in the right orderEach card is an instruction to the machineto do precisely one thing (i.e., put itselfinto one particular state)u A sequence of cards (i.e., a sequence ofinstructions) causes the machine to stepthrough a sequence of states. The cardsequence is a programu The weaver as a programmeruJoseph Marie Jacquard(as woven by his loomvia a program of 24,000instructions). Imagecourtesy of Wikipedia.37
The Jacquard Loom: ProgramminguuuuuA discrete, ‘automatic’ machineSince we have chosen a binary encoding the machine stateis a binary numberEach instruction is also a binary number since eachinstruction is (literally) the state the programmer wants themachine to be in when that instruction is executedThe program for the machine is a sequence of instructions.Each program is (literally) a sequence of states theprogrammer wants the machine to step throughThe program is thus a sequence of binary numbers38
A Loom 000000This machine’s state iscaptured in a 9-bitwordu Each instruction in theprogram is also a 9-bitwordu The state and eachinstruction is thus 9bits wideu This program is 9instructions longu39
Loom Program LimitationsuDoes not scale:vvvuNo decision making on the fly:vuLarge instructions: To program a ‘big’ machine you need ‘big’words (large state implies large instruction widths)No counting: No repeats or loops to do things over a certainnumber of times (No “do.while” or “repeat.until”)No modularity: No logical chunks for sub-patterns that can bereused without replication (No “functions, methods,subroutines ”)No branching to decide to do one thing instead of anotherbased on a condition (No “if-then-else”. No jumps or “goto”)So is the Jacquard loom a computer?40
How Big/Fast is a Modern Computer?uuTypical Macbook Pro laptop has 1 billion transistorsThe state of the machine is a binary number with 1billion bits (a binary word of width 1 billion)vuNot possible to program a Macbook Pro by writing a sequenceof instructions each 1 Billion bits wideA Macbook Pro executes 5 billion instructions persecondvPossible to have programs that are billions of instructions longand yet have them finish operating in a reasonable time41
Modern Computers?uuuuIf modern computers are so big, how do we program them?We model (abstract) the computer as something moresimpleProgram to that modelThen let the hardware and OS sort out the differencebetween reality and our abstractionuThis method of problem solving is very, very common in CSuMore later in semester42
Computer HistoryìMechanical computers: The difference and analytical engines, the Hollerith machine43
The Difference Engine (1822)Video fromYouTube.uCharles BabbageuMechanical calculator to compute mathematical tablesvvuuuLoom: program transforms threads to patterns on clothDifference engine: program transforms numbers into other numbersPolynomial function computation using differencesOutput was via a ‘printer’ – a device that producedprinter’s plates so they could be stamped onto paperNo branching or looping, limited in what it couldcompute44
The Analytical Engine (1837)Video fromYouTube.uCharles BabbageuWorld’s first general purpose mechanical calculatorvvvvuuMemoryArithmetic unitBranchingLoopingProgrammed by punched cards like a loomOutput was via a ‘printer’ – a device that producedprinter’s plates so they could be stamped onto paper45
The Hollerith Tabulator (1890)uuuuHermann HollerithFirst device to read data into a machine: anelectromechanical system based on punched cardsBuilt to tabulate the results of US censusHollerith's contributions to modern computing are."incalculable”vuHe did not stop at his original 1890 tabulating machine and sorter, butproduced many other innovative new models. He also invented the firstautomatic card-feed mechanism, the first key punch, and took what wasperhaps the first step towards programming by introducing a wiringpanel in his 1906 Type I Tabulator, allowing it to do different jobs withouthaving to be rebuilt! (The 1890 Tabulator was hardwired to operate onlyon 1890 Census cards.) These inventions were the foundation of themodern information processing industry.Hollerith went on to form the Tabulating Machine Company.Merged with others to form the Computing TabulatingRecording Company (CTR). Renamed in 1924 toInternational Business Machines (IBM)Hermann Hollerithand one of hispunched cards.Images courtesy ofWikipedia.46
The ENIAC (1943-46)uuuuElectronic Numerical IntegratorAnd ComputerEckert and Mauchly (University ofPennsylvania)First electronic, general purposecomputer. Turing-complete,digital, reprogrammable(cumbersome)Vacuum tube and diode-based47
The EDVAC (1944-49)uuuElectronic Discrete Variable AutomaticComputer (Eckert and Mauchly)First stored program computer, binary(ENIAC was decimal). Operational 1951.Popularized by von Neumann (FirstDraft of a Report on the EDVAC) – firstreport on a modern computerarchitecture48
Computer History SummaryAlthough computers can (and have been) built using allkinds of hardware, modern computing really took offwith the invention of electronic computers which werepreceded by mechanical computersu A history of computing and the Jacquard Loomu Mechanical ComputersuvvuThe Difference and Analytical EnginesThe Hollerith MachineElectronic ComputersvFrom EDSAC to the Macbook49
Fundamental ConceptsuState and discrete machinesuAbstraction and modelsuEncoding data and instructionsuProgramminguTo be general, programs need to access amemory, and to be able to control the order ofthe instructions to execute based on the resultsof computation50
Review of termsuuuuuState: The condition of a system at a point intimeEncoding: Symbolic expression used to representinformationDiscrete: Proceeding in finite steps, individuallyseparate and distinctBinary: Numerical notation that uses base 2Abstraction: Simplified (“higher-level”)description51
Next time: Computer ArchitectureìHow are computers built?52
Introduction to Computer Science CSCI 109 Andrew Goodney Fall 2019 Lecture 1: Introduction August 26, 2019 China –Tianhe-2. Purpose of this Course uIntroduce computer science as a discipline, a body of knowledge, and a domain
This handbook supplement applies to students entering the fourth year of their degree in Computer Science, Mathematics & Computer Science or Computer Science . Undergraduate Course Handbook 1.2 Mathematics & Computer Science The Department of Computer Science offers the following joint degrees with the Department of Mathematics: BA .
Introduction to Computer Science I Course Overview Computer Science 111 Boston University Welcome to CS 111! Computer science is not so much the science of computers as it is the science of solving pro
Trends in the State of Computer Science in U.S. K-12 Schools 2016 Table of Contents Executive Summary 3 Introduction 5 Value of Computer Science in Schools 6 Opportunities to Learn Computer Science 9 Perceptions of Computer Science 14 Challenges and Opportunities for Computer Science in K-12
work/products (Beading, Candles, Carving, Food Products, Soap, Weaving, etc.) ⃝I understand that if my work contains Indigenous visual representation that it is a reflection of the Indigenous culture of my native region. ⃝To the best of my knowledge, my work/products fall within Craft Council standards and expectations with respect to
Computer Science Teachers Association, Cyber Innovation Center, and National Math and Science Initiative have answered the call by organizing states, districts, and the computer science education community to develop conceptual guidelines for computer science education. The K-12 Computer Science Framework was developed for -12 Computer Science
Intensive Introduction to Computer Science Course Overview Programming in Scratch Computer Science S-111 Harvard University David G. Sullivan, Ph.D. Unit 1, Part I Welcome to CS S-111! Computer science is not so much the science of computers as it is the
Introduction to Science Section 2 The Branches of Science, continued The branches of science work together. -biological science: the science of living things botany, ecology -physical science: the science of matter and energy chemistry: the science of matter and its changes physics: the science of forces and energy -earth science: the science of the Earth, the
Computer Science as a discipline 8.1 The role and sub-disciplines of computer science 8.2 Artificial intelligence, data science and computer science 8.3 Ethical aspects of computer science 8.4 The ACM Code of
