Course Overview and Introduction to ComputationCOMS W1007Introduction to Computer ScienceChristopher Conway27 May 2003Contact InformationChristopher [email protected](212) 939-7069521 Computer Science BuildingOffice Hours: 3:30 - 5:00 Tuesday and ThursdayTA:Bogdan [email protected] Room (1st Floor Mudd)Office Hours: 3:00 - 4:30 Monday and Wednesdayhttp://www.columbia.edu/˜cs1007TextbooksRequired:Java Software Solutions: Foundations of Program Design,Third Edition.John Lewis and William Loftus.Addison Wesley, 2003.Available at Papyrus Books on Broadway at 114th.Recommended:The Java Programming Language, Third Edition.Ken Arnold, James Gosling and David Holmes.Addison Wesley, 2000.SoftwareEverything you need is on CUNIX. There are fancy JavaIDEs available, but we won’t do anything that requiresmore than a text editor and the Java SDK.If you want to work on your own computer:•Use Java version 1.3.1•Test all of your work on CUNIX.GradingHomework 40%Final 30%Midterm 20%Quiz 10%•There will be five homeworks. The first homework isdue next Tuesday.•Homeworks must be submitted by 6:00 AM on thedue date.Tests•Quiz: June 3 (next Tuesday), 15 minutes (beginning ofclass).•Midterm: June 13, 90 minutes (first half of class).•Final: July 3, 190 minutes (whole class), covers theentire semester.What is Computer Science?Computer science is the study of computation (i.e.,processing and manipulating data). It is an intersection ofmathematics, science and engineering.Primary concerns:1. Is a problem computable? (Algorithms)2. Is finding a solution to a problem feasible?(Complexity Theory)3. Is solving a problem practical? (Hardware/Software)What is a Computer?An algorithm is a set of rules for transforming an input intoan output.A computer is device that can execute algorithms. It takes:a) A set of rules (a program)b) Input data (e.g., keyboard input, mouse clicks, adatabase file)And produces:c) Output data (e.g., display output, a web page, aresult set)No, Really, What is a Computer?By “computer”, we typically mean a binary stored programdigital computer. (Von Neumann model)•“binary” - the data is stored as ones and zeroes.•“stored program” - the computer has memory, andboth the data and the program instructions are storedin that memory.•“digital” - operates on discrete quantities (i.e., onesand zeroes). Not continuous.•“computer” - it can execute algorithms.BinaryBinary is a base-2 number system. In general, a base-nnumber system encodes numbers as:(xixi−1. . . x1x0)n= x0n0+x1n1+···+xi−1ni−1+xiniThus:1010112= 1 · 20+ 1 · 21+ 0 · 22+ 1 · 23+ 0 · 24+ 1 · 25= 1 + 2 + 0 + 8 + 0 + 32= 43Computers like binary because 0/1 ⇔ off/on.Powers of TwoThe importance of binary means we have to get familiarwith the powers of 2.20= 26=21= 27=22= 28=23= 29=24= 210=25= 211=Bits and BytesWe call one binary digit (one or zero) a bit. 8 bits is a byte.n bits can represent 2ndifferent numbers.210bytes = 1 kilobyte220bytes = 1 megabyte230bytes = 1 gigabyte240bytes = 1 terabyteNotice that the exponent goes up by increments of tenbetween each order of magnitude. Thus there are 210kilobytes in a megabyte and 210megabytes in a gigabyte.HexadecimalAnother base that turns up in computer science isbase-16, or hexadecimal. Base-16 requires inventing afew new digits.Decimal Binary Hex0 0000 01 0001 12 0010 23 0011 34 0100 45 0101 56 0110 67 0111 7Decimal Binary Hex8 1000 89 1001 910 1010 A11 1011 B12 1100 C13 1101 D14 1110 E15 1111 FBinary and Hex16 is 24, so every hex digit can be converted to exactlyfour binary digits.C16= 11002716= 01112C716= 1100 01112Converting from binary to hex is just as easy:1101|{z}D0100|{z}41011|{z}B01102| {z }6= D4B616Converting from DecimalGoing to binary or hex from decimal is a little trickier. Ingeneral, the base-n representation (xixi−1. . . x1x0)nofa number X is:xj=—(X mod nj+1)njHere’s an algorithm:1. X0:= X2. Find the largest i such that ni≤ X.3. xi:= X0÷ ni, X0:= X0mod ni, i := i − 14. If i ≥ 0, return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Decimal to Binary: ExampleThat’s not as hard as it looks. Let’s convert 43 to binary.Step 1: X0:= 43Step 2: i := 5 (25= 32, 26= 64)Step 3: x5:= 43 ÷ 25= 43 ÷ 32 = 1X0:= 43 mod 32 = 11i := 5 − 1 = 4Step 4: 4 ≥ 0? Return to Step 3.Step 3: x4:= 11 ÷ 24= 11 ÷ 16 = 0X0:= 11 mod 16 = 11i := 4 − 1 = 3Step 4: 3 ≥ 0? Return to Step 3.Step 4: 3 ≥ 0? Return to Step 3.Step 3: x3:= 11 ÷ 23= 11 ÷ 8 = 1X0:= 11 mod 8 = 3i := 3 − 1 = 2Step 4: 2 ≥ 0? Return to Step 3.Step 3: x2:= 3 ÷ 22= 3 ÷ 4 = 0X0:= 3 mod 4 = 3i := 2 − 1 = 1Step 4: 1 ≥ 0? Return to Step 3.Step 4: 3 ≥ 0? Return to Step 3.Step 3: x3:= 11 ÷ 23= 11 ÷ 8 = 1X0:= 11 mod 8 = 3i := 3 − 1 = 2Step 4: 2 ≥ 0? Return to Step 3.Step