AlgorithmsNotesForProfessionals.pdf
(
2688 KB
)
Pobierz
Algorithms
Algorithms
Notes for Professionals
Notes for Professionals
of professional hints and tricks
200+ pages
GoalKicker.com
Free Programming Books
Disclaimer
This is an unocial free book created for educational purposes and is
not aliated with ocial Algorithms group(s) or company(s).
All trademarks and registered trademarks are
the property of their respective owners
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: Graph
........................................................................................................................................................... 8
Section 3.1: Storing Graphs (Adjacency Matrix)
......................................................................................................... 8
Section 3.2: Introduction To Graph Theory
.............................................................................................................. 11
Section 3.3: Storing Graphs (Adjacency List)
........................................................................................................... 15
Section 3.4: Topological Sort
...................................................................................................................................... 17
Section 3.5: Detecting a cycle in a directed graph using Depth First Traversal
................................................... 18
Section 3.6: Thorup's algorithm
................................................................................................................................. 19
Chapter 4: Graph Traversals
............................................................................................................................... 21
Section 4.1: Depth First Search traversal function
................................................................................................... 21
Chapter 5: Dijkstra’s Algorithm
........................................................................................................................... 22
Section 5.1: Dijkstra's Shortest Path Algorithm
......................................................................................................... 22
Chapter 6: A* Pathfinding
....................................................................................................................................... 27
Section 6.1: Introduction to A*
..................................................................................................................................... 27
Section 6.2: A* Pathfinding through a maze with no obstacles
.............................................................................. 27
Section 6.3: Solving 8-puzzle problem using A* algorithm
...................................................................................... 34
Chapter 7: A* Pathfinding Algorithm
................................................................................................................ 37
Section 7.1: Simple Example of A* Pathfinding: A maze with no obstacles
............................................................ 37
Chapter 8: Dynamic Programming
.................................................................................................................... 44
Section 8.1: Edit Distance
............................................................................................................................................ 44
Section 8.2: Weighted Job Scheduling Algorithm
.................................................................................................... 44
Section 8.3: Longest Common Subsequence
........................................................................................................... 48
Section 8.4: Fibonacci Number
.................................................................................................................................. 49
Section 8.5: Longest Common Substring
.................................................................................................................. 50
Chapter 9: Kruskal's Algorithm
............................................................................................................................ 51
Section 9.1: Optimal, disjoint-set based implementation
......................................................................................... 51
Section 9.2: Simple, more detailed implementation
................................................................................................ 52
Section 9.3: Simple, disjoint-set based implementation
.......................................................................................... 52
Section 9.4: Simple, high level implementation
........................................................................................................ 52
Chapter 10: Greedy Algorithms
........................................................................................................................... 54
Section 10.1: Human Coding
..................................................................................................................................... 54
Section 10.2: Activity Selection Problem
.................................................................................................................... 57
Section 10.3: Change-making problem
..................................................................................................................... 59
Chapter 11: Applications of Greedy technique
............................................................................................. 61
Section 11.1: Oine Caching
........................................................................................................................................ 61
Section 11.2: Ticket automat
....................................................................................................................................... 69
Section 11.3: Interval Scheduling
................................................................................................................................. 72
Section 11.4: Minimizing Lateness
............................................................................................................................... 76
Chapter 12: Prim's Algorithm
................................................................................................................................. 80
Section 12.1: Introduction To Prim's Algorithm
.......................................................................................................... 80
Chapter 13: Bellman–Ford Algorithm
................................................................................................................ 88
Section 13.1: Single Source Shortest Path Algorithm (Given there is a negative cycle in a graph)
..................... 88
Section 13.2: Detecting Negative Cycle in a Graph
.................................................................................................. 91
Section 13.3: Why do we need to relax all the edges at most (V-1) times
............................................................. 93
Chapter 14: Line Algorithm
.................................................................................................................................... 96
Section 14.1: Bresenham Line Drawing Algorithm
.................................................................................................... 96
Chapter 15: Floyd-Warshall Algorithm
............................................................................................................. 99
Section 15.1: All Pair Shortest Path Algorithm
........................................................................................................... 99
Chapter 16: Catalan Number Algorithm
........................................................................................................ 102
Section 16.1: Catalan Number Algorithm Basic Information
................................................................................. 102
Chapter 17: Multithreaded Algorithms
........................................................................................................... 104
Section 17.1: Square matrix multiplication multithread
.......................................................................................... 104
Section 17.2: Multiplication matrix vector multithread
........................................................................................... 104
Section 17.3: merge-sort multithread
...................................................................................................................... 104
Chapter 18: Knuth Morris Pratt (KMP) Algorithm
..................................................................................... 106
Section 18.1: KMP-Example
....................................................................................................................................... 106
Chapter 19: Edit Distance Dynamic Algorithm
........................................................................................... 108
Section 19.1: Minimum Edits required to convert string 1 to string 2
.................................................................... 108
Chapter 20: Online algorithms
........................................................................................................................... 111
Section 20.1: Paging (Online Caching)
.................................................................................................................... 112
Chapter 21: Big-O Notation
.................................................................................................................................. 118
Section 21.1: A Simple Loop
...................................................................................................................................... 119
Section 21.2: A Nested Loop
..................................................................................................................................... 119
Section 21.3: O(log n) types of Algorithms
............................................................................................................. 120
Section 21.4: An O(log n) example
........................................................................................................................... 122
Chapter 22: Sorting
.................................................................................................................................................. 124
Section 22.1: Stability in Sorting
............................................................................................................................... 124
Chapter 23: Bubble Sort
........................................................................................................................................ 125
Section 23.1: Bubble Sort
.......................................................................................................................................... 125
Section 23.2: Implementation in C & C++
................................................................................................................ 125
Section 23.3: Implementation in C#
......................................................................................................................... 126
Section 23.4: Python Implementation
..................................................................................................................... 127
Section 23.5: Implementation in Java
..................................................................................................................... 128
Section 23.6: Implementation in Javascript
........................................................................................................... 128
Chapter 24: Merge Sort
........................................................................................................................................ 130
Section 24.1: Merge Sort Basics
............................................................................................................................... 130
Section 24.2: Merge Sort Implementation in Go
.................................................................................................... 131
Section 24.3: Merge Sort Implementation in C & C#
............................................................................................. 131
Section 24.4: Merge Sort Implementation in Java
................................................................................................ 133
Section 24.5: Merge Sort Implementation in Python
............................................................................................. 134
Section 24.6: Bottoms-up Java Implementation
................................................................................................... 135
Chapter 25: Insertion Sort
.................................................................................................................................... 137
Section 25.1: Haskell Implementation
...................................................................................................................... 137
Chapter 26: Bucket Sort
........................................................................................................................................ 138
Section 26.1: C# Implementation
............................................................................................................................. 138
Chapter 27: Quicksort
............................................................................................................................................ 139
Section 27.1: Quicksort Basics
.................................................................................................................................. 139
Section 27.2: Quicksort in Python
............................................................................................................................ 141
Section 27.3: Lomuto partition java implementation
............................................................................................ 141
Chapter 28: Counting Sort
................................................................................................................................... 143
Section 28.1: Counting Sort Basic Information
....................................................................................................... 143
Section 28.2: Psuedocode Implementation
............................................................................................................ 143
Chapter 29: Heap Sort
........................................................................................................................................... 145
Section 29.1: C# Implementation
............................................................................................................................. 145
Section 29.2: Heap Sort Basic Information
............................................................................................................. 145
Chapter 30: Cycle Sort
........................................................................................................................................... 147
Section 30.1: Pseudocode Implementation
............................................................................................................. 147
Chapter 31: Odd-Even Sort
.................................................................................................................................. 148
Section 31.1: Odd-Even Sort Basic Information
....................................................................................................... 148
Chapter 32: Selection Sort
................................................................................................................................... 151
Section 32.1: Elixir Implementation
.......................................................................................................................... 151
Section 32.2: Selection Sort Basic Information
...................................................................................................... 151
Section 32.3: Implementation of Selection sort in C#
............................................................................................ 153
Chapter 33: Trees
..................................................................................................................................................... 155
Section 33.1: Typical anary tree representation
..................................................................................................... 155
Section 33.2: Introduction
......................................................................................................................................... 155
Section 33.3: To check if two Binary trees are same or not
................................................................................. 156
Chapter 34: Binary Search Trees
..................................................................................................................... 159
Section 34.1: Binary Search Tree - Insertion (Python)
........................................................................................... 159
Section 34.2: Binary Search Tree - Deletion(C++)
................................................................................................. 161
Section 34.3: Lowest common ancestor in a BST
.................................................................................................. 162
Section 34.4: Binary Search Tree - Python
............................................................................................................. 163
Chapter 35: Check if a tree is BST or not
..................................................................................................... 165
Section 35.1: Algorithm to check if a given binary tree is BST
.............................................................................. 165
Section 35.2: If a given input tree follows Binary search tree property or not
................................................... 166
Chapter 36: Binary Tree traversals
................................................................................................................. 167
Section 36.1: Level Order traversal - Implementation
........................................................................................... 167
Section 36.2: Pre-order, Inorder and Post Order traversal of a Binary Tree
...................................................... 168
Chapter 37: Lowest common ancestor of a Binary Tree
..................................................................... 170
Section 37.1: Finding lowest common ancestor
..................................................................................................... 170
Chapter 38: Searching
............................................................................................................................................ 171
Section 38.1: Binary Search
...................................................................................................................................... 171
Section 38.2: Rabin Karp
.......................................................................................................................................... 172
Section 38.3: Analysis of Linear search (Worst, Average and Best Cases)
........................................................ 173
Section 38.4: Binary Search: On Sorted Numbers
................................................................................................. 175
Section 38.5: Linear search
...................................................................................................................................... 175
Chapter 39: Substring Search
............................................................................................................................ 177
Section 39.1: Introduction To Knuth-Morris-Pratt (KMP) Algorithm
..................................................................... 177
Section 39.2: Introduction to Rabin-Karp Algorithm
............................................................................................. 180
Section 39.3: Python Implementation of KMP algorithm
...................................................................................... 183
Section 39.4: KMP Algorithm in C
............................................................................................................................ 184
Chapter 40: Breadth-First Search
................................................................................................................... 187
Section 40.1: Finding the Shortest Path from Source to other Nodes
.................................................................. 187
Section 40.2: Finding Shortest Path from Source in a 2D graph
......................................................................... 193
Section 40.3: Connected Components Of Undirected Graph Using BFS
............................................................ 194
Chapter 41: Depth First Search
......................................................................................................................... 199
Section 41.1: Introduction To Depth-First Search
.................................................................................................... 199
Chapter 42: Hash Functions
................................................................................................................................ 204
Section 42.1: Hash codes for common types in C#
............................................................................................... 204
Section 42.2: Introduction to hash functions
.......................................................................................................... 205
Chapter 43: Travelling Salesman
.................................................................................................................... 207
Section 43.1: Brute Force Algorithm
........................................................................................................................ 207
Section 43.2: Dynamic Programming Algorithm
................................................................................................... 207
Chapter 44: Knapsack Problem
....................................................................................................................... 209
Section 44.1: Knapsack Problem Basics
.................................................................................................................. 209
Section 44.2: Solution Implemented in C#
.............................................................................................................. 209
Chapter 45: Equation Solving
............................................................................................................................ 211
Section 45.1: Linear Equation
................................................................................................................................... 211
Section 45.2: Non-Linear Equation
.......................................................................................................................... 213
Chapter 46: Longest Common Subsequence
............................................................................................. 217
Section 46.1: Longest Common Subsequence Explanation
.................................................................................. 217
Chapter 47: Longest Increasing Subsequence
......................................................................................... 222
Section 47.1: Longest Increasing Subsequence Basic Information
...................................................................... 222
Chapter 48: Check two strings are anagrams
.......................................................................................... 225
Section 48.1: Sample input and output
.................................................................................................................... 225
Section 48.2: Generic Code for Anagrams
............................................................................................................. 226
Chapter 49: Pascal's Triangle
............................................................................................................................ 228
Section 49.1: Pascal triangle in C
............................................................................................................................. 228
Chapter 50: Algo:- Print a m*n matrix in square wise
............................................................................ 229
Section 50.1: Sample Example
................................................................................................................................. 229
Section 50.2: Write the generic code
...................................................................................................................... 229
Chapter 51: Matrix Exponentiation
................................................................................................................... 230
Section 51.1: Matrix Exponentiation to Solve Example Problems
.......................................................................... 230
Chapter 52: Applications of Dynamic Programming
............................................................................. 234
Section 52.1: Fibonacci Numbers
............................................................................................................................. 234
Chapter 53: polynomial-time bounded algorithm for Minimum Vertex Cover
........................ 237
Section 53.1: Algorithm Pseudo Code
...................................................................................................................... 237
Chapter 54: Dynamic Time Warping
.............................................................................................................. 238
Section 54.1: Introduction To Dynamic Time Warping
.......................................................................................... 238
Chapter 55: Fast Fourier Transform
.............................................................................................................. 242
Section 55.1: Radix 2 FFT
.......................................................................................................................................... 242
Section 55.2: Radix 2 Inverse FFT
............................................................................................................................ 247
Appendix A: Pseudocode
....................................................................................................................................... 249
Section A.1: Variable aectations
............................................................................................................................ 249
Section A.2: Functions
............................................................................................................................................... 249
Credits
............................................................................................................................................................................ 250
You may also like
...................................................................................................................................................... 252
Plik z chomika:
Rivit
Inne pliki z tego folderu:
Elaine Rich - Automata, Computability and Complexity.pdf
(112238 KB)
HaskellNotesForProfessionals.pdf
(1943 KB)
MicrosoftSQLServerNotesForProfessionals.pdf
(2705 KB)
MATLABNotesForProfessionals.pdf
(2886 KB)
GitNotesForProfessionals.pdf
(2546 KB)
Inne foldery tego chomika:
Android
Filmy
Gry PC PSX + CRACKI
Muzyka
Programy
Zgłoś jeśli
naruszono regulamin