Complete Intro to Computer Science
Learning Paths:
Topics:
Table of Contents
Introduction
Introduction
Brian Holt introduces the course by providing a brief overview of the course website, diving into some personal history with computer science, and discussing some reasons someone would want to learn computer science. The main goal of this course is to provide students with methods of structured thinking and logic.
Code Setup
Brian walks through setting up the exercises for the course, how the course code is organized, and some of the features that will be used on CodeSandbox. The Github link for running a local setup is also provided in this segment.
Algorithm Analysis
Big O Time Complexity
Brian discusses and demonstrates using the Big O method to analyze the efficiency of algorithms without getting too detailed and the effect increasing the complexity of a function has on the run time. A student's question regarding best practice when squaring variables compared to using constants is also covered in this segment.
Why Use Big O
Brian discusses how to easier determine the appropriate Big O for a process and demonstrates some practical applications of Big O including a comment system with a filtering ability. The key to determining the appropriate amount of Big O is getting as much context of the algorithm as possible.
Spatial Complexity
Brian discusses spatial complexity as how much storage space is required for an algorithm to complete and the different types including: linear, logarithmic, constant, and quadratic. Student questions regarding if network transfer is considered spatial complexity, how this applies to functional programming, and what's driving these constraints are also covered in this segment.
Big O Trade-Offs
Brian discusses the importance of being able to talk about the trade offs when deciding the amount of complexity to allow an algorithm. Some guiding principles when deciding the "better" Big O amount are provided and discussed in this segment. A student's question regarding how to best handle scaling problems is also covered in this segment.
Iterative Sorts
Bubble Sort
Brian discusses the bubble sorting algorithm which compares two items that are alongside each other in an array and swaps them if out of order. The computational complexity of the bubble sort algorithm will grow exponentially with larger arrays while the spatial complexity stays constant.
Bubble Sort Practice
Brian provides a short exercise to practice and visualize bubble sorting an array of numbers and then live codes the solution. A student's question regarding if the function's if check is intentionally going out of bounds is also covered in this segment.
Insertion Sort
Brian discusses insertion sort which will continually shift numbers over in the array until they reach their appropriate location. The worst, best, and average case scenarios for using this sort type are also discussed in this segment.
Insertion Sort Practice
Brian provides a short exercise to practice and visualize insertion sorting an array of numbers and then live codes the solution. Examples with larger arrays are also provided in this segment to better visually demonstrate how insertion sorts an array.
Recursive Sorts
Recursion
Brian discusses recursive functions as functions that call upon themselves, the basic mechanics, when recursive functions are useful, and provides an example using the Fibonacci sequence. Student's questions regarding if the map function is recursive, what happens if the max value is infinity, and what the purpose of list parameter in the example is are also covered in this segment.
Recursion Practice: Nested Addition
Brian provides a short exercise to practice recursion with a nested addition example and then live codes the solution. A student's question regarding the time complexity of the recursion solution is also covered in this segment.
Recursion Practice: Factorials
Brian provides a short exercise to practice recursion with a factorials example and then live codes the solution. This is example is fairly similar to the fibonacci example, but is little different to help solidify writing recursion functions. Students questions regarding how to conceptualize a recursive function and if it is correct to think of recursion like a promise are also covered in this segment.
Merge Sort
Brian discussion applying recursion to sort a list with merge sorting, walks through sorting a simple array, and provides a visual example. Recursion sorting will break an array down into smaller parts until the length is one or zero, which means it is already sorted.
Merge Sort Practice
Brian discusses the Big O and spatial complexity of merge sorting an array, provides a short exercise to practice merge sorting, and live codes the solution to the example. Every case of using merge sorting is the best, worst, and average as the array will always be broken down to lists of one.
Merge Sort Q&A
Brian answers student's questions regarding why left and right are being concatenated and what the policy for using built in JavaScript methods. Questions also covered in this segment include: if merge can be made recursive and if the solution could be completed in one function call.
Quick Sort
Brian discusses sorting arrays using quick sort, the Big O, spatial complexity, and possible variations of quick sort including a memory efficient version and quiicksort3. Quick sort will choose a pivot point, put values larger and smaller than the pivot into seperate arrays, return the arrays with lengths zero or one, and repeat until the array is sorted.
Quick Sort Practice
Brian provides a short exercise to practice quick sorting an array and live codes the example's solution. A student's question regarding what happens if there are duplicates in the arrays is also covered in this segment.
Quick Sort Q&A
Brian answers students questions regarding an error involving missing the - 1 in nums.length -1, if overwriting the variables would improve the memory, how to use a for of loop to solve the example, and walks through of the time complexity of this code. Student questions regarding how to decide what the log(n) is, if it makes sense to choose pivots outside the data set, and if choosing the perfect pivot is worth it are also covered in this segment.
Non-Comparison Sorts
Radix Sort
Brian discusses a non comparison sorting called radix sort, a walk through of an example array, and the Big O of this sorting method. Radix sorting will sort the array values into buckets for however many places there are in the largest number. Some starting helper functions for the radix sorting practice is also provided in this segment.
Radix Sort Practice
Brian provides a short exercise to practice radix sorting and then live codes the solution to the example with visual sorting snapshots. Student questions regarding what the constant mod is in the getDigit function and if the getLongestNumber function defeats the purpose of the entire sort are also covered in this segment.
Binary Search
Binary Search
Brian discusses searching for a particular element in an array using a binary search algorithm to keep cutting the array in half until the correct value is found. Unlike a linear search, a binary search method will only work if the array is already sorted. A student's question regarding if a binary search is best done recursively is also covered in this segment.
Binary Search Practice
Brian provides two short exercises of searching for student IDs to practice linear and binary searching and then live codes the solutions to the examples.
Lists
ArrayList
Brian discusses the ArrayList data structure and how to implement an array using just objects. JavaScript arrays are set normal arrays and there is no choice beyond that. No matter how big the ArrayList is, array lookups take the same amount of time.
ArrayList Practice
Brian provides a short exercise to practice implementing an object with ArrayList and then live codes the solution. Student questions regarding what to do if the index is not found, could the delete method be reused for pop, and if the ArrayList should have a peak function.
LinkedList
Brian discusses the LinkedList data structure which is composed of nodes that point to the next node in the list. Since the LinkedList data structure is not sequential in memory additions and deletions are easy, but look ups become more difficult.
LinkedList Practice
Brian provides a short exercise to practice implementing an object with LinkedList and then live codes the solution. A student's question regarding the index -1 in _find(index) is also covered in this segment.
Trees
Binary Search Tree
Brian disscusses binary search trees as a way to structure data, how to do a look up, add, delete, and the worst case for a binary search tree. Binary search trees are all ordered by value, so whenever you insert a new value, it will be inserted in a sorted fashion. Student's questions regarding if there can be duplicate elements and what the root of the tree is are also covered in this segment.
Binary Search Tree Practice
Brian provides a short exercise to practice building a binary search tree and then live codes the solution. A visual example of a binary search tree and a discussion of the max depth of a tree is also covered in this segment.
Self Balancing AVL Tree
Brian disscusses AVL trees which have a self balancing mechanism built into the tree to avoid the problem of binary search trees easily getting out of balance. Single and double rotations of a search tree are also discussed and visualized in this segment.
Self Balancing AVL Tree Exercise
Brian helps set up the AVL tree exercise by live coding a base Tree class and Node class. Students are then instructed to create and balance an AVL with rotations.
Self Balancing AVL Tree Solution
Brian live codes the solution to the Self Balancing AVL Tree exercise.
AVL Trees Q&A
Brian answers student questions regarding where to use AVL trees, what happens during rotations, and a more detailed explanation of height are covered in this segment.
Depth First Tree Traversals
Brian discusses depth-first tree traversals which are an essential part of storing data and are optimized to be searchable. How to serialize the tree into a flat data structure is also discussed in this segment.
Depth First Tree Traversals Practice
Brian provides a short exercise to practice building depth-first tree traversals using recursive methods and then live codes the solution. A student's question regarding a walkthrough of a three node tree is also covered in this segment.
Breadth First Tree Traversals
Brian discusses breadth-first tree traversals, provides a visual representation and a brief walkthrough of how a breadth-first tree traversal are arranged. Breadth-first isn't recursive processing of subtrees like depth-first but is instead processed one layer at a time.
Breadth First Tree Traversals Practice
Brian provides a short exercise to practice building breadth-first tree traversals and then live solves the exercise.
Heap Sort
Brian discusses a heap which is an array that represents a tree data structure and has to be sorted in a particular way to represent that tree. How to heapify, deque, and sort array items is also covered in this segment.
Heap Sort Practice
Brian provides a short exercise to practice implementing a heap, dequeuing, and sorting the array. A live solve of this practice exercise is also provided in this segment.
Applying Tree Algorithms
Graphs
Brian discusses using graphs as a data structure and modeling relations between items and walks through a example of Facebook's social graph. Student questions regarding what to do with duplicates and how to limit the amount of loops when you don't know the user to stop at are also covered in this segment.
Graphs Practice
Brian provides a short exercise to practice implementing graphs and then live codes the solution. Student questions regarding the complexity of graphs and if using the max heap for the traversals would be a more efficient option.
Pathfinding
Brian discusses using a pathfinding algorithm in order to find the path of least resistance between two points. An overview of how Dijkstra's algorithm is used for pathfinding is also covered in this segment.
Pathfinding Exercise
Students are instructed to find the shortest points between the twos while avoiding the one walls. It is recommended to complete the 4x4 maze before starting the more complicated 6x6 maze. A student's question on why pathfinding is useful is also covered in this segment.
Pathfinding Solution: a neighbors
Brian live codes the solution to the first half of the Pathfinding exercise part a.
Pathfinding Solution: b neighbors
Brian live codes the solution to the second half of the Pathfinding exercise part b. A student's question regarding how to go about solving this type of problem at the beginning of your computer science journey is also covered in this segment.
Tries
Brian discusses tries as a type of search tree optimised for locating specific keys from within a set. The example used in this segment is a list of autocomplete suggestions.
Tries Exercise
Students are instructed to construct a trie for the provided cities that returns the correct autocomplete suggestions.
Tries Solution
Brian live codes the solution to the tries exercise.
Other Data Structures
Bloom Filters
Brian discusses bloom filters which are an interesting data structure which are designed to tell you quickly and efficiently if an item is in a set. When you add more items to a bloom filter, you'll increase your false positive rate which can be mitigated by having a larger array.
Bloom Practice
Brian provides a short exercise to practice implementing bloom filters and then live codes the solution. A students question regarding if JavaScript would dynamically allocate for you is also covered in this segment.
