INFO 102 Lecture Notes for Exam 1 and quiz answers PDF

Preview

Summary

Quiz answers
Lecture notes for exam 1
INFO 102
Professor Ryan Cunningham...

Description

Monday January 25, 2021 ●

●

●

Primitive computation ○ 1642 pascal built pascals calculator ○ 1694 Leibniz built “stepped reckoner” ■ Still not doing computation ○ 1791-1871 charles babbage ■ 1822 designed difference engine ● Several versions built and used ■ 1837 designed analytic engine - first general purpose computer ■ Ada lovelace worked with babbage and was considered the first programmer ○ 1804 jacquard built jacquard loom ○ 1880s hollerith built hollerith machine ○ 1912-1952 alan turing ■ 1936 published theoretical model of computation and many fundamental results ■ 1940s worked as a cryptanalyst for british government, breaking german enigma code ■ 1950s published famous works on ai games and developmental biology ○ 1941 z3 built ○ 1943 colossus built ○ 1945 eniac built at the university of pennsylvania ○ 1949 edvac ○ 1951 univac ○ 1952 iliac To have a computer we need: ○ Ways to represent and store data ○ Ways to perform calculations on our data (computation) ○ Program the calculations (tell the computer to make decisions) ○ Turing complete - can do any type of calculation that we’ve ever known how to do People to remember ○ Alan turing ○ Babbage ○ Ada lovelace ○ Grace hopper ■ 1906-1992 ■ Enlisted in the navy ■ Worked on UNIVAC development team ■ 1954 invented first compiler based programming language ○ 1955 transistor computers built ○ 1958 jack kilby builds first integrated circuit ○ 1970’s first microprocessors built ○ 1965 moore's law

○ ○ ○ ○ ○

■ transistor count doubled every two years 1969 arpanet deployed 1972 pong released 1976 first ethernet network deployed 1980s personal computers hit market 1980s packman introduced, 1982 first laptop hit the market, 1982 TCP/IP protocol standardized, 1984 apple macintosh hit market, 1985 super mario bros, 1990 tim berners-lee published http/html, 1992 windows 3.1 hit market, 1993 mosaic web browser released, 1993 doom released, 1994 web search engines popularized, 1998 google search went public, 2000 dot com bubble burst, 2001 wikipedia established, 2002 web 2.0, 2004 world of warcraft released, 20017 apple iphone hits market, 2011 minecraft released, 2014 amazon echo released, 2015 apple watch released, 2016 overwatch released,

Wednesday January 27, 2021 ●

●

Data ○ ○ ○

Information stored in a computer is called data Data is represented in binary (a series of 0’s and 1’s) Each 0 or 1 is called a bit - the most basic unit of information ■ Bits are stored in groups of 8 are called bytes ■ Group of 4 bits is called a nibble ○ Data is stored in memory (RAM) Encoding ○ Representing information ■ 010010000100101010011000100110001001111 ■ ^What does this data represent? - unless we specify the encoding, we can’t know ○ Symbol - a unit for communicating information (character) ■ Ex. Q ○ Alphabet - a finite set of symbols used together to encode data ■ Ex. Σ = {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z} ○ Encoding information ■ We typically write numbers in decimal using the alphabet ● Σ = {0 1 2 3 4 5 6 7 8 9} ● 0 signifies the number zero, 1 signifies one, 10 signifies ten ■ Computers use a binary alphabet ● Σ = {0,1} ○ 0 signifies zero, 1 signifies one ○ 10 signifies the number two ○ 11 signifies the number three ● Everything is represented in binary; numbers, letters, textbooks, photos, videos, websites, programs… ■ Why binary?

●

○

○

○

○

○

Binary is great for engineering simple and robust electrical systems. A switch is either off (0) or on (1)(ex. High voltage or low voltage) ● Binary also has nice properties for logic (ex. 0=false, 1=true) because decisions are binary Natural numbers ■ 0 and all the numbers you get counting up ■ {0,1,2,3,4,5....} ■ No fractions. No decimals. No negative numbers. No imaginary numbers Encoding in decimal ■ In decimal, we have 10 symbols we use to write numbers ■ We count up through the symbols until we reach the biggest 0 1 2 3 4 5 6 7 8 9… ■ Whenever we run out of symbols, we add one to the column to the life and start over in the current column ...10 11 12 13… ■ This works no matter how big the number gets ...7999997 7999998 7999999 8000000… Positional notation

■ Ex. 5127 ■ 5(1000)+1(100)+2(10)+1(7) ■ 5*10^3 + 1*10^2 + 2*10^1 + 7*10^0 =5127 Counting in binary ■ In binary we have 2 symbols we use to write numbers ■ We count up through the symbols until we reach the biggest 01… ■ Whenever we run out of symbols, we add one to the column to the life and start over in the current column … 10 11 100 101 110 111 1000… ■ This works no matter how big the number gets ■ … 1111111110 1111111111 …. Positional notation ■ 1101

1(1)+0(2)+1(4)+1(8) 1*2^3+1*2^2+0*2^1+1*2^0= 13 ○

Converting binary to decimal ■ Use positional notation and af it up ■ Bit farthest to the right is 2^0 place, next is 2^1, next is 2^2 ■ For each bit in number (right to left): add bit*2^i (i being the current position) ■ Ex. convert 10011 in decimal 1*2^4 + 0*2^3 + 1*2^1 + 1*2^0 1*16 + 0*8 + 0*4 + 1*2 + 1*1 16 + 0 + 0 + 2 + 1 = 19

USEFUL POWERS TO REMEMBER

○

●

Converting decimal to binary ■ Take the number and divide it by 2 (the base). The remainder is the first digit. ■ Divide again. The remainder is the digit to the left. ■ Divide again. Remainder is next digit to the left ■ Keep going until nothing is left ● Ex. what is 29 in binary? 29/2 = 14 remainder 1 14/2 = 7 remainder 0 7/2 = 3 remainder 1 3/2 = 1 remainder 1 1/2 = 0 remainder 1 ● In binary, it is written 11101 (go from the bottom to the top of the remainders) Hexadecimal encoding ○ Counting in hexadecimal ■ Representing numbers in base 16 ■ In hexadecimal, we have 16 symbols we use to write numbers

■

■

0 1 2 3 4 5 6 7 8 9 A B C D E F… Whenever we run out of symbols, we add one to the column to the left and start over in the current column … 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20... This works nom after how big the number gets … AFFFD AFFFE AFFFF…

Friday January 29, 2021 ●

●

●

10101 in decimal ○ 1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 ○ 21 Encoding ○ Symbol - a unit for communicating information (character) ■ Ex. Q ○ Alphabet - a finite set of symbols used together to encode data ■ Ex. Σ = {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z} Converting hexadecimal to decimal ○ Use positional notation and add it up ○ Bit farthest to the right is 16^0 place, next is 16^1, next is 16^2... ○ For each digit in number (right to left): Add digit*16^i (where i is the current position)

○

●

Ex. 0xCD in decimal ■ C*16^1 + D*16^0 ■ 12*16 + 13*1 ■ 192 + 13 = 205 Converting decimal to hexadecimal ○ Divide by 16 (the base). the remainder is the first digit ○ Divide again. The remainder is the next digit to the left ○ Divide again. Remainder is next digit to the left ○ Keep going till nothing is left ○ While you have something remaining: Divide result by 16 Add remainder to the left of output ○ Ex. what is 359 in hexadecimal ■ 359/16 = 22 remainder 7 ■ 22/16 = 1 remainder 6 ■ 1/16 = 0 remainder 1

■ 167 Ex. what is 1526 in hexadecimal ■ 1526/16 = 95 remainder 6 ■ 95/16 = 5 remainder 15 ■ 5/16 = 0 remainder 5 ■ 5F6 Binary to hex or hex to binary ○ Each hex digit corresponds to 4 bits ○

●

●

●

●

●

○ Why hex ○ Groups of 4 bits = 1 hex digit (2 hex = 1 byte) ○ 1100101011111110 is hard to read ○ 1100 1010 1111 1110 = 0xCAFE is much easier to read ○ Ex. what is 0xC952 in binary? ■ 1100 1001 0101 0010 ○ Ex. what is binary 11001 0010 1011 in hex? ■ D2B ○ Ex. what is binary 1100 1010 1111 1110 in hex? ■ CAFE ○ Ex. what is binary 10110101101 in hex? ■ B5D ○ Ex. what is binary 0101 1010 1101 in hex? ■ 5AD Notation ○ 101 ← is this number in binary, decimal or hex? ○ Best to signal the encoding in some way ○ We do this with a prefix ■ Binary: 0b101 ■ Decimal: 101 (no prefix) ■ Hex: 0x101 Bits and bytes: Grouping bits ○ 8 bits grouped together is called a byte ○ A byte can be represented by two hex digits (ex. 0x1F) ○ 4 bits grouped together is called a nibble ○ A nibble can be represented by one hex digit (ex. 0xC) Binary math ○ Binary addition ■ Like decimal addition, carry 2s instead of 10s

1011 +101 ------10000 11 + 5 = 16 Monday February 1, 2021 Data representation ●

Binary math ○ Binary addition ■ Like decimal addition, carry 2s instead of 10s (because in binary “1,0” is how the number 2 is represented) ■ Ex. 1011 + 101 11 + 5 = 16 = 10000 ■

●

●

Ex. 1011 + 1111 = 11010 15 + 11 = 26

Storage size ○ The size of a number in a computer is sometimes limited (ex. 64 bits) ○ The storage size is typically called a word ○ If the data gets too big to fit in a word, we have an overflow ○ Ex. what if the word size is 1 byte 1111 1111 in hexadecimal FF - the biggest number you can get in this word size ○ Ex. 1111 1111+ 11 --------------1 0000 0010 This requires 9 bits, but we are only allowed to do 8, this is called an overflow ○ Integer overflow ■ Arithmetic operation results in a value too large to store ■ Typically, high order “carry” bits are lost, resulting in a “wrap around” Binary subtraction ○ Like decimal subtraction, borrow 2’s instead of 10’s ○ Ex. 1011 - 101 ------110 ○ Ex. what if the word size is 1 byte

■ 0-1 = overflow Integer overflow ■ We don’t know how to represent negative numbers! ■ Subtraction can also result in a “wrap around” Binary multiplication ○ Like decimal multiplication, borrow 2’s instead of 10’s ○ Ex. 1011 x 101 ------1011 00000 +101100 --------110111 Binary division ○ Like decimal division, borrow 2’s instead of 10’s ○ Ex. 01011 ----------10 | 10110 10 ----011 10 ----10 ○

●

●

●

●

Modulo operators ○ Extremely important operation! ○ Remainder after division (in decimal) ○ Ex. 5 mod 3 = 2 ○ Ex. what is 10 mod 3 = 1 (10/3 = 3 leftover is 1) ○ When a number is mod 2 ■ If the remainder is 0: it is even ● An even number is when you divide by 2 has no remainder ● Any number that when you take the modulo yields mod 0 ■ If the remainder is 1: it is odd Boolean operators ○ A simple algebra on true and false with few operators ○ Simplest operator is NOT (written as ‘) ■ Ex. if you want to say something is not true - you write it as false ■ If something is not false, it is true ○ A unary operator (takes only one input) ○ 1’=0 (“not true” means “false”) ○ 0’=1 (“not false” means “true”)

●

●

●

AND operators ○ A binary operator (takes 2 inputs) ○ Written as a dot · ○ Output is 1 only when both inputs are 1 ○ 1 · 0 = 0 (true AND false is false) OR operation ○ A binary operator (takes 2 inputs) ○ Written as a plus + ○ Outpost it 1 only when EITHER input is 1 ○ 1 + 0 = 1 (true OR false is true) XOR operation ○ A binary operator (takes two inputs) ○ Written as a circle plus ⊕ ○ Output is 1 when EXACTLY one input is 1 ○ 1⊕0=1

Wednesday February 3, 2021 ●

Truth table for AND, OR, and XOR

●

Boolean Expression ○ We can write expression using Boolean algebra ○ (0 ⊕ 1) + (1 · 1)’ = 1 + 0 = 1 Try It ○ What is ((0 · 1)’ + (0 ⊕ 1)) ⊕ (0 + 1)?

●

= (0’ + 1) ⊕ 1 = (1 + 1) ⊕ 1 =1⊕1 =0

●

Truth table ○ Columns for each unknown input and output ○ Represent possible input as rows

●

Logical operations on bits and bytes ○ AND: 1 if both inputs are 1 ○ OR: 1 if either input is 1 ○ XOR: 1 if exactly 1 input is 1 ○ NOT: 1 if input bit is 0

AND

0101 = 5 1100 = 12 ----------0100 = 4

XOR

0101 = 5 1100 = 12 ----------1001 = 9

●

Logical Operations ○ AND: 1011 AND 0101 = 0001 ○ OR: 1011 OR 0101 = 1111 ○ XOR: 1011 XOR 0101 = 1110 ○ NOT: NOT 1011 = 0100

●

Shift/Rotate ○ Shift numbers to the left or right (fill in with 0’s) ■ 1 shifted 2 to the left is 100 ○ Rotate numbers (fill in with what falls off the end) ■ 101 shifted 2 to the left is 110 ○ Can shift binary numbers to the right or left ■ 0000 0101 SHL 10 = 0001 0100 ■ 0000 0101 SHR 10 = 0000 0001 ○ Can rotate binary numbers to the right or left ■ 0101 0011 ROL 11 = 1001 1010 ■ 0101 0011 ROR 11 = 0110 1010

Representing Integers ●

Natural numbers ○ 0 and all the numbers you get counting up ○ {0,1,2,3,4,5…} ○ No fractions. No decimals. No negative numbers. No imaginary numbers.

●

Integers ○ The natural numbers and all the negative numbers ○ {...-5,-4,-3,-2,-1,0,1,2,3,4,5…} ○ No fractions. No decimals. No imaginary numbers.

●

Two’s complement ○ A clever trick to represent negative numbers ○ To represent a negative number: ■ Find its positive binary representation ■ Flip all of the bits (all 0s and 1s and vice versa) ■ Add 1 ○ Note: requires that we know storage size Disadvantage: losing a bit to take care of the size

●

●

Rationals ○ Just a ratio of two integers ○ Examples: 3/13, 5/4, -18/17 ○ No decimals. No imaginary numbers. ○ No special representation needed: just two binary numbers ○ Operations are trouble, so we don’t really use this encoding

●

Reals ○ All the rational numbers and irrational numbers ○ Irrational numbers: pi ○ Can’t truly represent irrational numbers digitally!

●

Floating Point Numbers

Friday February 5, 2021 ●

●

Examples ○ What is -7 in 6-bit 2’s complement? ■ First find the binary representation of the positive number (find 7 in normal binary) → 7 is 000 111 ■ Next flip the zeroes and the ones ■ Last step is to add one ■ 111001 ○ What is 11 in 6-bit 2’s complement? ■ First, 11 is represented as 1011 in binary ■ You need to stick 2 zeroes in front In 2’s complement: ○ If it is a positive number, you don’t have to flip the bits and we don’t have to add 1 ○ Pos numbers represented normal way but have to fit in the bits

●

●

● ●

●

○ Negative number we have to flip all the bits and add one Rationals ○ Just a ratio of two integers ○ Examples: 3/13, 4/4, -18/17 ○ No decimals. No imaginary numbers. ○ No special representation needed: just 2 binary numbers ○ Operations are trouble, so we don’t really use this encoding Reals ○ All the rational AND irrational numbers ○ Irrational: pi = 3.14159265359 ○ Can’t truly represent irrational numbers digitally Floating point numbers ○ Can move the decimal point around to represent the numbers we need to Representing decimal real numbers ○ Scientific notation - a form of floating point representation in which the decimal point is kept to the right of the leftmost digit ■ Ex. 12001.32708 is 1.200132708 x 10^4 ● (bc you moved the decimal place 4 spots to left, so that is why is is to the fourth power) ■ Ex. 123.332 in scientific notation ● 1.23332 x 10^2 ■ Ex. 0.0034 in scientific notation ● Move decimal point so that the number is the farthest to the right is right before the decimal ● 3.4 x 10^-3 Floating point binary numbers ○ A real value in base 2 can be defined by the following formula where the mantissa is an integer

■ ■

●

Exponent tells you how to move the decimal point What if we only had space to write 8 bits? ● Part has to be given to the mantissa ○ The more digits we give to the mantissa, the more accurate and precise we will be ○ The mantissa is based on how many bits we allocate. How much storage space we have to represent the number ● Part has to be given to the exponent ○ The more bits we give to the exponent, it lets you represent larger or smaller numbers ○ Mantissa is the bottom point of the number, the not exponent part of scientific notation Storing floating point numbers

● ●

●

■ 32 bits (8+23+1=32) ■ In this example, they call the mantissa the “fraction” ○ IEEE 754 is the standard way to encode floating point numbers ○ Won’t be asked to understand this format in detail Ex. what is (0b) 1111.11 in decimal ○ 15.75 = 15+½ +¼ = 15+.5+.25 Ex. What is the 4-bit binary mantissa of 56? ○ 56 decimal = 111000 (32+16+8) ○ 56 is 111000 in binary. If 1110 is the mantissa, what is the exponent? Representing text ○ Text has a variable length- cannot be represented in a fixed word ○ ASCII - 8 bytes to represent each character ○ Unicode - complex, but we are going to focus on ascii ○ Ex. encode HELLO in ASCII ■ H 0x48 ■ E 0x45 ■ L 0x4C ■ O 0x4F ■ 0x48454C4C4F

Homework 1: 2/7/21 1. Match the historical figure to their description ○ Published a paper about implementing symbolic logic using relays ■ Shannon ○ A consultant on the first general purpose computers ENIAC and EDVAC ■ Von Neumann ○ Designed the first mechanical machine that included memory ■ Babbage ○ Considered to be the first programmer ■ Ada Lovelace ○ Developed the concept of punched holes used to weave cloth ■ Jacquard ○ Invented an abstract model of computation, founding theoretical computer science ■ Turing ○ Built the first mechanical machine that did addition, subtraction, multiplication, and division ■ Leibniz ○ French mathematician who built and sold the first gear driven mechanical machine that did addition and subtraction ■ Pascal ○ The first educational institution to own a general purpose computer, which was known as the ILLIAC ■ The University of Illinois ○ Proposed punch card systems used for counting the census ■ Hollerith 2. Moore's law says that "Computers will either __________ in power at the same price or __________ in cost for the same power every 18 months." ○ Double, halve 3. How many symbols are used in the binary number system? ○ 2 4. How many symbols are used in the hexadecimal number system? ○ 16 5. In the earliest electronic computers, programmers had to write machine language code expressed in _______________. ○ Binary 6. A group of eight bits is called a(n) _______________. ○ Byte 7. How many bytes are required to represent a 128-bit integer? ○ 16 8. How many different values can 4 bits represent? ○ 16 9. How many different values can 10 bits represent? ○ 1024

10. How many bits are in 32 bytes? ○ 256 11. How many different values can be stored in one byte? ○ 256 12. Convert 0xBADA55 to decimal. ○ 12245589 13. In which hardware generation were integrated circuits introduced? ○ Third 14. True or False? The personal computer was introduced in the fourth generation of computer hardware. ○ True 15. FORTRAN and COBOL are two of the earliest _______________ programming languages. ○ High level 16. What is the result of 0xFADE xor 0xFACE? Report your answer in decimal. ○ 16 17. What is 0xCAFE xor 0xBABE? Report your answer in decimal. ○ 28736 18. What is 0xDAD if you perform a binary shift 2 bits to the left? Report your answer in decimal. ○ 14004 ○ https://bit-calculator.com/bit-shift-calculator 19. What is 0xDAD if you perform a binary shift 4 bits to the left? Report your answer in hex! ○ DAD0 20. What is 0xD00D modulo 0b1101? Report your answer in decimal. ○ 0 21. Add up the ASCII values for all of the letters in the string "DISCO FEVER". Report your answer in decimal. HINT: Don't forget the space! ○ 778 ○ https://www.rapidtables.com/convert/number/ascii-hex-bin-dec-converter.html 22. What is the ASCII value of the string "BAD" xored with 0xBAD? Report your answer in decimal. ○ ?? - we got it wrong ○ Convert “BAD” to hex ○ https://www.rapidtables.com/convert/number/ascii-to-hex.html ○ ○ Xor the hex values, convert answer to decimal Monday February 8, 2021 ● Ex. you encounter this number in a computer 0xFFFFFFFF ○ How many bits is it? ■ 32 bits ○ How many bytes is it? ■ 4 bytes

○

What number is it? ■ You would find out by converting from hex to decimal ■ 15*1+15*16+15*16^2+15*16^3+15*16^4… ■ Actually, it’s -1. You do this by subtract one and flip the number to take it out o...