tags : Computation and Computer Theory, Data Structures, Algorithm Problems, Recursion, Big Oh Notation, Problem solving Strategies in Algorithms

## Meta

- nlogn : we do n, logn amount of times.

## Search

### Binary search

- List must be sorted

#### Worst case

- In binary search, worst case is till we half it till we can’t half no more. i.e item not in list.
- So we need to find out “How many times we can
`half`

something util we get to`1`

”

⇒ $2_{k}n =1$ ⇒ $n=2_{k}$ ⇒ $g_{2}(n)=k$

- i.e we can
`half`

something`k`

times till we get`1`

.

#### About one-offs w binary search

- The algorithm is rather simple. But there’s a solid possibility of off by one errors with implementing Binary search.
- Things mostly differ based on how
`low`

and`high`

is defined- It changes the condition
- It changes what we return

- There can be different ways to calculate
`low`

and`high`

and all these do the same thing- eg. The pseudo-code in wikipedia differs from what’s there in CLRS, but they do the same exact thing.
- It’s just about knowing what you set for
`low`

and`high`

and then seeing that through the implementation of your algorithm. So you’ll be able to follow any implementation of binary search that way. - You can define this in terms of inclusive and exclusiveness.
- $[low,high)$ :
`low`

idx from the array,`high`

idx out of array.`high`

is`len(arr)-1`

- $[low,high]$ :
`low`

idx from the array,`high`

idx from the array.`high`

is`len(arr)`

- In both these cases, you can come up w an algorithm for binary search but how you calculate other variables will differ based on this thing.

- $[low,high)$ :

#### Integer overflow

- We need to be careful about our invariants.
- First,
`high`

and`low`

both need to be in the integer range that’s allowed. - Second, the usual way of calculating
`mid`

is`(high+low)/2`

which is susceptible to integer overflow. - So usually
`mid`

is calculated as`low + (high-low)/2`

which results in a integer that is in range and is mathematically the same as`(high+low)/2`

. This is something we need to do due to the limitations of our computers. As mentioned here, Nearly All Binary Searches and Mergesorts are broken

#### Resources

- Bitwise Binary Search: Elegant and Fast | orlp.net
- Beautiful Branchless Binary Search | Probably Dance

## Sorting

- If $X_{i}$ ≤ $X_{i+1}$ for the entire array, array is sorted.
- Largely two types, comparison based and non-comparison. (Lookup wikipedia). Me(a pleb) will mostly deal w comparison algorithms, non-comparison based include things like bucket sort, radix sort etc.
`Bubble, Selection and Insertion`

are aka`Quadratic Sorting algorithms`

because they take quadratic time.`stable`

: the stability of a sorting algorithm means if 2 elements in the input list are the same and then the list is sorted, the order of the 2 same elements will be preserved.

### Exchange based

#### Bubble sort

- Repeatedly swapping adjacent elements that are out of order
- At the end of 1st pass, you’ll have the max(arr) at the end of the array

### Selection based

#### Selection sort

#### Heapsort

- Good to understand before Quicksort

### Insertion based

- For scenarios where they need to merge 2 lists together
- Insertion sort is very fast for small arrays and it’s also better at using the hardware than bubblesort.

### Divide and Concur based

#### Quick sort

- In place sort
- Uses partitioning using pivot item
- Worst case: Reverse sorted and we pick pivot to be the smallest item.
- Time complexity: $(O(ngn)$ , can be $(O(n_{2})$ in worst case
- Implementation
- Partition func : Produces the pivot index and moves the items from one side to other
- Quicksort func: Calls partition func, gets the pivot, recalls itself

- If you apply quicksort to 2^20 random integers, at some point you’re sorting 2^17 8-integer subpartitions. Switching over to bubblesort for those subpartitions would be a nice optimization.
- Algo (TODO CHECK)
- Pick a pivot.
- Create 3 new lists
- all elements less than the pivot
- all elements greater than the pivot
- all elements equal to the pivot

- Recursively sort the first and second of these lists.
- Concatenate the list of smaller, equal, and larger values.

#### Merge sort

- For situations where you’re are getting in a piecemeal fashion. (eg. sorting a big file by loading chunks)
- Time complexity: $O(ngn)$ (Always), but involves copying of data unlike quicksort.

### Others

#### Topological sort

- https://github.com/python/cpython/blob/3.11/Lib/graphlib.py
- 7.17. Topological Sorting — Problem Solving with Algorithms and Data Structures 3rd edition

## Tree Traversal

- See Trees

## Graph

See Graphs

### Pathfinding

#### Meta

- Graph search algorithms work on
`weighted-directed`

graphs - They only understand the
`connectivity`

of the graph - Order
- CSS:
`TOP-RIGHT-BOTTOM-LEFT`

- Dir (differential direction, $(x,y)$)
- L: [-1,0]
- R: [1,0]
- T: [0,1]
- B: [0,-1]
- LT: [-1,1] (diagonals)
- LB: [-1,-1]
- RT: [1,1]
- RB: [1,-1]

- CSS: