Skip to content

arnabm14/Algorithms-Codec

Repository files navigation

Algorithms

[MergeSort.c]------ MergeSort an array of n elements.

[freqBinRec.c]----Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(logn).

[rotClockMin.c]----A sorted array is rotated clockwise at some unknown point, find the minimum element in it.

[missAPBin.c]------ Given an array that represents elements of arithmetic progression in order. One element is missing in the progression, find the missing number.

[bitonic.c]-------- A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing. A Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing. Find bitonic point in a bitonic sequence.

[invPairs.c])------- ( How Close a Data is To Being Sorted? ) Apply Merge Sort to count inversion pairs in an array. Two elements a[i] and a[j] form an inversion pair if a[i] > a[j] and i < j. Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

[sumBin.c]--------- Given a sorted array and a number X, search two elements of array s.t. their sum is X.

[twoDimArr.c]----- Apply Binary Search on 2D NxM array (A) having numbers stored in non-deceasing order under row-major scanning. Hint: k-th element = A[k/M][k % M] 4

[median.c]--------- Median of two sorted arrays: There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays (i.e. array of length 2n). The complexity should be O(log(n))

[BFS.cpp]---------- Breadth First Search of a Graph using STL.

[DFS.cpp]---------- Depth First Search of a Graph using STL.

[node_level.cpp]--- Finding number of nodes at a given level 'x' in an undirected graph ( BFS )

[unreach.cpp] ----- Nodes not reachable from a source node 'x' using DFS (can be done using BFS)

[kruskal.cpp] ----- Given a weighted undirected graph find the sum of weights of edges of a Minimum Spanning Tree.(Union function used here has O(n^2) time complexity)

[countSort.c] ----- Given an array of digits, sort them with time complexity O(n).

[permute.cpp] ----- Print all permutations of a given string.

[nQueen.cpp] -------- The N-Queen Problem where n is less than a given value(assumed n < 100).

[nQueenAllSolns.cpp]----- Printing all possible solutions of the N-Queen problem where n is less than a given value(assumed n < 100).

[ratMaze.cpp]---------- A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down.[In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination.]

[primPQ.cpp]------ Prim’s algorithm using priority_queue in STL

[radixLexiSort.cpp]----- Arrange a list of words (each of equal length) using dictionary sorting strategy (Hint : Radix Sort).

[dijkstra.cpp]-------------- Print Shortest Path and Distance using Dijkstra (using Multiset).

[quickSort.c]------------ Apply quicksort on a 2D M*N matrix of numbers so that the numbers are sorted in a row-major fashion in the 2D matrix (without auxiliary array).