Complete Intro to Computer Science
Table of Contents
IntroductionBrian 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 SetupBrian 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.
Big O Time ComplexityBrian 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 OBrian 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 ComplexityBrian 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-OffsBrian 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.
Bubble SortBrian 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 PracticeBrian 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 SortBrian 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 PracticeBrian 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.
RecursionBrian 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 AdditionBrian 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: FactorialsBrian 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 SortBrian 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 PracticeBrian 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.
Quick SortBrian 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 PracticeBrian 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&ABrian 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.
Radix SortBrian 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 PracticeBrian 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 SearchBrian 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 PracticeBrian provides two short exercises of searching for student IDs to practice linear and binary searching and then live codes the solutions to the examples.
ArrayList PracticeBrian 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.
LinkedListBrian 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 PracticeBrian 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.
Binary Search TreeBrian 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 PracticeBrian 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 TreeBrian 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 ExerciseBrian 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 SolutionBrian live codes the solution to the Self Balancing AVL Tree exercise.
AVL Trees Q&ABrian 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 TraversalsBrian 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 PracticeBrian 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 TraversalsBrian 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 PracticeBrian provides a short exercise to practice building breadth-first tree traversals and then live solves the exercise.
Heap SortBrian 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 PracticeBrian 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
GraphsBrian 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 PracticeBrian 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.
PathfindingBrian 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 ExerciseStudents 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 neighborsBrian live codes the solution to the first half of the Pathfinding exercise part a.
Pathfinding Solution: b neighborsBrian 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.
TriesBrian 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 ExerciseStudents are instructed to construct a trie for the provided cities that returns the correct autocomplete suggestions.
Tries SolutionBrian live codes the solution to the tries exercise.
Other Data Structures
Bloom FiltersBrian 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.