User:Aaronw1109/APCSP

Vocab Terminology

Technical Terminology

1. Computational Artifact - an object created by a human being that involves the use of computation in some way, for example a mobile app or web page.
2. Event-driven programming - a programming approach whereby the program's behavior is controlled by writing code that responded to various events that occur, such as Button clicks.
3. Hardware - the large and small physical components that make up a computers such as the computer's keyboard or its processor. It is what you can physically touch.
4. Software - the computer programs that make up a computer system such as the mobile apps we will be creating in this course. This set of instructions in the computer controls the hardware.
5. Abstraction - one of the seven big ideas of the CS Principles curriculum. An abstraction is a simplified and general representation of some complex object or process. One example would be a Google map.
6. Binary number- a number written in the binary system, a system that uses only two digits, 0s and 1s.

Vocab - 2

1. bit: short for binary digit, the smallest unit of unit of information on a machine
2. blacklist: in internet terminology, a generic term for a list of email addresses or IP addresses that are origination with known spammers
3. byte: a byte is 8 bits
4. character: any symbol that requires one byte of storage
5. cyberspace: a metaphor for describing the non-physical terrain created by computer systems
6. data: data is distinct information that is formatted in a special way. Data exists in a variety of forms, like text on paper or bytes stored in electronic memory
7. data center: physical or virtual infrastructures used by enterprises to house computer, server and networking systems and components for the company’s IT (information technology) needs
8. data network: a telecommunications network which allows computers to exchange data
9. disk drive: a randomly addressable and rewritable storage device
10. intellectual property: refers to any property that is created using original thought. Traditional intellectual property include patents, copyrights, and trademarks.
11. Moore's Law: The number of transistors per square inch on integrated circuits has doubled every year since the integrated circuit was invented.
12. network: a group of two or more computer systems linked together
13. processor: short for microprocessor or CPU
14. social network: a social structure made of nodes that are generally individuals or organizations. A social network represents relationships and flows between people, groups, organizations, animals, computers, or other information/knowledge processing entities
15. whitelist: a generic name for a list of email address or IP addresses that are considered to be spam free

Vocab - 3

1. algorithm: a formula or set of steps for solving a particular problem.
2. analog: a device or system that represents changing values as continuously variable physical quantities
3. ASCII: a code for representing English characters as numbers, with each letter assigned a number from 0 to 127
4. cloud computing: comparable to grid computing, cloud computing relies on sharing resources rather than having local servers handle applications.
5. cryptography: the art of protecting information by transforming it into an unreadable format, called ciphertext
6. digital: any system based on discontinuous data or events. Computers are digital machines because at the basic level they can distinguish between just two values, 0 and 1.
7. digital signal processing: (DSP) refers to manipulating analog information
8. download: to copy data (usually an entire file) from a main source to a peripheral device
9. lossless compression: data compression techniques in which no data is lost.
10. lossy compression: data compression techniques in which some amount of data is lost. This technique attempts to eliminate redundant information.
11. megabyte: used to describe data storage, 1,048,576 bytes (abbreviated MB)
12. megapixel: one million pixels, used in reference to the resolution of a graphics device
13. modeling: process of representing a real-world object of phenomenon as a set of mathematical equations.
14. OCR: optical character recognition, the branch of computer science that involves reading text from paper and translating the images into a form that the computer can manipulate
15. pixel: short for a picture element, a single point in a graphic image
16. raster: the rectangular area of a display screen actually being used to display images
17. refactoring: reducing the amount of code through the creation of procedures
18. render: refers to the process of adding realism to a computer graphics by adding 3-D qualities, such as shadows and variations in color and shade.
19. spam: spam is electronic junk mail or junk newsgroup postings
20. steganography: the art and science of hiding information by embedding messages within other, seemingly harmless messages
21. upload: to transmit data from a computer to a bulletin board service, mainframe, or network.

Vocab - 4

1. ad hoc: when used to describe programming, it means a quick fix for a problem, not usually #the best example that will sustain an issue.
2. cloud computing: comparable to grid computing, cloud computing relies on sharing resources rather than having local servers handle applications.
3. cookie: a small text file placed when you access a site and used by websites to track your activity on their site. A cookie allows the website to store and easily look up your records in their archive.
4. database: a collection of information organized in such a way that a computer program can quickly selected the desired pieces of data. Often abbreviated DB
5. data aggregation: process in which information is gathered and expressed in a summary form for purposes such as statistical analysis
6. data mining: a class of database applications that look for hidden patterns in a group of data that could be used to predict future behavior
7. data repository: generically refers to a general place where data is stored and maintained
8. data sources: name given to the connection setup from a database to a server. The name is commonly used when creating a query to the database
9. digital detritus: term used to describe unsightly debris that accrues as the result of the experience of digital living
10. dossier: a collection of documents about a person, event, or subject
11. EDR: event data recorder
12. encode: the phrase used to describe the method of preparing data for storage or transmission.
13. encryption: the translation of data into secret code
14. geotagging: the process of adding geographical information to various media in the form of metadata. The data usually consists of coordinates like latitude and longitude, but may even include bearing, altitude, distance and place names.
15. IP address: an identifier for devices on a TCP/IP network
16. ISP: Internet Service Provider
17. metadata: data about data; describes how and when and by whom a particular set of data was collected, and how data is formatted
18. PRISM: a secret program or tool that performs data collection for the NSA
19. query: a request for information from a database
20. RFID: radio frequency identification, similar to barcodes
21. server: a computer program or a device that provides functionality for other programs or devices, called "clients". A server can be used to share data or resources among multiple clients or to perform computations.

Vocab - 5

1. background: multitasking computers are capable of executing several tasks, or programs, at the same time
2. binary: pertaining to a number system that has just two unique digits
3. bot: short for robot, a computer program that runs automatically.
4. cache: a special high-speed storage mechanism
5. firewall: a part of a computer system or network that is designed to prevent unauthorized access to or from that network
6. foreground: in multiprocessing systems, the process that is currently accepting input from the keyboard or other input device
7. HTML: hypertext markup language, a standardized system for tagging text files to achieve font, color, graphic, and hyperlink effects on World Wide Web pages
8. URL: (uniform resource locator) it is the global address of documents and other resources on the World Wide Web

Unit 2 Notes

What is the Internet?

• A Global public network of independent and autonomous networks governed by the Internet Protocol Suite (IPS)
• Communication protocol

• A system of rules that govern the behavior of a system
• Diplomatic protocol

• Etiquette which governors how diplomats should behave

• Wikipedia definition: Global system of interconnected computer networks that use the IPS/TCP/IP to communicate

• Network of networks: Millions of private, public, academic, business and government networks, linked by a broad array of electronic, wireless and optical networking technologies

• Internet includes

• Interlinked hypertext documents and applications of the World Wide Web (WWW)
• Infrastructure to support email
• Peer-to-peer networks for file sharing and telephony (calling over internet rather than cell network)

• Applications for Collaboration

• Dropbox, skype, wikispaces, wiggio, www, google docs

The Internet vs. The WWW

• A common misconception -- they aren't the same!
• Wikipedia != WWW
• WWW is an...

• app that runs on the Internet
• a collection of documents, images, and resources
• it is NOT a network
• an Application service

• Based on the HTTP (Hypertext Transfer Protocol) + S (Secure)

• Internet = road; WWW = car -- They are useless without each other but not the same
• Internet applications are governed by protocols

• Email: SMTP (Simple Mail Transfer Protocol) or POP (Post Office Protocol)
• IM: IRC (Internet Relay Chat)
• Telephone: VoIP (Voice over IP)

• All of the above are considered distributed applications

• They don't run just on a single computer -- they run on a network

• Sir Tim Berners-Lee invented the WWW
  • Instead of patenting it, he made his idea freely available without royalties

• In his view, the WWW brought the Internet to a higher level of abstraction

Open Standards (changed regularly)

• HTTP is one of the many examples of the open standards that characterize the Internet
• "fundamentally based on the existence of open, non-proprietary standards"
• Not owned by any corporation; it is public
• It is created and managed through a public process by open international communities such as the IETF (International Engineering Task Force) and the W3C (WWW Consortium)

• Growth of the Internet

• Exponentially since 1984 inception
• From 0 to 1 billion domains in just 20 years

• Small dip in 2006 due to recession due to cost of domains

Mobile Apps and Mobile Devices: A First Look at Hardware and Software

Types of computers and hardware components

• General Purpose Computers -- Can run any program, or app, given to it
• Special Purpose Computers -- Fixed program that can’t be changed (e.g. Microwave, Calculator, etc.)
• Computer Programmer -- Or coder, is one who designs and writes software
• Main Hardware Components --

• Hard Drive -- Stores data permanently even when the power is off (Disk drives, flash drives, CDs, etc.)
• Central Processing Unit -- Processes program’s instructions and performs arithmetic and logic operations (Arithmetic Logic Unit and Control Unit)
• RAM -- Store’s computer programs and data temporarily while power is on, volatile/temporary storage

• Input and Output (IO Devices) --

• Input devices (touch screen, microphone, mouse, etc.) transfer information into the computer’s memory
• Output devices (touch screen, speaker, printer, etc.) transfer information out of the memory

• Motherboard and Chips --

• A motherboard -- a pre-printed circuit board that houses all of the computer’s main electronic components.
• A computer chip -- another term for an integrated circuit (IC), a component that contain millions of electronic circuits. This contains the Computer’s CPU.
• I/O Connections -- Devices can be connected here to send signals through the motherboard
• Memory chips -- The computer’s Random Access Memory (RAM)

• Chip: Integrated Circuit -- Millions of electronic components such as diodes, switches, gates and circuits can be printed on a single chip

• Nexus 4 Motherboard Back includes 2GB Samsung Ram memory chip and a Snapdragon 1.4 GHz CPU underneath with a Qualcomm audio codec and modem
• Front includes an 8 GB Flash drive insertion, a Qualcomm 4GB LTE phone chip, an accelerometer sensor, a wifi/bluetooth module and HDMI

Types of software components

• Software Interfaces -- Software serves as an interface between us and our computers (otherwise, all we’d say is strings of binary)

• e.g. Layers of Interfaces includes Application layer (app) and the Operating system layer

• Machine Language; Machine-readable -- Binary; computers only understand their own machine language (1s, 0s)

• High- and Low-level languages --
• High-level = human readable
• Low-level = machine readable (computers aren’t actually that smart)
• Translator software translates high level source code to low level binary code

• Language Abstractions --

• App Inventor code = a human-readable abstraction (taking something so complicated and taking all details away so it’s easier to read)

• Binary code = a machine-readable abstraction

• Running an App -- Reinterpret blocks whenever something changes
• Interpretation -- Process of translating source code into machine language one instruction at a time and immediately executing instruction
• Package the App into binary .apk file (android machine code, packaging file)
• Redownload the entire file if one mistake or one update
• Compilation -- Process of translating the entire source code into a single binary file

Introduction to Algorithms

• Similar to recipes

• However, computers are dumb; we are smart
• Specific information is necessary

• It is a step-by-step procedure used to complete a calculation or computation

• Each step must be completely clear, with no errors
• Precision and ambiguity, free of discrepancies
• It must be doable; if impossible, then crash

Types of algorithms

• Sequential

• Application of each step in the order of which the statements are given

• Selection / Branching

• Uses a boolean (true / false) conditional statement to select which branch of the algorithm to use

• Repetition / Iteration / Looping

• Repetition of a portion of the algorithm for a specified number of times until a condition is met

Expressing algorithms

• Basic English language
• Pseudocode

• Not executable; fake

• Real computer language

• Only algorithms expressed in a real computer language can be run

Abstractions

• One of the seven big ideas of APCSP
• Abstracting – A basic computational skill involving the process of creating abstractions, or vague terms

A general representation of something

• Literally anything

• It is impossible to speak without them

• Formed solely via the inclusion of details necessary to make them useful in some way

• Words, ideas, concepts, models, symbols -- all examples that we use every day to think and talk about the world

• In APCSP: The process of simplifying, condensing, and encapsulating information

• Assists in the reduction of complexity, making computer systems easier to use and understand
• A general concept that represents any portion of one thing

• Variables can represent any number depending on the context of the equation

The Binary Number System

• Sequences of 0s and 1s can be used to represent any and all computer data, including...

• Numbers
• Letters and text
• Images, sounds, and videos
• Instructions

• Used to represent difference between being on and off or high or low (a two-selection switch)

• Which is not inherently easy to do on a 10-option scale, or at least it is more complex that way

Binary vs. Decimal

NAME	BASE	DIGITS	PLACEHOLDERS
Decimal	Base-10	0-9	10000, 1000, 100, 10, 1
Binary	Base-2	0-1	16, 8, 4, 2, 1
Quinary	Base-5	0-4	625, 125, 25, 5, 1
Octal	Base-8	0-7	4096, 512, 64, 8, 1
Hexadecimal	Base-16	0-9; A-F	65536, 4096, 256, 16, 1

Converting between binary and decimal

1. Write the number, with spaces in between
2. Write the binary place values above the number, going right to left
3. Add up all place values with a 1 underneath them
4. The sum is the decimal value of the binary number

1....0...1...0...1

16..8...4...2...1

16..+...4...+...1...=...21

Octal

• 8-bit numbering system
• To convert to binary, break off every 3 digits, starting right to left since 7 is the largest octal (4...2...1) and can be made with those three binary digits

• 1 101 100 011 011 111 010 110 → 1 5 4 3 3 7 2 6 (22 to 8 digits)

• Conversion: Octal → Decimal

• 16 → (8 x 1) + (1 x 6) = 14
• 37 → (8 x 3) + (1 x 7) = 31
• 58 →x trick question

BINARY	OCTAL
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

Hexadecimal

• To convert to binary, break off every 4 digits, starting right to left since 15 is the largest octal (8...4...2...1) and can be made with those four binary digits

• 1111 1010 0000 0101 1011 1101 0010 → F A 0 5 B D 2 (22 to 7 digits)

• Conversion: Octal → Decimal

• 1C → (16 x 1) + (1 x 12) = 28

81CG →x trick question

BINARY	HEXADECMIAL
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

Hardware Abstractions: Gates and Logic

• The higher the level of abstraction; the more it is based on implication
• Binary data is processed by physical layers of hardware

• Motherboard is most abstract
• Computer; integrated system of functional components
• Then integrated circuits

• Very complex; low-level elements are combined into complex integrated circuits or computer chips

• Functional Component = RAM; at the highest levels, these are created for specific functions
• Gates and flip flops

• Basic circuits are combined into basic computational elements such as AND gates and S/R flip flops
• Light switch is on until turned off, so it’s a flip flop

• Electronic circuits

8At the lowest level, physicists and electrical engineers develop materials and design and build electronic circuits that are composed of transistors, the fundamental building block of electronic devices

• Transistors

Types of gates

• Gates are tiny electronic circuits that perform basic logic operations

• Physical AND gate - power is sent through only when both switches A and B are closed

• Logical (Boolean) AND Gate - Light is off if one switch is open

• Physical OR gate - power is sent through if one switch; A or B; is closed

• Logical (Boolean) OR Gate - Light is off when both switches are open

• NOT gate - if A is true, Z is false and Z is true when A is false (opposite)

• Combining these three gates make electronic components

• NAND gate = AND + NOT

• Only false if ALL inputs are true

• NOR gate = NOT + OR

• Only true if ALL inputs are false

• Example: A Flip Flop circuit
• Latch / Flip-flop is a circuit with two-states and can be used to store 1 bit of data, a 0 or a 1, until changed
• Other gates

• Exclusive OR / XOR - If A or B = true, then 1 ; If A and B true, then 0

Unit 3 Notes

Representing Images

• It’s all bits!
• Run-Length Encoding (RLE)

• RLE Compression

• 1. White pixels, # Black pixels, # White pixels…
• 16: Row 1 has 16 white pixels
• 12, 3, 1: Row 2 has 12 white, 3 black, 1 white
• 6, 9, 4, 2, 0: Row 3 has 6w, 9b, 4w, 2b, 0w
• Always starts white - if starts black, then starts with 0
• Lossless compression technique
• Good for images with lots of whitespace (e.g. fax)
• Used in BMP images (bitmap - in line drawings mostly)

• Lossless vs. Lossy Compression

• Lossless: Original image can be perfectly reconstructed from the compressed data

• Good for medical, archival images
• Used in BMP images

• Lossy: Some data may be lost during compression

• Ok for camera images where the lost data cannot be perceived by the human eye (e.g. JPEG or Zip)

• How much data?

• Original image: 16x16 = 256 pixels
• RLE: 62 numbers
• Monochrome images

• 1 bit per pixel
• 256 pixels = 256 bits
• 1 = white, 0 = black
• Old technique from 1960s

• Saving:

• 256 pixels original (1 bit per pixel)
• 62 numbers compressed (8 bits per number) = 496 bits
• Not saving anything!

• 8-bit Color Image

• 1980s

• RGB = Red / Green / Blue = Can only represent 255 colors
• 8 bits per pixel
• 3R, 3G, 2B
• 0 1 2 3 4 5 6 7
• R R R G G G B B
• 1 1 1 0 0 0 1 1 = Magenta
• 0000 0000 = Black (0)
• 1111 1111 = White (1)

• Modified RLE

• Color specification if more than 2 colors
• 255.16 -- 255.12, 0.3, 255.1, etc.
• Twice the numbers = 992 bits
• 124 vs. 256 is saving space

• 24-bit Color Image

• RGB
• 24 bits per pixel (8R, 8G, 8B)
• 2^24 = 16,777,216 = More than the human eye can see
• Four times as many numbers - 248 with 8 bits/number = 1984 bits

• Amount of RLE Compression

• Dependent on number of bits per pixel
• More importantly… depends on number of colors in the image

• Binary represents numbers, colors, and machine language!

• 0100 0001 could be 65? A? Magenta? It depends on how it’s used!
• Image? Text? Spreadsheet?

• Representing Character Data

• ASCII = American Standard Code for Information Interchange in the 1060s
• 7-bit code, 128 characters

ASCII Charts (copied from Wikipedia article)

Binary	Oct	Dec	Hex	Glyph
				1963	1965	1967
010 0000	040	32	20	space
010 0001	041	33	21	!
010 0010	042	34	22	"
010 0011	043	35	23	#
010 0100	044	36	24	$
010 0101	045	37	25	%
010 0110	046	38	26	&
010 0111	047	39	27	'
010 1000	050	40	28	(
010 1001	051	41	29	)
010 1010	052	42	2A	*
010 1011	053	43	2B	+
010 1100	054	44	2C	,
010 1101	055	45	2D	-
010 1110	056	46	2E	.
010 1111	057	47	2F	/
011 0000	060	48	30	0
011 0001	061	49	31	1
011 0010	062	50	32	2
011 0011	063	51	33	3
011 0100	064	52	34	4
011 0101	065	53	35	5
011 0110	066	54	36	6
011 0111	067	55	37	7
011 1000	070	56	38	8
011 1001	071	57	39	9
011 1010	072	58	3A	:
011 1011	073	59	3B	;
011 1100	074	60	3C	<
011 1101	075	61	3D	=
011 1110	076	62	3E	>
011 1111	077	63	3F	?
100 0000	100	64	40	@	`	@
100 0001	101	65	41	A
100 0010	102	66	42	B
100 0011	103	67	43	C
100 0100	104	68	44	D
100 0101	105	69	45	E
100 0110	106	70	46	F
100 0111	107	71	47	G
100 1000	110	72	48	H
100 1001	111	73	49	I
100 1010	112	74	4A	J
100 1011	113	75	4B	K
100 1100	114	76	4C	L
100 1101	115	77	4D	M
100 1110	116	78	4E	N
100 1111	117	79	4F	O
101 0000	120	80	50	P
101 0001	121	81	51	Q
101 0010	122	82	52	R
101 0011	123	83	53	S
101 0100	124	84	54	T
101 0101	125	85	55	U
101 0110	126	86	56	V
101 0111	127	87	57	W
101 1000	130	88	58	X
101 1001	131	89	59	Y
101 1010	132	90	5A	Z
101 1011	133	91	5B	[
101 1100	134	92	5C	\	~	\
101 1101	135	93	5D	]
101 1110	136	94	5E	↑	^
101 1111	137	95	5F	←	_
110 0000	140	96	60		@	`
110 0001	141	97	61		a
110 0010	142	98	62		b
110 0011	143	99	63		c
110 0100	144	100	64		d
110 0101	145	101	65		e
110 0110	146	102	66		f
110 0111	147	103	67		g
110 1000	150	104	68		h
110 1001	151	105	69		i
110 1010	152	106	6A		j
110 1011	153	107	6B		k
110 1100	154	108	6C		l
110 1101	155	109	6D		m
110 1110	156	110	6E		n
110 1111	157	111	6F		o
111 0000	160	112	70		p
111 0001	161	113	71		q
111 0010	162	114	72		r
111 0011	163	115	73		s
111 0100	164	116	74		t
111 0101	165	117	75		u
111 0110	166	118	76		v
111 0111	167	119	77		w
111 1000	170	120	78		x
111 1001	171	121	79		y
111 1010	172	122	7A		z
111 1011	173	123	7B		{
111 1100	174	124	7C	ACK	¬	|
111 1101	175	125	7D		}
111 1110	176	126	7E	ESC	|	~

ASCII (1977/1986)

	_0	_1	_2	_3	_4	_5	_6	_7	_8	_9	_A	_B	_C	_D	_E	_F
0_ 0	NUL 0000	SOH 0001	STX 0002	ETX 0003	EOT 0004	ENQ 0005	ACK 0006	BEL 0007	BS 0008	HT 0009	LF 000A	VT 000B	FF 000C	CR 000D	SO 000E	SI 000F
1_ 16	DLE 0010	DC1 0011	DC2 0012	DC3 0013	DC4 0014	NAK 0015	SYN 0016	ETB 0017	CAN 0018	EM 0019	SUB 001A	ESC 001B	FS 001C	GS 001D	RS 001E	US 001F
2_ 32	SP 0020	! 0021	" 0022	# 0023	$ 0024	% 0025	& 0026	' 0027	( 0028	) 0029	* 002A	+ 002B	, 002C	- 002D	. 002E	/ 002F
3_ 48	0 0030	1 0031	2 0032	3 0033	4 0034	5 0035	6 0036	7 0037	8 0038	9 0039	: 003A	; 003B	< 003C	= 003D	> 003E	? 003F
4_ 64	@ 0040	A 0041	B 0042	C 0043	D 0044	E 0045	F 0046	G 0047	H 0048	I 0049	J 004A	K 004B	L 004C	M 004D	N 004E	O 004F
5_ 80	P 0050	Q 0051	R 0052	S 0053	T 0054	U 0055	V 0056	W 0057	X 0058	Y 0059	Z 005A	[ 005B	\ 005C	] 005D	^ 005E	_ 005F
6_ 96	` 0060	a 0061	b 0062	c 0063	d 0064	e 0065	f 0066	g 0067	h 0068	i 0069	j 006A	k 006B	l 006C	m 006D	n 006E	o 006F
7_ 112	p 0070	q 0071	r 0072	s 0073	t 0074	u 0075	v 0076	w 0077	x 0078	y 0079	z 007A	{ 007B	| 007C	} 007D	~ 007E	DEL 007F

  Letter   Number   Punctuation   Symbol   Other   Undefined   Changed from 1963 version

Parity Error Checking

• Error Detection

• Everything is bits -- i.e. all data are represented as binary 0s and 1s
• Errors may occur during transmission of data / while data is being written to a desk drive
• Even one error may make a significant difference

• Scenario

• 8 BIT: Bank 00000001 ($1) flipped → 10000001 ($129)
• 16 BIT: 0000000000000001 ($1) flipped → 100000000000000 ($32,769)

• Detecting the Error

• Parity bit error detection
• Uses redundancy -- extra bits are added to the data to enable us to detect the error

• Parity: Evenness or oddness of a number
• Parity bit: Additional bit added to each row and column to make the row or column have an even number of 1 bits
• Parity Schemes

• Even: The number of 1s in the sequence add up to an even number
• Odd: The number of 1s in the sequence add up to an odd number

ASCII = 7 bit

Unit 4 Notes

Pseudo Random Numbers

• How computers do (or compute) randomness?

• True Randomness - Tough to do on a computer

• Radioactive decay
• Weather
• Flipping a coin
• Rolling dice
• Drawing cards from a well-shuffled deck

• Pseudo Randomness is simulated by computers

• Uses algorithm to spew out however many numbers wanted
• Generates sequences of numbers
• Appears to be random, but isn't

• Pseudo Random Number Generator (PRNG)

• Uses algorithm
• Generates random-looking sequence of numbers
• Useful in cryptography, computer games, weather models
• Used by Random (integer) blocks in App Inventor to produce random numbers
• Formula needed that calculates next value in sequence given the current value
• Given the current value in the sequence, Xi
• Generate the next value, Xi+1 , which equals Xi * 2 +1
• So, 21 → PRNG → 43 → PRNG → 87

• Clock Arithmetic (12-hour)

• 9:00 + 4 hours = 1:00 (not 13:00)
• 9 + 4 = 13 - 12 = 1

• Modular Arithmetic

• 24 + 9 = 31 - 12 = 19 - 12 = 7

• Modulo (mod) operation

• Repeatedly subtract x (the modulus) until we get a number between 1 and x
• Xi+1 = Xi * 2 + 1 mod 13 → 10, 8, 4, 9, 6, 0, 1, 3…
• Smallest number on right and trying to fit that into left
• 31 mod 12 = 7
• 5 mod 31 = 5 (if it doesn’t fit, number doesn’t change)
• Cyclical randomness… eventually starts to repeat itself

• Linear Congruential PRNG

• Uses a linear function

• Other types…

• Limited CGs (LCG) have certain desirable characteristics due to good randomness qualities, speed, and limited requirement of memory but not good enough for cryptographic applications and certain simulations due to ease in ability of figuring out the algorithm

• So, a PRNG is…

• A computational model of randomness
• An abstraction of real randomness, since it’s an algorithm and not real randomness
• Is it a good model? Is it equally like to…

• generate any number within a 1-100 range?
• generate “Heads” or “Tails”?

8draw any card out of a shuffled deck of 52 cards?

• Casino slot machines aren’t fully random

Unit 5 Notes

Search algorithms

• Binary search - splitting ordered lists half each time to eliminate half each guess
• Linear search - flipping through unordered lists to find what you need