My blogs chronicle my experience as a technologist making my way into Silicon Valley. I am a queer person of color, gender non-conforming, immigrant, and ex-foster youth. I come from a non-traditional coding background. I studied a few CS courses in college and ended up majoring in the humanities before becoming a teacher. Teaching web development to under served teens turned me on to coding. After finishing at a coding school, I began working at start ups in San Francisco. Half of my blogs are about technical subjects and the other half are about equality and tech access (my journey).
Chose another tutorial from Brian Holt this week. What I love about learning from Brian is that he understands self-learning, well because he admits to dropping out of college and being self-taught. He explains everything in plain English, humbly acknowledges that the tools he uses or how he goes about solving a problem is an “opinion” and emphasizes that there are other ways of achieving the same result. He says things like, “The first time you learn recursion is tough. But once you get it, you start to realize that it is hard but it’s simple.” He also adds a caveat that this course is not a replacement for taking 4 semesters of comp sci. I know dropping out of college and being ‘self-taught’ is kind of a running joke in the tech industry, if the show Silicon Valley is any indication of that:
Big Takeaways:
- Big O
- Recursion
- Sorting Algorithms
- Data Structures
Big O Notation
In simple terms, Big O is the measurement of the time it takes to perform x number of operations with n inputs. For example, if you have the equation, 3x² + x + 1. Big O takes into account the operation x² which gives us the largest number in the equation. The Big O for this equation then would be O(n²) because if we add up the operations O(n²) + O(1) + O(1) = O(2n²) and we drop the coefficient because it is inconsequential as the numbers get larger. Let’s try calculating the Big O using another function.
var crossAdd = function(input) {var answer = [];for (var i = 0; i < input.length; i++){var goingUp = input[i];var goingDown = input[input.length-1-i];answer.push(goingUp + goingDown);}return answer;}
Let’s calculate Big O, crossAdd is an assignment so that is O(1), so is answer. So we have, O(1) + O(1). Our for loop O(1) + O(n) + O(n). Another assignment, O(1) + O(n) + O(n) + O(1). In total, we have O(5) + O(4n). Since O(1) is a constant, we can drop the O(5). The coefficient in front of the n will matter less and less as the number gets larger so we are left with O(n). Try another:
function makeTuples(input) {var answer = [];for (var i = 0; i < input.length; i++) {for (var j = 0; j < input.length; j++) {answer.push([input[i], input[j]]);}}return answer;}
Keeping track of the operations that affect the program the most, the 2 for loops means we have to go through the inputs O(n) * O(n) times which equals O(n²).
Recursion
- a function is calls itself inside of its code block
- must have a base case (breaks the function out of the recursive call)
- if your base case fails you get stack overflow — function is called until there is no more memory left in the stack (high cost, use for or while loops — iteration instead of recursion)
When do we use recursion? Invoking a function multiple times entails overhead since the function’s stack frame must be created. This involves memory operations and CPU register updates, at the lowest level. Iteration / Loops require none of this additional work. If we have a program that requires a user to call a recursive function multiple times, this is not efficient, iteration would work better.
function countdown(current) {if(current <= 0) return;wr(current);countdown(current-1)}
Famous recursive function — Fibonacci
function fibonacci(num) {if(num <= 2) {return 1} else {return fibonacci(num — 1) + fibonacci(num — 2)}}
Equally famous recursive function — Factorial
function factorial(num) {if(num < 2) {return 1} else {return num * factorial(num — 1)}}
Sorting Algorithms
//create a function that will swap numbers
//write a function that will take a list, index1, and index2function swap(list, index1, index2) {let swapped = list[index1]list[index1] = list[index2]list[index2] = swapped}
- Bubble Sort — highly inefficient, because with an external and an internal loop, plus other constant operations, the algorithm’s Big O is equal to O(n²).
//loop across the list to keep track if you are atthe beginning of the end//loop across the list to swap letters//return the new list
function bubbleSort(items){let len = items.lengthfor (let i=0; i < len; i++){for (j=0, stop=len-i; j < stop; j++){if (items[j] > items[j+1]){swap(items, j, j+1);}}}return items;}
2. Insertion Sort — more complex, occasionally useful. See pseudocode for explanation
//ex: [5, 3, 1] => inserts 3 into the 5 position, now 2 are sorted to [3, 5, 1] => makes a copy of 1 compares it to 5, moves 5 into its spot => look
function insertionSort(array) {for(var i = 0; i < array.length; i++) {var temp = array[i];var j = i — 1;while (j >= 0 && array[j] > temp) {array[j + 1] = array[j];j — ;}array[j + 1] = temp;}return array;}
3. Merge Sort — divide and conquer, splits the array up into a left sorted and a right and then we put it back together
function stitch(left, right) {const results = []while(left.length && right.length) {if(left[0] <= right[0]) {results.push(left.shift())} else {results.push(right.shift())}}while(left.length){results.push(left.shift())}while(right.length) {results.push(right.shift())}}
Merge Sort
function mergeSort(nums) {if(nums.length < 2) {return nums}const length = nums.lengthconst middle = Math.floor(length / 2)const left = nums.slice(0, middle)const right = nums.slice(middle, length)const sortedLEft = mergeSort(left)const sortedRight = mergeSort(right)return stitch(mergeSort(left), mergeSort(right))}
4. Quick Sort — another divide and conquer algorithm, most powerful sorting algorithm, recursive. The basic gist is that you take the last element in the list make that the pivot. Everything that’s less than the pivot gets put into a “left” list and everything that’s greater get’s put in a “right” list. You then make a recursive call for quick sort on the left and right lists, concatenate the sorted left list, the pivot, and then the right list (in that order.) The base case is when you have a length 1 or 0, return the list.
function quicksortBasic(array) {if(array.length < 2) {return array;}var pivot = array[0];var lesser = [];var greater = [];for(var i = 1; i < array.length; i++) {if(array[i] < pivot) {lesser.push(array[i]);} else {greater.push(array[i]);}}return quicksortBasic(lesser).concat(pivot,quicksortBasic(greater));}
Data Structures
Array List vs. Linked Lists
Array Lists — requires interacting with allocated pieces of memory. In Java, you have to declare the size of your array. Typical methods are: push, pop, find, and delete (_collapseTo which is a helper function for delete in this tutorial).
Linked Lists — have a head, tail, next, and previous (if doubly linked). Linked lists are useful in avoiding data collisions via duplicate keys in a hash table. They are also useful in deletion and insertions.
Binary Search Tree (BST) — Fast for searches, BSTs can have 0, 1, 2 children. Left is less than the parent node. Right is greater than the parent. Lookups are O(log n). BSTs are not used in production. Self-balancing trees are used in production.
class Node {constructor(data, left=null, right=null) {this.data = datathis.left = leftthis.right = right}}
class Tree {constructor() {this.root = null;}
add(value) {if (this.root === null) {this.root = new Node(value);} else {let current = this.root;while(true) {if (current.value > value) {// go leftif (current.left) {current = current.left;} else {current.left = new Node(value);break;}} else {// go rightif (current.right) {current = current.right;} else {current.right = new Node(value);break;}}}}return this;}
toJSON() {return JSON.stringify(this.root.serialize(), null, 4);}
toObject() {return this.root.serialize();}}
There was definitely a LOT of information in this tutorial and I was definitely drinking through the firehose trying to absorb it all. I WILL DEFINITELY be watching this again.