Tiêu đề Algorithm notes for professionals(257pgs).pdf ✅

Contents About ................................................................................................................................................................................... 1 Chapter 1: Getting started with algorithms .................................................................................................... 2 Section 1.1: A sample algorithmic problem ................................................................................................................. 2 Section 1.2: Getting Started with Simple Fizz Buzz Algorithm in Swift ...................................................................... 2 Chapter 2: Algorithm Complexity ......................................................................................................................... 5 Section 2.1: Big-Theta notation .................................................................................................................................... 5 Section 2.2: Comparison of the asymptotic notations .............................................................................................. 6 Section 2.3: Big-Omega Notation ................................................................................................................................ 6 Chapter 3: Big-O Notation ........................................................................................................................................ 8 Section 3.1: A Simple Loop ............................................................................................................................................ 9 Section 3.2: A Nested Loop ........................................................................................................................................... 9 Section 3.3: O(log n) types of Algorithms ................................................................................................................. 10 Section 3.4: An O(log n) example .............................................................................................................................. 12 Chapter 4: Trees ......................................................................................................................................................... 14 Section 4.1: Typical anary tree representation ......................................................................................................... 14 Section 4.2: Introduction ............................................................................................................................................. 14 Section 4.3: To check if two Binary trees are same or not ..................................................................................... 15 Chapter 5: Binary Search Trees .......................................................................................................................... 18 Section 5.1: Binary Search Tree - Insertion (Python) ............................................................................................... 18 Section 5.2: Binary Search Tree - Deletion(C++) ..................................................................................................... 20 Section 5.3: Lowest common ancestor in a BST ...................................................................................................... 21 Section 5.4: Binary Search Tree - Python ................................................................................................................. 22 Chapter 6: Check if a tree is BST or not .......................................................................................................... 24 Section 6.1: Algorithm to check if a given binary tree is BST .................................................................................. 24 Section 6.2: If a given input tree follows Binary search tree property or not ....................................................... 25 Chapter 7: Binary Tree traversals ..................................................................................................................... 26 Section 7.1: Level Order traversal - Implementation ............................................................................................... 26 Section 7.2: Pre-order, Inorder and Post Order traversal of a Binary Tree .......................................................... 27 Chapter 8: Lowest common ancestor of a Binary Tree ......................................................................... 29 Section 8.1: Finding lowest common ancestor ......................................................................................................... 29 Chapter 9: Graph ......................................................................................................................................................... 30 Section 9.1: Storing Graphs (Adjacency Matrix) ....................................................................................................... 30 Section 9.2: Introduction To Graph Theory .............................................................................................................. 33 Section 9.3: Storing Graphs (Adjacency List) ........................................................................................................... 37 Section 9.4: Topological Sort ..................................................................................................................................... 39 Section 9.5: Detecting a cycle in a directed graph using Depth First Traversal .................................................. 40 Section 9.6: Thorup's algorithm ................................................................................................................................. 41 Chapter 10: Graph Traversals .............................................................................................................................. 43 Section 10.1: Depth First Search traversal function .................................................................................................. 43 Chapter 11: Dijkstra’s Algorithm .......................................................................................................................... 44 Section 11.1: Dijkstra's Shortest Path Algorithm ........................................................................................................ 44 Chapter 12: A* Pathfinding ..................................................................................................................................... 49 Section 12.1: Introduction to A* ................................................................................................................................... 49 Section 12.2: A* Pathfinding through a maze with no obstacles ............................................................................. 49 Section 12.3: Solving 8-puzzle problem using A* algorithm .................................................................................... 56

Chapter 29: Bubble Sort ........................................................................................................................................ 144 Section 29.1: Bubble Sort .......................................................................................................................................... 144 Section 29.2: Implementation in C & C++ ............................................................................................................... 144 Section 29.3: Implementation in C# ........................................................................................................................ 145 Section 29.4: Python Implementation ..................................................................................................................... 146 Section 29.5: Implementation in Java ..................................................................................................................... 147 Section 29.6: Implementation in Javascript ........................................................................................................... 147 Chapter 30: Merge Sort ......................................................................................................................................... 149 Section 30.1: Merge Sort Basics ............................................................................................................................... 149 Section 30.2: Merge Sort Implementation in Go .................................................................................................... 150 Section 30.3: Merge Sort Implementation in C & C# ............................................................................................. 150 Section 30.4: Merge Sort Implementation in Java ................................................................................................ 152 Section 30.5: Merge Sort Implementation in Python ............................................................................................. 153 Section 30.6: Bottoms-up Java Implementation ................................................................................................... 154 Chapter 31: Insertion Sort ..................................................................................................................................... 156 Section 31.1: Haskell Implementation ....................................................................................................................... 156 Chapter 32: Bucket Sort ........................................................................................................................................ 157 Section 32.1: C# Implementation ............................................................................................................................. 157 Chapter 33: Quicksort ............................................................................................................................................. 158 Section 33.1: Quicksort Basics .................................................................................................................................. 158 Section 33.2: Quicksort in Python ............................................................................................................................ 160 Section 33.3: Lomuto partition java implementation ............................................................................................. 160 Chapter 34: Counting Sort ................................................................................................................................... 162 Section 34.1: Counting Sort Basic Information ....................................................................................................... 162 Section 34.2: Psuedocode Implementation ............................................................................................................ 162 Chapter 35: Heap Sort ........................................................................................................................................... 164 Section 35.1: C# Implementation ............................................................................................................................. 164 Section 35.2: Heap Sort Basic Information ............................................................................................................. 164 Chapter 36: Cycle Sort ........................................................................................................................................... 166 Section 36.1: Pseudocode Implementation ............................................................................................................. 166 Chapter 37: Odd-Even Sort .................................................................................................................................. 167 Section 37.1: Odd-Even Sort Basic Information ...................................................................................................... 167 Chapter 38: Selection Sort ................................................................................................................................... 170 Section 38.1: Elixir Implementation .......................................................................................................................... 170 Section 38.2: Selection Sort Basic Information ...................................................................................................... 170 Section 38.3: Implementation of Selection sort in C# ............................................................................................ 172 Chapter 39: Searching ............................................................................................................................................ 174 Section 39.1: Binary Search ...................................................................................................................................... 174 Section 39.2: Rabin Karp .......................................................................................................................................... 175 Section 39.3: Analysis of Linear search (Worst, Average and Best Cases) ........................................................ 176 Section 39.4: Binary Search: On Sorted Numbers ................................................................................................. 178 Section 39.5: Linear search ...................................................................................................................................... 178 Chapter 40: Substring Search ........................................................................................................................... 180 Section 40.1: Introduction To Knuth-Morris-Pratt (KMP) Algorithm ..................................................................... 180 Section 40.2: Introduction to Rabin-Karp Algorithm ............................................................................................. 183 Section 40.3: Python Implementation of KMP algorithm ...................................................................................... 186 Section 40.4: KMP Algorithm in C ............................................................................................................................ 187 Chapter 41: Breadth-First Search .................................................................................................................... 190