Cory Althoff - The Self-Taught Computer Scientist

1 Cover

2 Title Page The Self-Taught Computer Scientist The beginner’s guide to data structures & algorithms Cory Althoff

3 Introduction What You Will Learn Who Is This Book For? Self-Taught Success Stories Getting Started Sticking with It

4 I: Introduction to Algorithms 1 What Is an Algorithm? Analyzing Algorithms Constant Time Logarithmic Time Linear Time Log-Linear Time Quadratic Time Cubic Time Exponential Time Best-Case vs. Worst-Case Complexity Space Complexity Why Is This Important? Vocabulary Challenge 2 Recursion When to Use Recursion Vocabulary Challenge 3 Search Algorithms Linear Search When to Use a Linear Search Binary Search When to Use a Binary Search Searching for Characters Vocabulary Challenge 4 Sorting Algorithms Bubble Sort When to Use Bubble Sort Insertion Sort When to Use Insertion Sort Merge Sort When to Use Merge Sort Sorting Algorithms in Python Vocabulary Challenge 5 String Algorithms Anagram Detection Palindrome Detection Last Digit Caesar Cipher Vocabulary Challenge 6 Math Binary Bitwise Operators FizzBuzz Greatest Common Factor Euclid's Algorithm Primes Vocabulary Challenge 7 Self-Taught Inspiration: Margaret Hamilton

5 II: Data Structures 8 What Is a Data Structure? Vocabulary Challenge 9 Arrays Array Performance Creating an Array Moving Zeros Combining Two Lists Finding the Duplicates in a List Finding the Intersection of Two Lists Vocabulary Challenge 10 Linked Lists Linked List Performance Create a Linked List Search a Linked List Removing a Node from a Linked List Finding a Linked List Cycle Vocabulary Challenges 11 Stacks When to Use Stacks Creating a Stack Using Stacks to Reverse Strings Min Stack Stacked Parentheses Vocabulary Challenges 12 Queues When to Use Queues Creating a Queue Python's Built-In Queue Class Create a Queue Using Two Stacks Vocabulary Challenge 13 Hash Tables When to Use Hash Tables Characters in a String Two Sum Vocabulary Challenge 14 Binary Trees When to Use Trees Creating a Binary Tree Breadth-First Tree Traversal More Tree Traversals Invert a Binary Tree Vocabulary Challenges 15 Binary Heaps When to Use Heaps Creating a Heap Connecting Ropes with Minimal Cost Vocabulary Challenge 16 Graphs When to Use Graphs Creating a Graph Dijkstra's Algorithm Vocabulary Challenge 17 Self-Taught Inspiration: Elon Musk 18 Next Steps What’s Next? Climbing the Freelance Ladder How to Get an Interview How to Prepare for a Technical Interview Additional Resources Final Thoughts

6 Index

7 Copyright

8 Dedication

9 About the Author

10 About the Technical Editor

11 Acknowledgments

12 End User License Agreement

1 Chapter 1 Figure 1.1 Constant complexity Figure 1.2 Logarithmic complexity Figure 1.3 Linear complexity Figure 1.4 Log-linear complexity Figure 1.5 Quadratic complexity Figure 1.6 Big O complexity chart

2 Chapter 3Figure 3.1 Sorted data set for a binary searchFigure 3.2 A binary search first locates the middle number.Figure 3.3 The next step in a binary search eliminates the half of the data ...Figure 3.4 A binary search then finds the middle number again.Figure 3.5 Our binary search found our number.Figure 3.6 Exponential notation versus logarithmic notationFigure 3.7 ASCII chart

3 Chapter 4Figure 4.1 The first part of a merge sort

4 Chapter 5Figure 5.1 You use modulo arithmetic when you tell time.Figure 5.2 Eight hours after 9 is 5.

5 Chapter 6Figure 6.1 The place values for the number 1,452 in base 10Figure 6.2 The powers of 10 used in the place values in base 10Figure 6.3 The powers of 2 used in the place values in base 2

6 Chapter 9Figure 9.1 An example of data in an arrayFigure 9.2 Array operation run timesFigure 9.3 An array stored in a computer's memoryFigure 9.4 Adding data to an array often means changing many memory location...

7 Chapter 10Figure 10.1 A linked list is a chain of nodes.Figure 10.2 A linked list does not need to store nodes in consecutive memory...Figure 10.3 Pointers map the nodes of a linked list.Figure 10.4 Inserting an element into a linked list requires adjusting two p...Figure 10.5 A doubly linked list has pointers that go in two directions.Figure 10.6 A circular linked list points from the end back to the head.Figure 10.7 Linked list operation run timesFigure 10.8 To remove a node, change the previous node's pointer.Figure 10.9 Reversing a linked list

8 Chapter 11Figure 11.1 Data can be pushed on a stack or popped from it.Figure 11.2 Stack operation run timesFigure 11.3 If you pop off the characters of super, you get repus.

9 Chapter 12Figure 12.1 In a queue, you add items to the rear and remove them from the f...Figure 12.2 The primary operations of queues are enqueueing and dequeueing....Figure 12.3 Queue operation run timesFigure 12.4 When there is one item in your queue, it is both the front and t...Figure 12.5 Now the node with 1 in it is the front, and the node with 2 in i...Figure 12.6 The node with 1 in it is the front, and the node with 3 in it is...Figure 12.7 When you dequeue the 1, the front changes to the node with 2 in ...Figure 12.8 When you dequeue again, there is only one item left, so it is bo...Figure 12.9 Now your queue is empty.

10 Chapter 13Figure 13.1 A hash table stores key-value pairs in an array.Figure 13.2 To store 86 in the hash table, you perform modulo by the number ...Figure 13.3 To store 90 in the hash table, you perform modulo by the number ...Figure 13.4 Your hash table after adding all the numbersFigure 13.5 Hash table operation run times

11 Chapter 14Figure 14.1 An example of a tree data structureFigure 14.2 A tree with a root node, parent nodes, child nodes, and edgesFigure 14.3 A path through a treeFigure 14.4 In a binary tree, a parent node can have only two child nodes.Figure 14.5 An example of a binary search treeFigure 14.6 A simple tree showing the root node, A, and its descendantsFigure 14.7 Binary search trees operation run timesFigure 14.8 An example of folders in a treeFigure 14.9 The document object modelFigure 14.10 A tree for evaluating a mathematical expressionFigure 14.11 A binary tree with five nodesFigure 14.12 Levels in a binary treeFigure 14.13 A book represented as a treeFigure 14.14 A postorder tree traversalFigure 14.15 An in-order tree traversal

12 Chapter 15Figure 15.1 You create a binary heap using a binary tree.Figure 15.2 A max heap has the highest priority node as the root.Figure 15.3 A min heap has the lowest priority node as the root.Figure 15.4 The result of heapifying an arrayFigure 15.5 Swapping values to balance a heapFigure 15.6 Swapping D and T is the first step to balance this he...Figure 15.7 The left side of the heap was already balanced.Figure 15.8 Balancing the tree at the next levelFigure 15.9 C is now the root node in your binary heap.Figure 15.10 The R node trickles down the tree as long as it has a larger va...Figure 15.11 A balanced heapFigure 15.12 An array with keys at indexes based on their position in the tr...Figure 15.13 The right child of the root is at index 2.

13 Chapter 16Figure 16.1 A graph contains vertices, edges, payloads, and weight.Figure 16.2 A directed graph moves in a specific direction.Figure 16.3 An undirected graph can move in either direction.Figure 16.4 A complete graph has connections among all vertices.Figure 16.5 An incomplete graph has some connected vertices.Figure 16.6 A graph path follows a specific sequence.Figure 16.7 An example of a graph that contains a cycleFigure 16.8 A graph with four verticesFigure 16.9 An adjacency matrix of the graph in Figure 16.8Figure 16.10 Graphs can represent 3D shapes.Figure 16.11 A graph with four verticesFigure 16.12 Set the path to the starting vertex to zero and the other paths...Figure 16.13 What the data structures in your algorithm look like when it fi...Figure 16.14 The data structures after visiting vertex AFigure 16.15 The data structures after visiting vertex BFigure 16.16 The data structures after visiting vertex CFigure 16.17 The data structures after visiting vertex D