Notes PDF

Preview

Summary

EECS Intro to Computer ScienceSept 9th, 2020 History of Computers Abacus: first developed in Babylonia, over 5000 years ago  Algorithm: a finite set of unambiguous instruction to solve a problem – Muhammad Ibn  Early calculating machines were either manual or mechanical ex. slide rule, mechanical...

Description

EECS Intro to Computer Science Sept 9th, 2020 History of Computers    

 





Abacus: first developed in Babylonia, over 5000 years ago Algorithm: a finite set of unambiguous instruction to solve a problem – Muhammad Ibn Early calculating machines were either manual or mechanical ex. slide rule, mechanical calculators Jacquard Loom 1801  Used punch cards to define complex patters for textile  Later used them to code computer programs George Poole 1815-1864  Boolean algebra, laid logical foundations of digital computers Birth of the electronic computer 1930 – 1951  Claude Shannon 1916 – 2001  Introduced the application of Boolean logic in creating computing machines  1948 published “A mathematical theory of Computer” established principles for encoding info  Von Neumann Architecture  Stored Program, CPU, A memory, mass storage, I.O.  Basis for modern computers  Alan Turing 1912 – 1954  Led the WWII research group that broke the code for Enigma machine  Enigma machine invented in 1918, most sophisticated code system of it’s day ENIAC: Electronic Numerical Integrator And Computer is the first general-purpose electronic digital computer  Used vacuum tubes to control the flow of electronic signals  Decimal internal coding Age of the mainframes 1951 – 1970  Since 1950s, computers have gotten smaller overtime  Grace Murray Hopper 1906 - 1992  Created first compiler because she was tired of writing machine code by hand which greatly improved programing speed and efficiency  The transistor was the most important invention of the 20th century  It replaced vacuum tubes which were bulky and heated up easily  The integrated circuit was essentially a device that allowed several transistors to be placed on a small surface





 Today we can exceed 10 billion transistors in a package of 25cm2 1960s IBM system/360  Introduced in 1964  Going to the moon was achievable goal but Apollo space program depended on computers to calculate trajectories  Margaret Hamilton  Led the team who coded the programing for the guidance computer  Gordan Bell “minicomputer” Digital Equipment Corp.  PDP series offered mainframe performance at a fraction of the cost  Offered at 20,000 vs 1M to that of mainframe  Specialized the development of supercomputers first developed in the late 1970s Age of personal computers 1970 – present  Intel 4004 microprocessor 1972  Contained 2300 transistors and ran at 100 KHz  Beginning of Microsoft  1975 Bill gates and Paul Allen approached MITS and promised to deliver a basic compiler  Radio Shack TRS-80 1978  Successful, affordable, limited commercial software  Osborne I 1981  Advanced research projects agency network (ARPANET)  Basis of the internet today  Allowed for a local network which was used by universities to share data

September 14th, 2020 Intro to MS Excel 



Importance of spreadsheets  They allow for fast and effective work without having the need to do mental math or fully understand the mathematical concepts  Visualization and projections of patterns are easier to observe  Can help with large data sets  Cons include sub-optimal processing speed and errors that are difficult to spot Features of spreadsheets  Options to format and organize data  Ability to import data from foreign sources  Manipulate, process, transform generate or analyze data  Visualize the data using numbers, text, charts, or graphs

September 16th, 2020 Intro to MS Excel II    

The editing button on the top right corner can be used to create series =sum(A1:A7) will give sum of A1 through A7 Do not use input from the cell that is currently being used to manufacture a function as that will give a circular reference error Dollar sign between column and row variable (i.e. C$3) creates a constant

September 21st, 2020 Intro to MS Excel III   

 

Calculations can be made for entire columns Use lookup function to classify data The data registers only the lowest member of its class

Lookup value is the set of data being classified, lookup vector is the set of data that is sets the range and the result vector is the defined class

September 23rd, 2020 Analog vs Digital information 

2 main ways to log information o Analog data: continues representation, analogous to the actual information it represents  Thermometer is an example as it continually rises and falls in direct proportion to the temperature  Speedometer is another example  Has infinite precision o Digital data: discrete representation, using a finite number of digits to record data









  

        

Time is an example of digital data as it is not continuous, and data is limited  Does not have infinite precision Questionnaire scales o Ex. how much do u read on a scale of 1 – 10 (discrete) o Saying you read 12345 words every day is harder to analyze even though it might be a true value Computers are finite o Information is represented in an infinite range o They can only operate on a fixed amount of data at a time, the type of data must be known ahead of time o Represent enough of the range to meet our computational needs is a good way to present information from an infinite range Conversion of analog to digital data in 2 steps o 1. Sampling (discretization). Converts continuous variation to discrete snapshots  Digitization of video: 24-30 frames per second  Dividing a still picture into pixels (1920 X 1080)  Digitization of audio o 2. Quantization (truncation). Converts infinite range of values to a finite one  1/3 = 0.33333 (some finite number of digits)  Pie = 3.14159  RGB color range per pixel Digitizing analogous information results in loss of data There are several mechanisms put in place that determine proper parameters to digitize analogue data with as much precision as necessary Bit (binary digit info) unit symbol b o Holds one of two values: 0 or 1 o Uses Boolean logic Often combined in groups of eight to represent data o A group of 8 bits is called a byte, with a unit symbol B Kilobit = 2^10, Megabit 2^20, gigabit 2^30 Computers cannot work well with analog information Using binary represents only one of two states, benefits cost, and reliability Analog signals fluctuate in voltage up and down Digital signals have only a high (1) or low (0) state All signals when transmitted degrade as they move down a line Digital: if distortion is small enough the signal can completely regenerate and regain its original shape Analog: degradation of analog signals is permanent: there is no way to determine if distortion was not present originals



 

Both digital and analogue data can be recorded o Magnetic audio tapes, vinyl records, pencil drawings, VHS tapes, CDs, and Blu ray o Digital copies are always completely identical to the original o Error- detection and correction codes exist for digital data Most of the data we encounter has some redundancy Digital representation o Easier to process o Easier to transmit reliably o Digital signals can be completely regenerated o Easier storage and compression

Sept 23rd, 2020 Representing Numbers      

  

Natural numbers are whole positive numbers (do not include fractions) Negative numbers are whole numbers that are less than zero Both natural and negative numbers are classified as integers Rational numbers are integers that are quotient of other integers Complex and imaginary numbers are derived from the idea of square root of negative numbers Positional Notation o 10^4, 10^3, 10^2, 10^1, and 10^0 for a number in the 10,000s  Ex 27916 Non-decimal number systems Binary is base 2 and has 2-digit symbols 0 and 1 The individual digits of a number in each base b must be less than the base b o Base 5 = 0,1,2,3,4 o Hex 16 = 0,1,2,3,4,5,6,7,8,9, a, b, c, d, e, f  When running out of single digit possibilities use letters in alphabetical order

Sept 25th, 2020 Representing Numbers II



Sept 25th, 2020 Representing Numbers III  

N units Minimum number that can be represented is 0 while the maximum number is 2n -1

 

For fractional component multiply instead of dividing

September 29th,2020 Representing Numbers IV  In notebook  The left most bit represents sign (0 is positive and 1 is negative) o Ex. if a computer can represent integers  1011110 is a negative 011110  0011110 is a positive 011110

October 5th, 2020 Representing Numbers VI, Text I   

 





Scientific notation is used to represent real numbers Sign (negative, positive), mantissa (integer) x 10 (exponent) o This representation is called floating point The way in which floating point numbers are represented in computers is governed by the IEEE 754 standard o It uses 32bit, 64bit and 128bit representations

Character set is a list of characters and the codes used to represent each one o Experts in the computer industry agree on a specific character set thereby creating a standard for sharing data ASCII Character Set o American standard code for information exchange o Originally seven bits for each character, 128 unique characters  2^7 = 128 possible o 33 of them control characters, rest of them decimal digits o Later extended ASCII evolved so that all eight bits were used  Represent lines, symbols, and letters with accents  Several incompatible versions  2^8 = 256 possible characters



Unicode uses 16+ bits per character and can represent more than 1 million characters o the first 128 characters are the same as ASCII, but the rest are organized into blocks with a common theme

October 7th, 2020 Representing Text II        

 



There are still no ways to use multiple languages at the same time ASCII is a subset of Unicode Emoji is “picture character” o First appeared in Unicode v6.0, now more than 1085 in v9.0 Miscellaneous Symbols and Pictographs, range 1f300 – 1f5ff Emoticons, range 1f600 – 1fg4f Compression (lossless) – when some things are reductant o Data compression is reducing the amount of space needed to store data Compression ratio is the size of the compressed data divided by the size of the original data DC techniques can be lossy or lossless

Keyword encoding o Frequently used words are replaced by a single character o Characters used to encode cannot be part of the original text Run-length encoding

o Sequence of repeated characters is replaced by a flag character, followed by the repeated character followed by a single digit that indicates repetition o *A7 would decode to AAAAAAA

October 9th, 2020 Representing Text III 

  

Huffman encoding o Uses variable-length bit strings to represent each character o Prefix property- no code is a prefix of another code, enables unique decodability  Ex. If A is 01, and B is 1010 if B does not begin 01 it is not a prefix of A o Use few bits for common characters and reserve longer bits for characters that appear less often making the document size smaller  Idea comes from morse code which uses dots and dashes (0,1) Keyword is the least effective, Huffman is the most effective Applications o RLE is used when there is lots of white space, any data that changes slowly  Can be combined with Huffman o Huffman is used in a lot of algorithms as a building block  Is optimal for per character compression  Can do better if consider more symbols at a time during analysis Compressing can be better if we are willing to accept small loses Huffman’s Algorithm o Input: symbols and their frequency count o Output: binary code for each symbol o Property: optimum compression rate with prefix property Step 1: Sort them in ascending order of frequency, small – largest Step 2: Replace the two minimum frequency symbols by one combined symbol Step 3: Repeat step 1 and 2 until all characters are combined

 

Name right and left branch 1,0 (either or)

 

 

o Using this method, a unique code can be derived when working from root-node to leaf (can be done vise-versa) o The goal is to make a unique code, so it does not matter how you name the branches (one side must be 1 and other side must be 0) o This is a way to attain prefix property and manually create the Huffman code

October 19th, 2020 Word Processing      

Use MS word to make stuff like tables, headers etc. and avoid doing them manually Use (home) the styles bar to manipulate aspects of text such as heading 1 and 2, footnotes etc. Use insert>links to make hyperlinks Use insert > header and footer to add headers, footers, and page numbers. Use inset > tables to insert tables into MS Use references > captions to add captions to the document o > citations to insert citations o > table of contents  Can have word generate lists of equations, tables etc. o

October 21st, 2020 Digital Media I  

   

Representing audio, images, and video Microphone is a transducer, converting audio (sound waves) to electrical signals o Transducer is a device that converts energy to a different type of energy  Speaker converts electrical signals to sound waves Sampling the audio, makes it so that audio is assigned a value that corresponds to the amplitude of the analog wave Audio can also be made from scratch and that process is called synthesis Period is the amount of time it takes to reach from peak to peak o Period = 1/ f Period and frequency have an inverse relationship

October 23rd, 2020 Digital Media II 



Humans can hear between 16Hz – 22kHz o When we age 25+, we have trouble hearing frequencies greater than 15kHz o On a piano key on the left are lower freq. ranging from 16hz – 5khz Digitalizing sound involves taking samples (measurements) at a fixed rate (sampling rate) and recording them o 2fast  large file, 2slow  inaccurate

 

 

  

 



o Low sampling rate reproduces a sound (red) that does not match the original frequency (blue) Compression saves space and transmits data faster Sample interval needs to be less than or equal to half period to be able to catch peaks and valleys o Half period = 1/2f Each sample is recorded using a fixed number of bits, bit depth o Higher bit depth means more accurate sample A bit depth of 16 is the optimal value, where the data produced is not distinguishable than the data in the computer

Computers are finite; therefore, it is important to choose a length of bits when storing data Bit rate is bits per second o Higher bit rate is better quality which means larger file size

o Lose less audio compression o Similar to text compression techniques Lossy audio compression o Remove imperceptible sounds using psychoacoustics models o Reduce bit rate less accurate reproduction of the original Codecs o Compression and decompression algorithms for audio



 

  

 

Portmanteau word combination of coder and decoder or compressor and decompressor

Color is typically represented using RGB color model o 3 integers in the range 255 describe the amount of red, green and blue required to reproduce the color

More than 16M combinations but in real life there is an infinite amount 255 values = 1 byte = 2 nibbles = hexadecimal digits

Picture (pixel element) o Dots of color in an image



 

Resolution o Number of pixels in an image or on a display o Size of an image, measured in pixels o Can refer to pixel density, number of pixels per unit of distance (ppi) o Sampling is when only some of the dots are shown  Truncation- each of these pixels have infinite colors and con only mapped with limitations Ways to store graphics

o Instead of storing picture by picture we store the definition of space using mathematical equations o Quality isn’t affected that much



o Quality gets compromised

October 25th, 2020 Digital Media III

 o Similar to keyword encoding

 

JPEG (Joint Photographic Experts Group) o Ideal format for photos but bad for images with sharp lines

 Compression ratios of 1-10%, depending on quality o Lossy  Original image is divided into smaller blocks  Stores the difference between each pixel’s intensity and the average intensity of the block

  

   

Video is essentially audio and images

Progressive – all lines refresh at the same time Interlaced - odd lines refresh, then lines with even number refresh Spacial – frames are compressed individually one at a time

 



 



Tempral- keyframes are compressed independently, other frames are compressed based on key frames o Algorithms store the difference between keyframes and other frames Effect of Bitrate o If bit rate is low parts of the video is pixelated o Constant Bitrate – same throughout the video o Variable bitrate – can vary  Allows higher motion scenes to have higher bitrate and vice versa HuffYUV (Huffman, YUV color space) o Loseless, Huffman encoding, compression ratio is 47% MPEG-2 o Lossy, temporal and spacial compression, Huffman encoding, ratio around 3.3%  Highly dependent on bitrate H.264 o Lossy, temporal and spacial compression, frame prediction  Oredeicts next frame using spacial and temporal info, compares with the actual frame and only saves the difference o CR = 1.6% o Higher quality than MPEG-2 at same bitrate

 

October 30th, 2020 Logic Gates       

Gate – A device that performs a basic operation on electrical signals Circuits – gates combined to perform more complicated tasks Boolean expressions – a mathematical notation for expressing two valued logic Logic diagrams – a graphical representation of a circuit: each gate has its own symbol Truth tables – a table showing all possible input values and the associated output values Function notation – uses a function name followed by a list of arguments in place of the operands used in Boolean logic Two main roles of transistor: Amplifier, Binary switch

  

Gates are distinguished only by their shape 1 means true, 0 means false











x = a’

x = a.b

x = a+b

not of or = NOR, not of and = Nand

  



Distributive law can be used to make Boolean logic more efficient o X= A.B + A.C = A . (B + C) At digital level, addition is performed in binary o Addition operations are carried out by special circuits called appropriately adders  Half adder – a circuit that computes the sum of two bits and produces the correct carry bit  Full adder – a circuit that computes the sum of two bits and a carry bit and produces the correct carry bit



 

o Carry in is basically a 3rd Vector For a multi digit binary number, a half adder can be used with the rest being full adders They can also all be full adders if need so

November 3rd , 2020 Computer components  

Peripherals are utility that attaches to CPU. Motherboard – electrical circuit board that is joins everything







The von Neumann Architecture o Created a simplified computing model comprised of a CPU, memory, (secondary) storage, and input and output devices Memory vs storage

Short term memory used when doing something vs having a long-term memory while doing somethin...