Algorithms Notes for Professionals

20

21

22

24

24

30

33

37

39

49

49

70

71

72

77

77

77

79

79

86

94

97

Chapter 13: A* Pathfinding Algorithm

...............................................................................................................

59

Section 13.1: Simple Example of A* Pathfinding: A maze with no obstacles

..........................................................

59

Chapter 14: Dynamic Programming

.................................................................................................................

66

...........................................................................................................................................

66

Section 14.1: Edit Distance

Section 14.2: Weighted Job Scheduling Algorithm

Section 14.3: Longest Common Subsequence

Section 14.4: Fibonacci Number

Section 14.5: Longest Common Substring

..................................................................................................

66

..........................................................................................................

.................................................................................................................................

................................................................................................................

Chapter 15: Applications of Dynamic Programming

................................................................................

73

Section 15.1: Fibonacci Numbers

Chapter 16: Kruskal's Algorithm

................................................................................................................................

73

..........................................................................................................................

76

Section 16.1: Optimal, disjoint-set based implementation

Section 16.2: Simple, more detailed implementation

Section 16.3: Simple, disjoint-set based implementation

Section 16.4: Simple, high level implementation

.......................................................................................

76

...............................................................................................

.........................................................................................

.......................................................................................................

Chapter 17: Greedy Algorithms

Section 17.1: Human Coding

Section 17.2: Activity Selection Problem

Section 17.3: Change-making problem

............................................................................................................................

.....................................................................................................................................

....................................................................................................................

82

.....................................................................................................................

84

Chapter 18: Applications of Greedy technique

............................................................................................

86

Section 18.1: Oine Caching

Section 18.2: Ticket automat

Section 18.3: Interval Scheduling

Section 18.4: Minimizing Lateness

.......................................................................................................................................

......................................................................................................................................

................................................................................................................................

............................................................................................................................

101

Chapter 19: Prim's Algorithm

..............................................................................................................................

105

Section 19.1: Introduction To Prim's Algorithm

.......................................................................................................

105

Chapter 20: Bellman–Ford Algorithm

............................................................................................................

113

Section 20.1: Single Source Shortest Path Algorithm (Given there is a negative cycle in a graph)

Section 20.2: Detecting Negative Cycle in a Graph

Section 20.3: Why do we need to relax all the edges at most (V-1) times

...............................................................................................

..........................................................

.................

113

116

118

Chapter 21: Line Algorithm

...................................................................................................................................

121

Section 21.1: Bresenham Line Drawing Algorithm

..................................................................................................

121

Chapter 22: Floyd-Warshall Algorithm

Section 22.1: All Pair Shortest Path Algorithm

Chapter 23: Catalan Number Algorithm

..........................................................................................................

........................................................................................................

.......................................................................................................

127

Section 23.1: Catalan Number Algorithm Basic Information

................................................................................

127

Chapter 24: Multithreaded Algorithms

.........................................................................................................

129

Section 24.1: Square matrix multiplication multithread

Section 24.2: Multiplication matrix vector multithread

Section 24.3: merge-sort multithread

.........................................................................................

129

..........................................................................................

.....................................................................................................................

124

124

129

129

Chapter 25: Knuth Morris Pratt (KMP) Algorithm

.....................................................................................

131

Section 25.1: KMP-Example

......................................................................................................................................

131

Chapter 26: Edit Distance Dynamic Algorithm

..........................................................................................

133

Section 26.1: Minimum Edits required to convert string 1 to string 2

...................................................................

133

Chapter 27: Online algorithms

...........................................................................................................................

136

Section 27.1: Paging (Online Caching)

....................................................................................................................

137

Chapter 28: Sorting

.................................................................................................................................................

143

Section 28.1: Stability in Sorting

...............................................................................................................................

143

144

144

145

146

147

149

150

Chapter 29: Bubble Sort

........................................................................................................................................

144

..........................................................................................................................................

Section 29.1: Bubble Sort

Section 29.2: Implementation in C & C++

Section 29.3: Implementation in C#

Section 29.4: Python Implementation

Section 29.5: Implementation in Java

Section 29.6: Implementation in Javascript

...............................................................................................................

........................................................................................................................

.....................................................................................................................

.....................................................................................................................

...........................................................................................................

147

Chapter 30: Merge Sort

.........................................................................................................................................

149

...............................................................................................................................

Section 30.1: Merge Sort Basics

Section 30.2: Merge Sort Implementation in Go

Section 30.3: Merge Sort Implementation in C & C#

Section 30.4: Merge Sort Implementation in Java

Section 30.5: Merge Sort Implementation in Python

Section 30.6: Bottoms-up Java Implementation

....................................................................................................

.............................................................................................

150

................................................................................................

152

.............................................................................................

153

...................................................................................................

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

Section 33.2: Quicksort in Python

Section 33.3: Lomuto partition java implementation

..................................................................................................................................

............................................................................................................................

158

160

.............................................................................................

160

Chapter 34: Counting Sort

...................................................................................................................................

162

Section 34.1: Counting Sort Basic Information

Section 34.2: Psuedocode Implementation

.......................................................................................................

162

............................................................................................................

162

Chapter 35: Heap Sort

...........................................................................................................................................

164

Section 35.1: C# Implementation

Section 35.2: Heap Sort Basic Information

.............................................................................................................................

164

.............................................................................................................

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

Section 38.2: Selection Sort Basic Information

Section 38.3: Implementation of Selection sort in C#

..........................................................................................................................

......................................................................................................

............................................................................................

172

Chapter 39: Searching

............................................................................................................................................

174

......................................................................................................................................

..........................................................................................................................................

Section 39.1: Binary Search

Section 39.2: Rabin Karp

Section 39.3: Analysis of Linear search (Worst, Average and Best Cases)

Section 39.4: Binary Search: On Sorted Numbers

Section 39.5: Linear search

Chapter 40: Substring Search

......................................................................................................................................

...........................................................................................................................

.................................................................................................

........................................................

176

Section 40.1: Introduction To Knuth-Morris-Pratt (KMP) Algorithm

Section 40.2: Introduction to Rabin-Karp Algorithm

Section 40.3: Python Implementation of KMP algorithm

Section 40.4: KMP Algorithm in C

Chapter 41: Breadth-First Search

.....................................................................

180

.............................................................................................

......................................................................................

............................................................................................................................

....................................................................................................................

170

170

174

175

178

178

180

183

186

187

190

208

210

210

214

214

Section 41.1: Finding the Shortest Path from Source to other Nodes

Section 41.2: Finding Shortest Path from Source in a 2D graph

Section 41.3: Connected Components Of Undirected Graph Using BFS

..................................................................

..........................................................................

190

196

.............................................................

197

Chapter 42: Depth First Search

........................................................................................................................

202

Section 42.1: Introduction To Depth-First Search

...................................................................................................

202

Chapter 43: Hash Functions

................................................................................................................................

207

Section 43.1: Hash codes for common types in C#

Section 43.2: Introduction to hash functions

...............................................................................................

207

..........................................................................................................

Chapter 44: Travelling Salesman

Section 44.1: Brute Force Algorithm

Section 44.2: Dynamic Programming Algorithm

....................................................................................................................

........................................................................................................................

...................................................................................................

210

Chapter 45: Knapsack Problem

........................................................................................................................

212

Section 45.1: Knapsack Problem Basics

Section 45.2: Solution Implemented in C#

..................................................................................................................

212

..............................................................................................................

212

Chapter 46: Equation Solving

Section 46.1: Linear Equation

Section 46.2: Non-Linear Equation

............................................................................................................................

...................................................................................................................................

..........................................................................................................................

216

Chapter 47: Longest Common Subsequence

............................................................................................

220

Section 47.1: Longest Common Subsequence Explanation

..................................................................................

220

Chapter 48: Longest Increasing Subsequence

.........................................................................................

225

Section 48.1: Longest Increasing Subsequence Basic Information

......................................................................

225

Chapter 49: Check two strings are anagrams

..........................................................................................

228

Section 49.1: Sample input and output

Section 49.2: Generic Code for Anagrams

....................................................................................................................

228

.............................................................................................................

229

Chapter 50: Pascal's Triangle

Section 50.1: Pascal triangle in C

............................................................................................................................

231

.............................................................................................................................

231

Chapter 51: Algo:- Print a m*n matrix in square wise

.............................................................................

232

Section 51.1: Sample Example

Section 51.2: Write the generic code

Chapter 52: Matrix Exponentiation

..................................................................................................................................

.......................................................................................................................

232

232

..................................................................................................................

233

Section 52.1: Matrix Exponentiation to Solve Example Problems

.........................................................................

233

Chapter 53: polynomial-time bounded algorithm for Minimum Vertex Cover

........................

237

Section 53.1: Algorithm Pseudo Code

Chapter 54: Dynamic Time Warping

......................................................................................................................

237

..............................................................................................................

238

Section 54.1: Introduction To Dynamic Time Warping

..........................................................................................

238

Chapter 55: Fast Fourier Transform

..............................................................................................................

242

Section 55.1: Radix 2 FFT

Section 55.2: Radix 2 Inverse FFT

..........................................................................................................................................

242

............................................................................................................................

247

Appendix A: Pseudocode

.......................................................................................................................................

249

Section A.1: Variable aectations

Section A.2: Functions

............................................................................................................................

249

...............................................................................................................................................

249

Credits

............................................................................................................................................................................

250

You may also like

......................................................................................................................................................

252

About

Please feel free to share this PDF with anyone for free,

latest version of this book can be downloaded from:

https://goalkicker.com/AlgorithmsBook

This Algorithms Notes for Professionals book is compiled from Stack Overflow

Documentation, the content is written by the beautiful people at Stack Overflow.

Text content is released under Creative Commons BY-SA, see credits at the end

of this book whom contributed to the various chapters. Images may be copyright

of their respective owners unless otherwise specified

This is an unofficial free book created for educational purposes and is not

affiliated with official Algorithms group(s) or company(s) nor Stack Overflow. All

trademarks and registered trademarks are the property of their respective

company owners

The information presented in this book is not guaranteed to be correct nor

accurate, use at your own risk

Please send feedback and corrections to [email protected]

GoalKicker.com – Algorithms Notes for Professionals

1

Chapter 1: Getting started with algorithms

Section 1.1: A sample algorithmic problem

An algorithmic problem is specified by describing the complete set of instances it must work on and of its output

after running on one of these instances. This distinction, between a problem and an instance of a problem, is

fundamental. The algorithmic problem known as sorting is defined as follows: [Skiena:2008:ADM:1410219]

Problem: Sorting

Input: A sequence of n keys, a_1, a_2, ..., a_n.

Output: The reordering of the input sequence such that a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

An instance of sorting might be an array of strings, such as { Haskell, Emacs } or a sequence of numbers such as

{ 154, 245, 1337 }.

Section 1.2: Getting Started with Simple Fizz Buzz Algorithm in

Swift

For those of you that are new to programming in Swift and those of you coming from different programming bases,

such as Python or Java, this article should be quite helpful. In this post, we will discuss a simple solution for

implementing swift algorithms.

Fizz Buzz

You may have seen Fizz Buzz written as Fizz Buzz, FizzBuzz, or Fizz-Buzz; they're all referring to the same thing. That

"thing" is the main topic of discussion today. First, what is FizzBuzz?

This is a common question that comes up in job interviews.

Imagine a series of a number from 1 to 10.

1 2 3 4 5 6 7 8 9 10

Fizz and Buzz refer to any number that's a multiple of 3 and 5 respectively. In other words, if a number is divisible

by 3, it is substituted with fizz; if a number is divisible by 5, it is substituted with buzz. If a number is simultaneously

a multiple of 3 AND 5, the number is replaced with "fizz buzz." In essence, it emulates the famous children game

"fizz buzz".

To work on this problem, open up Xcode to create a new playground and initialize an array like below:

// for example

let number = [1,2,3,4,5]

// here 3 is fizz and 5 is buzz

To find all the fizz and buzz, we must iterate through the array and check which numbers are fizz and which are

buzz. To do this, create a for loop to iterate through the array we have initialised:

for num in number {

// Body and calculation goes here

}

After this, we can simply use the "if else" condition and module operator in swift ie - % to locate the fizz and buzz

GoalKicker.com – Algorithms Notes for Professionals

2

for num in number {

if num % 3 == 0 {

print("\(num) fizz")

} else {

print(num)

}

}

Great! You can go to the debug console in Xcode playground to see the output. You will find that the "fizzes" have

been sorted out in your array.

For the Buzz part, we will use the same technique. Let's give it a try before scrolling through the article — you can

check your results against this article once you've finished doing this.

for num in number {

if num % 3 == 0 {

print("\(num) fizz")

} else if num % 5 == 0 {

print("\(num) buzz")

} else {

print(num)

}

}

Check the output!

It's rather straight forward — you divided the number by 3, fizz and divided the number by 5, buzz. Now, increase

the numbers in the array

let number = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

We increased the range of numbers from 1-10 to 1-15 in order to demonstrate the concept of a "fizz buzz." Since 15

is a multiple of both 3 and 5, the number should be replaced with "fizz buzz." Try for yourself and check the answer!

Here is the solution:

for num in number {

if num % 3 == 0 && num % 5 == 0 {

print("\(num) fizz buzz")

} else if num % 3 == 0 {

print("\(num) fizz")

} else if num % 5 == 0 {

print("\(num) buzz")

} else {

print(num)

}

}

Wait...it's not over though! The whole purpose of the algorithm is to customize the runtime correctly. Imagine if the

range increases from 1-15 to 1-100. The compiler will check each number to determine whether it is divisible by 3

or 5. It would then run through the numbers again to check if the numbers are divisible by 3 and 5. The code would

essentially have to run through each number in the array twice — it would have to runs the numbers by 3 first and

then run it by 5. To speed up the process, we can simply tell our code to divide the numbers by 15 directly.

Here is the final code:

for num in number {

GoalKicker.com – Algorithms Notes for Professionals

3

if num % 15 == 0 {

print("\(num) fizz buzz")

} else if num % 3 == 0 {

print("\(num) fizz")

} else if num % 5 == 0 {

print("\(num) buzz")

} else {

print(num)

}

}

As Simple as that, you can use any language of your choice and get started

Enjoy Coding

GoalKicker.com – Algorithms Notes for Professionals

4

Chapter 2: Algorithm Complexity

Section 2.1: Big-Theta notation

Unlike Big-O notation, which represents only upper bound of the running time for some algorithm, Big-Theta is a

tight bound; both upper and lower bound. Tight bound is more precise, but also more difficult to compute.

The Big-Theta notation is symmetric: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

An intuitive way to grasp it is that f(x) = Ө(g(x)) means that the graphs of f(x) and g(x) grow in the same rate, or

that the graphs 'behave' similarly for big enough values of x.

The full mat...