##IV: Abstract Data Types & Data Structures: Storing data on memory{ Array Inserting elements in arrays are "expensive" Arrays have fixed sizes (need to find contiguous open space)
Linked list Every element also needs to store a reference to the next item in the list
ADTs vs DTs Abstract Data Types vs Data Type
Abstract Data Types [ADT]s (does not refer directly to memory): Stack and Queues: CAN NOT ACCESS PARTICULAR ELEMENT Both are lists and can store duplicate values
Stack : LIFO => Push to top, and pop from top
Queues: FIFO => Unshift to back, and pop from front
Data Structures are used to implement data structures You can use an array to implement the stack or queue ADTs
Immutable (Primative) Data Types in JS:
Undefined Null Boolean String Numbers Symbol
IN JS Strings are encoded using UTF-16!
The only non-Primative DT is Object (everything else is an Object)
Trees NEVER have branches converge.
Binary search tree (each node has <=2 children); Create a chain of numbers where each node that is smaller than the previous is placed on the left (larger => right) EG:
10
8 15
4 9
Searching a tree Breadth-first: Go across each level first; Should implement with queue
Depth-first: * Pre-order: Process current node, then roots, * In-order: First process left most root, process root node, process right subtree * Post-order: Process the root most ones first. (allows for save delete in languages with memory leaks)
Hash Table: Use a hash function to create the index value that will store the data in the array. We will implement a hash table by using objects or arrays to store multiple pairs when index values collide.
##I: Information Theory & Hardware: Storage SSD<HD<Optical Drive (CD)<Tape Drive Non-volatile (perminant) Memory RAM<L2 Cache<L1 Cache<CPU Registry volatile (not stored between sessions)
Computers can only manipulate information on the Registry. The # of bits (64 > 32) is called a word.
##II: Abstractions & Encoding (ALWAYS USE UTF-8) Notations: Binary : 8 bits each is 2^place Floating-Point Signed Double notation : 64 bits = 1(sign) 11(exponent) 52(fraction) Hexadecimal Notation: base 16 - converts easily to binary, uses 4 binary bits ?!?!
ASCII: 7-bits to signify different glifs
011 0000 - 0 - First Number Glyph
100 0001 - A - First Letter Glyph
UTF-8: Standerdized 8-bit coding for Unicode
Unicode = U+[4 digit Hex Code]
UTF-16: Shitty version of UTF-8; incompatable with ASCII
Image encoding (Red / Yellow / Blue subpixels in each pixel) 24-bits can enclode each pixel (8 per sub)
##III: Software & APIs Machine code: instruction (8-bit) a CPU can interpret Assembly: shortened codes for 8 bit instructions
Compiler: Translates specified source language into object [presumably machine] code Need new code every time Hardware changes. Now instead we have Source Code => Object Code => Operating System => Hardware Devices
Compile run by compiler (runs ahead of time / faster) vs Interpreted (Like JS) using Engine (V8) Run the language as soon as you read it, slower.