Algorithms
Disclaimer: current page is not for educational purposes, it has a intention of notes for myself about algorithms.
Big O
Asymptotic runtime.
Time complexity
BigTheta
is a merge of BigO and BigOmega =>
the algorithm is BigTheta(N) if it is O(N) && BigOmega(N).
In industry BigO is close to BigTheta => the tightest description of the time.
The way to describe bigO for particular input:
Best case (not useful)
Worst case
expected case (useful to consider as worst, but sometimes.
ℹ️When you see a problem where number of elements is halved each time, it will be most likely runtime.
ℹ️ When recursive function makes multiple calls =often=>
Space complexity
To create a array n => O(n) space
To create two-dimentional array n*n => space
What affects: data structure size and call stack size.
Iteration over strings (Перебор строк)
Lexicographical order: (abc < acb) Strict definition:
For three chars 'a', 'b', 'c' the code to produce all combinations in lexicographical order is:
In more general case, when it is required to iterate over all strings with length n which consist of first m chars of alphabet. The task can be reformulated differently: Output all sequences with a length on n which consist of numbers from 0 to m.
Permutation
All sequences of integers from 1 to n, where each integer is used only once. Such sequence is called - permutation.
Array used
is needed to restrict having permutation with same integers. Output is:
Correct brace sequence
Lets consider a correct brace sequence from Math point of view. E.g. ((()))
, ()()()
, (())()
. One of implementations:
Also there is a well-known implementation of this algorithm with a stack.
Implementation of correct brace sequence using recursion
Binary search
time efficiency O(log(n)). (base of logarithm is 2, not 10.)
3 parts of successful binary search:
pre-processing. Sort if collection is not sorted.
Binary search. Using loop or recursion divide search space in half each comparison.
post-processing. Determine viable candidates in remaining space.
Template 1
Distinguishing Syntax:
Initial Condition:
left = 0, right = length-1
Termination:
left > right
Searching Left:
right = mid-1
Searching Right:
left = mid+1
Another template
Below template inspired by known article ⭐LINK
Suppose we have a search space. It could be an array, a range, etc. Usually it's sorted in ascending order. For most tasks, we can transform the requirement into the following generalized form:
Minimize k , s.t. condition(k) is True
The following code is the most generalised binary search template:
Breadth first search
Used to explore nodes and edges of the graph.
Time complexity O(Verticies + Edges).
Finding shortest path on unweighted graphs.
Depth first search (DFS)
Goes deep.
Dijkstra's Algorithm
The basic goal of the algorithm is to determine the shortest path between a starting node, and the rest of the graph. This is a greedy algorithm.
First explanation Shortest path from source to all vertices in given graph + code Really nice explanation of Dijkstra`s algorithm Really good article about algorithm + java implementation
Logic
Settled nodes are the ones with a known minimum distance from the source.
The unsettled nodes set gathers nodes that we can reach from the source, but we don't know the minimum distance from the starting node.
Here's a list of steps to follow in order to solve the SPP with Dijkstra:
Set distance to startNode to zero.
Set all other distances to an infinite value.
We add the startNode to the unsettled nodes set.
While the unsettled nodes set is not empty we:
Choose an evaluation node from the unsettled nodes set, the evaluation node should be the one with the lowest distance from the source.
Calculate new distances to direct neighbours by keeping the lowest distance at each evaluation.
Add neighbours that are not yet settled to the unsettled nodes set.
These steps can be aggregated into two stages, Initialisation and Evaluation.
Dynamic connectivity problem
Union find
This is an algorithm which answers a question whether two nodes are connected to each other (see dynamic connectivity problem).
Find query
check if two objects are in the same component
Union command
Replace components containing two objects with their union
Quick-find algorithm (eager approach)
algorithm | init | union | find |
quick-find | N | N (too slow) | 1 |
quick-union | N | N | N |
quick-union (weighted) | N | logN | logN |
Data structure:
Integer array
id[]
of size NInterpretation:
p
andq
are connected iff (if and only if) they have the same id
Find. Check if p
and q
have the same id.
Union. To merge components containing p
and q
change all entries whose id equals id[p] to id[q].
Quick-union (lazy approach)
Data structure:
Integer array
id[]
of size NInterpretation: id[i] is parent of i
Find. Check if p
and q
have the same root.
Union. To merge components containing p
and q
- set the id of p's root to the id of q's root. (e.g. union(3,4) - 3 goes under 4. The order is important)
Quick-union (weighted)
Modify quick-union to avoid tall trees
Keep track of size of each tree
Balance by linking root of smaller tree to root of larger tree
Depth of any node x
is at most lgN
(base 2 logarithm).
Quick-union with path compression
Percolation
Useful math
=> for BigO notation it is not important what is a base for logarithm
Explained tasks
Single number among others being twice
This is non optimal solution. The better is here.
Robot return to origin. Check that moves right, left, down, up have equal number and you return to the same initial point.
Jewels and stones. How many chars from one string are contained in another string.
Last updated