This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Table of Contents
Big O & Recursion
Introduction
- Brian Holt begins by introducing himself and talking about why he developed this course. He also shares some recommended reading and outlines the topics he’ll be covering. The goal of this course is to provide a practical introduction to computer science concepts for those who already know JavaScript.
Big O
- Big O is a method for analyzing the efficiency of algorithms. In an equation, Big O may represent an exponential value since it’s the largest term in the equation. All other insignificant coefficients are ignored.
Finding Big O
- Brian demonstrates how to calculate Big O on a few functions. When a loop is present, the Big O value is typically related to the number of iterations required by the loop or the number of nested loops. If a function simply returns a value without any iteration, the function would have a Big O value of 1 or “constant time”.
Recursion
- In the context of computer science, recursion occurs when a function calls itself. Recursion is a powerful programming technique due to it’s ability to maintain state during subsequent function calls. However, problems like a stack overflow can arise if a recursive function is not implemented correctly.
Recursion Example
- Brian walks through a few recursion examples including how to generate a Fibonacci sequence. He also stresses the beginning of any recursive function should contain the base case to prevent any stack overflow errors.
Exercise 1: Recursion
- In this exercise, you will make a function that computes the factorial of any number recursively. Before starting the exercise, Brian answers a few audience questions about the previous recursion example.
Exercise 1 Solution
- Brian walks through the solution to exercise 1. He also demonstrates how to include unit testing libraries in Codepen.
Sorting Algorithms
Bubble Sort
- The bubble sort algorithm is typically the easiest to conceptually understand but the least efficient in execution. It continually loops through an array comparing adjacent indexes until the entire array is sorted. Brian uses a simple array of values to demonstrate the bubble sort order of execution and Big O value.
Exercise 2: Bubble Sort
- In this exercise, you will create a bubble sort function that compares two adjacent numbers and swaps their places if the smaller indexed value is greater than the larger indexed value.
Exercise 2 Solution
- Brian walks through the solution to exercise 2.
Insertion Sort
- In a worst-case-scenario, insertion sort has a similar efficiency to bubble sort. However, with data sets that are already partially sorted, insertion sort can be highly effective. It works by taking items from the unsorted portion of the list and placing them into their sorted position.
Exercise 3: Insertion Sort
- In this exercise, you will create an insertionSort() function with two loops. The outer loop will be stepping through each item in the array. The inner loop will place the targeted item in the proper position in the sorted part of the array.
Exercise 3 Solution
- Brian walks through the solution to exercise 3. He also shares the bigocheatsheet.com website which provides Big O best and worst-case scenarios for many algorithms.
Merge Sort
- Merge sort is a divide-and-conquer algorithm that uses recursion to divide a list into smaller pieces for sorting. This division continues until you have a list of one. After introducing merge sort, Brian also explains the need for a stitching function and talks about merge sort’s Big O and spacial complexity.
Exercise 4: Merge Sort
- In this exercise, you will write a mergeSort() function that will take an array of numbers and return a sorted array of numbers.
Exercise 4 Solution
- Brian walks through the solution to exercise 4. In the solution he creates a mergeSort() function and an accompanying stitch() function for combining the sorted array parts. He also briefly explains the ES6 Array spread operator.
Median Values
- Brian spends a few minutes talking about some of the other ways sorting algorithms can be used. For example, to find the median value of two lists, a modified version of the stitch() function could be created to combine the lists until the medium index is reached.
Quick Sort
- Quick sort is one of the most useful and powerful sorting algorithms. Like merge sort, quick sort uses recursion to divide-and-conquer. The last element in the list is used as the “pivot”. Everything smaller than the pivot is place in a “left” list. Larger values are placed in a “right” list. Quick sort is then performed again on the left and right lists.
Exercise 5: Quick Sort
- In this exercise, you will create a quickSort() function that will grab a pivot from the end of the list and create two lists of values that are greater than and lesser than the pivot. The function will then recursively execute on these subsequent lists until all values are sorted and concatenated back into a single list.
Exercise 5 Solution
- Brian walks through the solution to exercise 5. He also shares a few final thoughts about the various sorting algorithms he covered throughout this section.
Data Structure Interfaces
Interfaces Data Structure
- Brian introduces the concept of interfaces and how they behave like a black box. They provide details about how they can be used without exposing their implementation. Before moving into the first interface topic, Brian answers a few lingering audience questions about sorting algorithms.
Set Data Structure
- A set is a data structure than has four basic operations: Items can be added, items can be removed, a “contains" method can verify an item’s existence, and the set can return a list of it’s items.
Map Data Structure
- Maps, or dictionaries as they are sometimes referred to, are key-value sets. Maps are also very similar to an associative array. Since the keys in a map are a set, there cannot be any duplicates. When a value of a key is updated, the previous value is lost.
Stack Data Structure
- A stack is an interface that adheres to the “last-in first-out” principle. You can only push (add) or pop(remove) from the stack. Stacks may also contain a “peek” method to view the current top value without modifying the stack.
Queue Data Structure
- A queue is a “first-in first-out” data structure similar to a waiting line. Like a stack, queues have push/pop methods called enqueue and dequeue. They are useful for items that need to be handled in order or prioritize based on their need.
Implementing Data Structures
Array List
- Array lists are created from directly interacting with the allocated memory. They are simple in the way they are constructed. However, inserting and removing values can be costly since the entire list must be collapsed or expended to accommodate the updated value.
Exercise 6: Array List
- In this exercise you will approximate an implementation of ArrayList. Brian begins the exercise by stubbing out the class and member functions needed in the implementation. He then gives the group time to complete the exercise.
Exercise 6 Solution
- Brian walks through the solution to exercise 6.
Linked List
- Brian spends a few minutes diagramming linked lists and comparing their specifications with array lists. Linked lists are composed of nodes which point to the next node in the list. While item retrieval is slower with a linked list, adding and removing is much faster.
Exercise 7: Linked List
- In this exercise, you will implement a linked list. Like the previous exercise, Brian begins by stubbing out the the two classes necessary for his implementation.
Exercise 7 Solution Part 1
- Brian begins walking through the solution to exercise 7.
Exercise 7 Solution Part 2
- Brian finishes the solution to exercise 7.
Binary Search Tree
- Trees are useful middle ground between array lists and linked lists. Brian introduces the Binary Search Tree which is composed of nodes with 0, 1, or 2 subtrees. Elements in the left subtree are lesser than the node value. Elements in the right subtree are greater than the node value.
Exercise 8: Binary Search Tree
- In this exercise, you will create a binary search tree. The Tree class will keep track of a root which will be the first item added. From there, if the item is less than the value of that node, it will go into its left subtree and if greater it will go to the right subtree.
Exercise 8 Solution
- Brian walks through the solution to exercise 8.
AVL Tree
- AVL trees are a specialized binary search tree. When values are added to an AVL tree, a recursive call will check to see if any rebalancing is necessary. A tree is considered out of balance if the difference in height of any two subtrees is greater that one.
Single Rotation
- Brian demonstrates how rotations are performed. They are necessary when one side of the tree is too heavy and needs rebalancing. Single rotations can take the form of either a right rotation or a left rotation.
Double Rotation
- A double rotation is necessary when the opposite child is heavy during a rotation. For example, if the execution of a right rotation causes the left side to be heavy, a left rotation should be performed first on the child node.
Exercise 9 Solution Part 1
- Brian begins walking through the solution to exercise 9. In this first part, he creates the Node class and implements the add() method which handles creating left and right child nodes.
Exercise 9 Solution Part 2
- Brian finishes the solution to exercise 9. He implements the balance() method in the Node class. He also looks at the left and right rotation code.
Hash Table
- Hash tables are key-value stores used to implement maps or sets. With hash tables, the key is used as the index for where to find the value in memory. This is done by passing the key through a hashing function which converts it to an addressable space. After introducing hash tables, Brian talks through some of the code from the hash table exercise.
Functional Programming 101
Functional Programming Concepts
- Brian explains the foundations of functional programming and talks about why using functional programming will help you create code that it’s more maintainable, composeable, and easier to reason about. He also talks about using higher order functions and how to avoid side effects.
Map Function
- Map is a higher order function that has similarities to forEach. It takes a function as a parameter and applies that function individually to each element in an array. It returns a new array of the values without modifying the original list.
Reduce Function
- The reduce function combines a list into a single meaningful value. It takes a reducer function as a parameters. Each time the reducer function is called, it is passed an accumulator, which is an the interim value, along with the current value from the list.
Filter Function
- The filter function takes a list of items and decides which items should stay in the list and which items should be removed by returning either true or false each time it is called. The result is a new list containing only the items that returned true.