CS_Fundementals.md

Computer Science Fundementals

Recursion

• a function that calls itself
• Base Case: a terminating scenario that does not use recursive power to produce an answer.
• Recursive Case: A set of instructions, moving towards the base case, that end in a call to the same function.
• Ex.) Factorial:

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n-1);
}

factorial(3);

• Ex.) Fibonacci Sequence (find the nth number in the sequence):

function fibonacci(num) {
  if (num <= 1) return 1;

  return fibonacci(num - 1) + fibonacci(num - 2);
}

• Ex.) Sum of an array:

function sum(arr) {
  if(!arr.length) return 0;
  let number = arr.pop();
  return number + sum(arr)
}

• Ex.) Reversing a String:

function revStr(str) {
  if (str.length <= 0) return '';
  const strArr = str.split('')
  let letter = strArr.pop();
  str = strArr.join('')
  return letter += revStr(str)
}

// or

function revStr(str) {
  if (str.length <= 0) return '';
  letter = str.slice(str.length-1)
  return letter + revStr(str.substr(0, str.length-1))
}

// or

function revStr(str) {
  return str.length < 1 ? '' : str.slice(str.length-1) + revStr(str.substr(0, str.length-1));
}

revStr('wheres the cash at');

• Calculating the power of a number

function power(num, exp) {
  return exp < 1 ? 1 : num * power(num, exp - 1)
}

power(3, 2);

• Calculating the steps to get back to 1: The Collatz conjecture applies to positive numbers and speculates that is alway possible to get back to 1 if you follow these steps:
  • If n is 1, stop.
  • Otherwise, if n is even, repeate this process on n/2.
  • Otherise, if n is odd, repeat this process on 3n + 1.
  • Write a recursive function that calculatees how many steps it takes to get to 1:

n	collatz(n)	Steps
2	1	2 > 1
3	7	3 > 10 > 5 > 16 > 8 > 4 > 2 > 1
4	2	4 > 2 > 1

function calcSteps(n) {
  if (n === 1) return 0;
  if (n % 2 === 0){
    return 1 + calcSteps(n/2);
  } else {
    return 1 + calcSteps(n*3 + 1);
  } 
}

// or

function calcSteps(n) {
  return n < 2 ? 0 : 1 + calcSteps(n % 2 === 0 ? n/2 : n*3 + 1);
}

calcSteps(3)

Sorting Algorithms

• BubbleSort and SelectionSort take significantly more time to process each time the dataset gets larger.
• BubbleSort and SelectionSort are perfectly fine to use on smaller datasets that will remain small.
• MergeSort is much better suited for large datasets, but is a little more complex to implement.

Sorting Algorithm	Runtime (Big O Notation)
BubbleSort	n^2
SelectionSort	n^2
MergeSort	n * log(n)

Bubble Sort

• Runtime: n^2
• 'bubbles' the largest elements to the end
• For each element, bubbleSort has an inner loop that also loops through each element until array.length - i (gets smaller each outer iteration), it then checks that 'j' item against 'j + 1' and if 'j' is larger they swap. It continues this process until the largest 'j' item is 'bubbled' to the end. This process continues until 'i' reaches array.length-1 unless checks are in place to see if it has already been sorted.
• Steps:
  1. Loop through each element in the array (outer loop)
  2. For each element, loop through each element again to array.length - i (i increases, so the j iteration becomes smaller for each i iteration)
  3. if the element j is greater than j + 1, swap the elements

const nums = [3, 4, 2, 5, 2, 8, 5, 4];

function bubbleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < (arr.length - 1 - i); j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

bubbleSort(nums);

Optimized Bubble Sort

function bubbleSort(arr) {
  let swapped;
  for (let i = 0; i < arr.length - 1; i++) {
    if (swapped === false) {
      return arr;
    }

    console.log('running the loop!');
    swapped = false;

    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
  }
  return arr;
}

Selection Sort

• Runtime: n^2
• For each element, selectionSort assumes that element is the min, it then iterates through the rest of the array and compares each value to the element, if any of these values are less than the original element, they are swapped
• Nickname: prove me wrong algorithm
• Steps:
  1. Iterate through each array item
  2. Assume the element at 'i' is the least in the array, assign 'i' to 'indexOfMin'
  3. For j from i + 1 to end of array
  4. See if there is an element with a lower value than i
  5. If there is, record its index
  6. If the index of the current element and the index of the 'lowest' element is not the same, swap them

function selectionSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    let indexOfMin = i;
    for(let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j;
      }
    }
    if (indexOfMin !== i) {
      [arr[i], arr[indexOfMin]] = [arr[indexOfMin], arr[i]]
    }
  }
  return arr;
}

selectionSort(nums)

Merge Sort

• Splits the array in half and then calls MergeSort recursively
• Merge sort uses two functions:
  1. MergeSort
  2. Merge (called within MergeSort, can sort and merge 2 sorted arrays)
• Merge Steps:
  1. Create 'results' array
  2. While there are still elements in both arrays:
  3. If the first element (index 0) in the left half is less than the first than the first element (index 0) in the right half * 'shift' the element from left into a 'result' array
  4. else * 'shift' the element from right into a 'result' array
  5. Take everything from the array that still has stuff in it and put it in 'results'
• MergeSort function steps:
  1. Check base case: Array.length === 1.
  2. Find the center of the array: Math.floor(arr.length / 2)
  3. Split the array into left and right using .slice
  4. return merge while passing in (mergeSort(left), mergeSort(right)) as the params

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr
  }
  const center = Math.floor(arr.length / 2)
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge (mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  const results = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  return [...results, ...left, ...right];
}

Insertion Sort

• shift the first item off the array and put it on the second array
• keep shifting numbers off the original array, save to variable, compare then set new index
• compare the shift number to the last item in the new array, if smaller swap, bubble the number down until it is greater than the previous number (reverse for loop)

Quick Sort

• pick a pivot point and pop off the array (usually the last item anyway)
• create two new arrays: one less than the pivot and one greater than the pivot
• keep poping off numbers from the original and compare to the pivot, if greater push into greater array, if less than push into less than array.
• can now assume that the pivot is in its correct index
• recursively call quickSort on the lessThanArray and the greaterThanArray
• Steps:
  1. Establish a base case, if array.length <= 1 return that array
  2. use array.pop() to take the last element of the array and save it as the pivot
  3. create two empty arrays named lessThan or greaterThan
  4. for loop to iterate over the original array, if the currentElement is less than pivot, push the element into lessThan, else push the element into greaterThan
  5. recursively call quickSort on the lessThan array and the greaterThan array

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr.pop();
  const lessThan = [];
  const greaterThan = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      lessThan.push(arr[i])
    } else {
      greaterThan.push(arr[i])
    }
  }
  return [...quickSort(lessThan), pivot, ...quickSort(greaterThan)]
}

quickSort(nums)

Data Structures

• ways to store data in an application
• array, object, stack, linked list, binary search tree

Linked List

• data structure composed of nodes (spaces in memory that contain some data)
• each node only knows about the node after it
• head or root node is the first node in the linked list

---

• types: singly linked list, doubly linked list, circular linked list
• compared to arrays: cheaper to add & remove items, difficult to search/access individual items

Creating a Linked List with a JS object

{
  head: {
    data: 1,
    next: {
      data: 2,
      next: {
        data: 3,
        next: null
      }
    }
  }
}

Binary Search Tree

• parent child relationship, top parent is called the root, last child is called a leaf.
• particularly good for inserting, finding and moving around data in an efficient, cheap way.
• rules:
  1. Each BST has a root node, which contains data and has no parent nodes.
  2. Each node has zero to two, child nodes (word binary comes from max 2 child nodes)
  3. Each child node linked to the left has a data value less than or equal to the parent node.
  4. Each child node linked to the right has a data value greater than the parent node.
  5. Ideally you want to avoid duplicates, conditional logic in nodes to catch duplicates, most data being entered in BST's will be unique by default

• Insert sudo code:

  1. class Binary Search Tree
  2. root node = null;
  3. class Node
  4. data = value;
  5. left = null;
  6. right = null;
  7. Check the node (default to root)
  8. Compare to node
  9. check if the currNode has children
  10. if true, move down and repeat process for next node, else set as child to currNode

• Find sudo code:

  1. check the root
  2. compare
  3. if less than check left child, if greater than check right child
  4. repeat

  Traversing the trie: Depth First Search vs. Breadth First Search

  • both vising every node in the tree

DFS	BFS
Finish all the nodes (including the grandChildren)	Visit all nodes at the same depth (children before grandChildren)
PreOrder, InOrder, PostOrder	by Level

Stack

• First In, Last Out
• 2 methods: Push() & Pop()

Higher Order Functions

• A function that takes another function (callback) as an argument, and/or, returns a function.
• examples: .then, .map, .filter, .reduce

const add = (num1, num2) => {
  return num1 + num2
}

// takes in a function
const compute = (operation, num1, num2) => {
  return operation(num1, num2)
}

// returns a function
const computer = operation => {
  return (num1, num2) = operation(num1, num2)
} 

Currying

• decomposing a function with multiple arguments into a chain of functions each with only one argument

const multiply = (x, y) => {
  return
}

multiply(3, 4)

const curriedMultiply = x => {
  return (y => {
    x * y
  })
}

const triple = curriedMultiply(3)

triple(4) // 12

// implicit returns
const implicitCurriedMultiply = x => y => z => {
  return x * y * z;
}

implicitCurriedMulitply(3)(4)(5); // 60

Call Stack

• Stack Frame - element on the stack