/*
* Problem : Given 2 number x and y where 2 <= x <= 10^100 and 2 <= y<= 10^6.
* Algorithm : Long division Method.
* Variables:
* dividend - Each element of dividend aray represent a digit of x. dividend[0] = Most significant Digit
* divisor - y
* size - No. of digits in x
* If x is divisible by y then return true else return false.
*/
#define len 1000000
bool divide(int dividend[], int divisor, int size) {
int rem, d, index;
rem = d = index = 0;
while(true) {
d = rem;
while( d < divisor && index < size ) {
d = d*10 + dividend[index++];
}
rem = d % divisor;
if(index >= size) {
if(rem == 0) {
return true;
}else {
return false;
}
}
}
}
Monday, 7 April 2014
Program to check whether x ( 2 <= x <= 10^100) is divisible by y ( 2 <= y <= 10^6) .
Monday, 14 October 2013
Quick select: Select Kth smallest element in an array of size n in O(n) time.
#include <iostream>
using namespace std;
inline void swap(int arr[],int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int randint(int len) {
srand(time(NULL));
//srand((unsigned)rdtsc());
return (rand() % (len) + 0);
}
int randomPartition(int arr[],int start , int end) {
int pivotPos = randint(end-start) + start;
swap(arr,start,pivotPos);
int pivot = arr[start], i = start+1, j= start+1;
pivotPos = start;
for(;j<=end; j++) {
if(arr[j] < pivot) {
swap(arr,i,j);
i++;
}
}
swap(arr,pivotPos,i-1);
pivotPos = i-1;
return pivotPos;
}
int Rselect(int arr[],int start, int end, int k) {
int pivotPos = randomPartition(arr,start,end);
if(pivotPos == k)
return arr[k];
else if(pivotPos < k)
return Rselect(arr,pivotPos+1,end,k);
else
return Rselect(arr,start,pivotPos-1,k);
}
int main() {
int arr[] = {40,1,10,70,2,5,30,9,8,6};
int size = sizeof arr/sizeof arr[0];
cout<<"Kth greatest = "<<Rselect(arr,0,size-1,3);
system("pause");
return 0;
}
Knuth-Morris-Pratt Pattern Matching Algorithm
//============================================================================
// Name : KMP.cpp
// Author : Varun Sharma
// Complexity : O(P) pre-processing O(T) kmpMatching, O(P+T).
// Copyright :
// Description : Knuth-Morris-Pratt pattern matching Algo.
//============================================================================
/*
PRE-PROCESSING
==============
Construct an array kmp[] that stores the no. of positions by which one should move the pattern in case of mismatch at character i.
Kmp[i] = Length of longest prefix in pattern[0…i] which is also suffix of pattern[0…i].
Pattern : AABAAC
Pattern[0..4] = AABAA.
Longest prefix and suffix in Patern[0…4] = AA hence Kmp[4] = 2
String A A B A A C
KMP 0 1 0 1 2 0
1. Create an array kmp[] and set kmp[0] = 0 and set len =0.
2. For i=1 to patternLength.
len will keep track of prefix, while i will scan entire string from left to right.
3. Check if char at i matches char at len, pattern[i] == pattern[len]
a. If match occurs increment len (len++) and set kmp[i] = len and increment I (i++).
b. If no match, then
i. If len = 0, i.e. at beginning of pattern, then set kmp[i] = 0 and increment i
ii. Else shift pattern by kmp[len-1], do not increment I and repeat step 3.
KMP MATCHING
============
1. Preprocessing : Build the preprocessing Array.
2. Use t for scanning Text and p for scanning pattern, t=p=0.
3. If text[t] == patter[p] then increment p and t (p++, t++)
a. If p == pattern length, then pattern occurs in string and print.
4. Else There is a mismatch.
a. If p==0 i.e. at first character in pattern, then increment t and start matching from first character in pattern.
b. Else use pre-processing array to determine matching position (p)
set p = kmp[p-1].
*/
#include <iostream>
using namespace std;
void preprocessing(int *kmp, string pattern, int pLen) {
kmp[0] = 0;
int len,i;
for(i=1,len=0; i<pLen; ) {
//Check if char at i matches char at len.
if(pattern[i] == pattern[len]) {
//If match occurs increment len and set kmp[i] = len.
len++;
kmp[i] = len;
i++;
}
else {
//If characters don't match and len = 0, i.e. at very first character.
//Then set kmp[i] = 0 and simply increment i.
if(!len) { kmp[i] = 0; i++;}
else
//else repeat matching step by shifting pattern by kmp[len-1].
len = kmp[len-1];
}
}
}
void kmpMatching(string text , string pattern) {
int tLen, pLen , t, p;
tLen = text.length();
pLen = pattern.length();
//if length of text is greater than length of pattern then return.
if(tLen < pLen) {
cout<<"Pattern Doesn't exist";
return;
}
//Build kmp array as part of preprocessing step.
int *kmp = new int[pLen];
preprocessing(kmp,pattern,pattern.length());
//p is use to traverse in pattern.
//t is use to traverse in text.
for(t = p =0; t<tLen; ) {
//If character at p in pattern
//and character at t in text
//match then increment p and t.
if(text[t] == pattern[p]) {
t++; p++;
//if p = pattern length then pattern occurs.
if(p==pLen) {
cout<<"n Pattern Occurs at : "<<t-pLen+1<<" position";
p = 0;
}
}else {
//if p = 0, i.e. very first character in pattern.
//Then increment text and start matching from pattern[p].
if(!p) t++;
//else if p!=-0 then set p = kmp[p-1] and start matchng from pattern[p].
else p = kmp[p-1];
}
}
}
int main() {
string text = "I google about google.";
string pattern = "google";
kmpMatching(text,pattern);
return 0;
}
Sunday, 6 October 2013
Implementation of Bellman Ford Algorithm.
/*
ALGORITHM (Borrowed from wiki)
==============================
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices and edges,
// and fills two arrays (distance and predecessor) with shortest-path information
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"
BELLMAN FORD VS DIJKSTRA
========================
1. Bellman Ford runs in O(VE) time where as Dijkstra can be optimized to run in O(VlogV) time with use of Fibonacci heap.
2. Bellman ford works on negative weight graphs as well where as Dijkstra doesn’t allow negative weight edges.
3. Dijkstra algorithm is highly centric and is not very distributive. Dijkstra is good if all data is stored on one machine’s main memory.
COMPLEXITY
==========
O(VE)
*/
public void bellmanFord(int sourceVertex) {
int i,j,cost;
Vertex source,target;
boolean negativeCycle = false;
int distance[] = new int[totalVertices];
// Step 1: initialize graph
//Set distance of each vertex from source to INF and distance source = 0
for(i=0; i<totalVertices; i++)
distance[i] = INF;
distance[sourceVertex] = 0;
// Step 2: relax edges repeatedly
//Relax each edge by 1,2...|V|-1
//Complexity : O(|V|).
//Longest cycle free path between 2 vertices can have atmost |v|-1 edges.
for(i=0; i<totalVertices-1; i++) {
//Explore each edge. Complexity : O(|E|)
for(j=0; j<totalVertices; j++) {
source = vertices[j];
for(Edge e : source.edges) {
target = e.Target;
cost = distance[source.vertexId] + e.weight;
//If current distance is greater than new reachable distance.
//then update distance.
if(distance[target.vertexId] > cost) {
distance[target.vertexId] = cost;
}
}
}
}
// Step 3: check for negative-weight cycles
//Detect negative weight cycles by relaxing to |V| edges.
//If there is a negative cycle in the path then simply report it.
for(j=0; j<totalVertices; j++) {
source = vertices[j];
for(Edge e : source.edges) {
target = e.Target;
cost = distance[source.vertexId] + e.weight;
if(distance[target.vertexId] > cost) {
negativeCycle = true;
System.out.println("NEGATIVE WEIGHT CYCLE IN GRAPH");
break;
}
}
}
}
Implementation of Dijkstra, single source shortest path.
/*
ALGORITHM
=========
1. Initialize distance of each vertex from source as INF, and distance back to source = 0.
2. For I = 0 to Total vertices Repeat step 3 to 4.
3. Find minimum distance vertex, which is not yet explored and put it to explored set.
4. Find all vertices reachable from current vertex and update its distance if it is less than distance[currentVertex] + edge weight.
COMPLEXITY
==========
Time : O(|V||E|) .
Time complexity can be improved by using Fibonacci heap to retrieve minimum value.
Time : O(|E| + |V|log|V|).
LIMITATIONS
===========
• Dijkstra algorithm can be used for graphs with all positive weight edges only.
• Dijkstra is not lacks distribute property.
*/
public int minimum(int distance[],boolean visited[]) {
int min = INF,minNode = -1;
int i;
for(i=0; i<totalVertices; i++) {
if(distance[i] <= min && visited[i] == false) {
min = distance[i];
minNode = i;
}
}
return minNode;
}
public void dijkstra(int sourceVertex) {
System.out.println("nnDIJKSTRA");
int i,j,minV,cost;
Vertex minVertex,target;
//Distance array to store distance of each vertex from sourcevertex
int distance[] = new int[totalVertices];
boolean visited[] = new boolean[totalVertices];
//Initialize distance array with INF, and distance[source] = 0.
for(i=0; i<totalVertices; i++) {
visited[i] = false;
distance[i] = INF;
}
distance[sourceVertex] = 0;
for(i=0; i<totalVertices; i++) {
//Get minimum vertex out of all unexplored vertex
//and put it to explored set.
minV = minimum(distance,visited);
visited[minV] = true;
if(distance[minV] == INF)
continue;
minVertex = vertices[minV];
//compute the distance, if it is less than current distance then update it.
for(j=0; j<minVertex.edges.size(); j++) {
cost = distance[minV] + minVertex.edges.get(j).weight;
target = minVertex.edges.get(j).Target;
if(cost < distance[target.vertexId]) {
distance[target.vertexId] = cost;
}
}
}
}
Topological Sort.
/*
PRE-CONDITION
=============
Graph should be Acyclic and Directed (DAG).
APPLICATIONS
============
• Ordering of formula cell evaluation when recomputing formula values in spreadsheets,
• Logic synthesis.
• Determining the order of compilation tasks to perform in makefiles.
• Data serialization
• Resolving symbol dependencies in linkers.
• It is also used to decide in which order to load tables with foreign keys in databases.
ALGORITHM
=========
1. Put all the vertices in unexplored set.
2. While unexplored set is not empty, Repeat step 3 to 5
3. Select a vertex from unexplored set and perform DFS taking this as source,
4. Remove vertex in DFS path from unexplored set and put them in explored set.
5. Print the last node in DFS exploration (sink node).
*/
public void printSinkNodeDFS(Vertex source, boolean visited[]) {
//Move the vertex to explored set.
visited[source.vertexId] = true;
for(int i=0; i<source.edges.size(); i++) {
//Get all the vertices reachable from current vertex and present in unexplored set.
Vertex target = source.edges.get(i).Target;
if(!visited[target.vertexId])
printSinkNodeDFS(target, visited);
}
//When there are no more unexplored vertices reachable from current node.
//Process the current node which is now the sink node.
System.out.print(" " + source.vertexId);
}
public void topologicalSort() {
System.out.println("nnTopological Sort");
int i;
//Initially each vertex is in unexplored set.
boolean visited[] = new boolean[totalVertices];
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Scan all vertices in unexplored set and perform DFS with first unscanned vertex as source.
//Move vertices from unexplored to explored set.
//Repeat until no vertex is present in unexplored set.
for(i=0; i<totalVertices; i++) {
if(!visited[i]) {
printSinkNodeDFS(vertices[i],visited);
}
}
}
Friday, 4 October 2013
Depth First Search
/*
TIME COMPLEXITY :
O(|v| + |E|).
APPLICATIONS OF DFS
Finding strongly connected components in a graph (Kosaraju Algorithm).
Topological Sorting.
Solving Maze.
*/
public void recursiveDFS(Vertex sourceVertex,boolean visited[]) {
//Process the top vertex from stack and put it to explored set of vertices.
visited[sourceVertex.vertexId] = true;
System.out.println(sourceVertex.vertexId);
for(int i=0; i<sourceVertex.edges.size(); i++) {
//Push all not visited vertices reachable from process vertex
//one by one and aggressively search to deeper levels.
//backtrack when no more path can be taken and
//process all other vertices reachable from processed vertex
Vertex target = sourceVertex.edges.get(i).Target;
if(!visited[target.vertexId]) {
recursiveDFS(target,visited);
}
}
}
public void DFS(int sourceVertex) {
System.out.println("DFS Traversal");
int i;
//Initially put all vertices in unexplored set.
boolean visited[] = new boolean[totalVertices];
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Push source vertex in stack.
recursiveDFS(vertices[sourceVertex],visited);
}
Breadth First Search in a Graph.
/*
ALGORITHM
Enqueue the root node
Dequeue a node and examine it
If the element sought is found in this node, quit the search and return a result.
Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
If the queue is not empty, repeat from Step 2.
COMPLEXITY
BFS is very first and runs in linear time O(|V| + |E|) since each vertex and edge is explored once in worst case.
APPLICATIONS
Finding shortest path between 2 nodes in an undirected graph.
Checking if a graph is bipartite
Ford Fulkerson method for computing maximum flow in a network.
Serialization/Deserialization of a binary tree.
Finding all nodes within one connected components.
*/
public void BFS(int sourceVertex) {
System.out.println("BFS Traversal");
int i,targetId;
ArrayList<Vertex> queue = new ArrayList<>();
boolean visited[] = new boolean[totalVertices];
//Put all the vertices to unexplored set of vertices, initially.
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Put source vertex to explored vertices set.
visited[sourceVertex] = true;
queue.add(vertices[sourceVertex]);
while(!queue.isEmpty()) {
//Remove the very first vertex from the queue.
Vertex vertex = queue.get(0);
queue.remove(0);
//Process the removed vertex.
System.out.println(vertex.vertexId);
for(i=0; i<vertex.edges.size(); i++) {
//Get all the vertices reachable from processed vertex and add them to queue.
//put the processed vertex to explored set of vertices, so that its not explored again.
targetId = vertex.edges.get(i).Target.vertexId;
if(!visited[targetId]) {
queue.add(vertex.edges.get(i).Target);
visited[targetId] = true;
}
}
}
}
Adjacency List Implementation
/*
* Demo Vertex class contains only vertexId.
* Can be extended to keep other details.
*/
public class Vertex {
int vertexId;
ArrayList<Edge> edges ;
public Vertex(int id) {
vertexId = id;
edges = new ArrayList<>();
}
public void addEdge(Edge e) {
edges.add(e);
}
}
public class Edge {
Vertex Target;
int weight;
public Edge(Vertex Target, int weight) {
this.Target = Target;
this.weight = weight;
}
}
public class Graph {
/*
* @vertices, ArrayList of all vertices in a graph.
* @directed, boolean variable to store if graph is directed/undirected
* @totalVertices, Total number of vertices in a graph.
*/
Vertex vertices[];
boolean directed;
int totalVertices;
/*
* @param directed , boolean variable to keep if graph is directed.
* @param totalVertices, total number of vertices in a graph.
*/
public Graph(int totalVertices, boolean directed) {
this.totalVertices = totalVertices;
this.directed = directed;
vertices = new Vertex[totalVertices];
for(int i=0; i<totalVertices; i++)
vertices[i] = null;
}
/*
* @param target @param source, check if source and target vertex already present (!=null).
* if source/target vertex not present in graph then create it.
* Else add weighted edge from source to target vertex.
*/
public void addVertex(int source, int target, int weight) {
if(vertices[source] == null) {
vertices[source] = new Vertex(source);
}
if(vertices[target] == null) {
vertices[target] = new Vertex(target);
}
Vertex sourceVertex = vertices[source];
Vertex targetVertex = vertices[target];
sourceVertex.addEdge(new Edge(targetVertex,weight));
if(!directed) {
targetVertex.addEdge(new Edge(sourceVertex,weight));
}
}
}
Graph Introduction.
GRAPH
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
Wednesday, 25 September 2013
Parity Checker
#include <iostream>
using namespace std;
int setParity(int n)
{
int number = 1;
number = number<<8 ;
return (n|number);
}
bool isParitySet(int n)
{
int number = 128;
if(number && n)
return true;
else
return false;
}
int countOnes(int n)
{
int number = 1;
int count = 0;
for(int i=0; i<7; i++)
{
if(number & n)
{
count++;
}
number = number<<1;
}
return count;
}
int main()
{
int n = 2;
if(countOnes(n) % 2 == 0)
{
if(isParitySet(n))
{
n = n ^ 128;;
}
cout<<n;
}
else
{
cout<<"INVALLID NUMBER";
}
system("pause");
}
Monday, 23 September 2013
Longest Increasing Sub-sequence.
/*
Guess
=====
If including element i forms maximum length increasing sequence.
Sub-problem
===========
Prefix of input string X, X[:i] for all i < n.
Recurrence
==========
LIS(i) = 1 + max(LIS(j)) for all j < i and arr[i] > arr[j].
Running Time
============
For string of length n.
No. of sub-problems = O(n).
Time/subprolem = O(n) (check all j's less than i)
Running Time = O(n2).
*/
#include <iostream>
using namespace std;
#define MAX 100
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
int size = sizeof arr/sizeof arr[0];
int DP[MAX];
int DP1[MAX];
int findMax(int a[], int n) {
int maxVal = a[0];
for(int i=1; i<=n; i++)
if(maxVal < a[i])
maxVal = a[i];
return maxVal;
}
//Bottom Up Approach.
int LIS() {
int i,j,maxVal;
//Every element is a Sequence of length 1.
for(i=0; i<size; i++)
DP[i] = 1;
for(i=1; i<size; i++) {
for(j=0; j<i; j++) {
if(arr[i] > arr[j]) {
DP[i] = max(DP[i] , DP[j] + 1);
}
}
}
//Pick Maximum of all LIS
maxVal = findMax(DP,size-1);
return maxVal;
}
//Top Down Approach.
int LISTopDown(int i) {
int maxVal;
if(i==0)
return 1;
if(DP1[i]) {
return DP1[i];
}
for(int j=0; j<i; j++) {
if(arr[j] < arr[i])
if(LISTopDown(j)+1 > DP1[i])
DP1[i] = LISTopDown(j)+1;
}
maxVal = findMax(DP1,i);
return maxVal;
}
int main() {
printf("%d",LIS());
printf("\n%d",LISTopDown(size-1));
return 0;
}
Steps of Dynamic Programming.
Steps of Dynamic Programming
- Define Sub problems
Break a problem into sub-problems.Usually this is the tough part, identifying sub problems is half job done. - Guess Part of solution.Guess a solution of the sub-problem and the trick is don't just try any guess, try them all.
- Recurrence Relation.
Most important step.Once you have identified the sub-problems, the recurrence relation will be trivial. - Recurse + MemoizeStep-4 and step-5 will follow once completed first 3 steps.
- Solve original Problem
Use solution to sub-problems to solve the original problem.
Running Time
Running Time = No. of Sub-problems . Time/sub-problem
Eg.
consider worked out example for Edit Distance Problem.
Given two strings X and Y and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.
Sub-problem:
==========
Suffix of X => X[i:]
Suffix of Y => Y[j:]
Considering length of X (|X|) = m and length of Y(|Y|) = n.
Total No. of Sub-problems = O(|X||Y|) = O(mn).
Guess
=====
From current position 3 decisions can be taken,
Replace X[i] -> Y[j] and advance both i and j.
Insert Y[j] and advance j.
Delete X[i] and advance i.
Recurrence
========
At current position select the minimum cost operation, out of all 3 operations.
DP(i,j) = min( REPLACE_COST(X[i],Y[j]) + DP(i+1,j+1) , INSERT_COST(Y[j]) + DP(i,j+1), COST_DELETE(X[i] ) + DP(i+1,j))
Solve Original Problem
================
DP(m,n) = Minimum cost.
Running Time
=========
No. of Subproblems = O(mn)
Time/Subproblem = O(1).
Running Time = O(mn).
Sunday, 22 September 2013
What is Dynamic Programming?
Dynamic
programming is a method for solving complex problems by breaking them down into
simpler subproblems.
Dynamic
programming takes advantage of the fact that while solving a problem many of
the sub-problems are encountered and solved multiple times.
If we store the solution of this sub-problem (Memo-ize)
then no need of solving the sub-problem again, instead we refer to the memory
location where the solution of the sub-problem is stored and get the solution.
Dynamic
programming solves each sub-problem only once (the very first time), next time
the same problem can be looked up in the memory.
A Naïve solution
often ignores this fact and solves the sub-problem each time it is encountered.
Dynamic
programming can be applied to problems exhibiting 2 properties:
- Overlapping Sub problemsA
recursive algorithm solving the problem should solve the same subproblems over
and over, rather than generating new subproblems.For example, consider recursive algorithm for generating Fibonacci Numbers.Fi+2 = Fi+1 + Fi
F5 = F4 + F3 , F6 = F5 + F4Here F4 is solved in both F5 and F6. - Optimal SubstructureSolution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems.
Dynamic
Programming algorithms are used for optimization problem, (eg. Finding shortest
path, minimum cost of multiplying matrices etc) where we need to maximize or
minimize certain behaviour.
Dynamic
programming is kind of exhaustive search, an intelligent brute force that examines
all possible ways to solve the problem and pick the best solution.
Dynamic
Programming can solve a problem in 2 ways:
- Memoization/Top-Down Approach:A problem is divided into sub-problem, and solution of each sub-problem is searched in look up table. If solution already exist then it is returned else the sub-problem is computed and the result is stored in the lookup table.Initially lookup table is initialized with NULL.
- Tabulation/Bottom Up Approachsolve the sub-problems first and then combine the solution of these sub-problems stored in lookup table to solve the problem. Solution to bigger and bigger sub-problems is generated iteratively and ultimately solution to the original problem is obtained.
Tuesday, 3 September 2013
Pascal Triangle.
/*
* ALGORITHM : Dynamic Programming.
* Input size of triangle n.
* Allocate a 2-D array of size nxn.
* Recurrence relation C(n,k) = C(n-1,k-1) + C(n-1,k)
* Use 2-D matrix to store C(n,k) at arr[i][j].
* Time complexity O(n2) and O(n) extra space.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define CLR(a) memset(a,0,sizeof a)
using namespace std;
void printSpaces(int sp)
{
int i,j;
printf("\n");
for(i=0; i<sp; i++)
printf(" ");
}
void binomialCoefficient(int n)
{
int i,j;
int arr[n+1][n+1];
CLR(arr);
for(i=0; i<=n;i++)
{
for(j=0;j<= n ;j++)
{
if( j ==0 || i == j)
arr[i][j] = 1;
else
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
for(i=0;i<=n;i++)
{
printSpaces(n-i);
for(j=0;j<=i;j++)
printf("%d ",arr[i][j]);
}
}
int main()
{
int n;
while(true)
{
scanf("%d",&n);
if(n <= 0)
break;
binomialCoefficient(n);
}
}
/*
OUTPUT
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
*/
Monday, 2 September 2013
MAX XOR
/*
* Given an array A of unsigned 32-bit ints, choose two in-bounds indices i, j so as to maximize the value of A[i] ^ A[j], where ^ is the bitwise XOR (exclusive OR) operator.
* If there are multiple possible answers, print any one.
* Example Input:
* 4 2 0 13 49
* Output:
* 3 4
* Explanation: 13 ^ 49 is 60, 13 and 49 are positioned at indexes 3 and 4. Printing "4 3" would have been equally valid.
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(arr.length^2) time, O(1) space.
* Hard: Sub-quadratic complexity. An O(k*arr.length) time algorithm is possible. It is OK to use some extra space.
*/
#include <iostream>
using namespace std;
class node
{
int val;
bool isLeaf;
node *left;
node *right;
public:
node()
{
val = 0;
isLeaf = false;
left = NULL;
right = NULL;
}
void setVal(int n)
{
val = n;
}
int getVal()
{
return val;
}
void setLeftChild(node *ptr)
{
left = ptr;
}
void setRightChild(node *ptr)
{
right = ptr;
}
node* getLeftChild()
{
return left;
}
node* getRightChild()
{
return right;
}
void setIsLeaf(bool b)
{
isLeaf = b;
}
bool getIsLeaf()
{
return isLeaf;
}
};
class Tree
{
node *root;
int heightOfTree ;
public:
Tree()
{
root = new node();
root->setVal(99);
heightOfTree = 31;
}
int getMSBPosition()
{
return 0;
}
void insertNode(node* ptr, int n, int pos)
{
if(pos>=0)
{
int getBit = (1<<pos) & n;
node* newNode;
if(getBit)
{
if(ptr->getRightChild() == NULL)
{
newNode = new node();
newNode->setVal(1);
ptr->setRightChild(newNode);
}
if(pos == 0)
{
node* leafNode = new node();
newNode->setIsLeaf(true);
leafNode->setVal(n);
newNode->setLeftChild(leafNode);
}
else
insertNode(ptr->getRightChild(),n,pos-1);
}
else
{
if(ptr->getLeftChild() == NULL)
{
newNode = new node();
newNode->setVal(0);
ptr->setLeftChild(newNode);
}
if(pos == 0)
{
node* leafNode = new node();
leafNode->setVal(n);
newNode->setIsLeaf(true);
newNode->setLeftChild(leafNode);
}
else
insertNode(ptr->getLeftChild(),n,pos-1);
}
}
}
void insert(int n)
{
insertNode(root,n,heightOfTree);
}
int findMax(node* ptr1, node* ptr2)
{
if(ptr1->getIsLeaf() == false)
{
int n01 = 0;
int n10 = 0;
bool pathTaken = false;
if(ptr1->getLeftChild() != NULL && ptr2->getRightChild() != NULL)
{
n01 = findMax(ptr1->getLeftChild(),ptr2->getRightChild());
pathTaken = true;
}
if(ptr1->getRightChild() != NULL && ptr2->getLeftChild() != NULL)
{
n10 = findMax(ptr1->getRightChild(),ptr2->getLeftChild());
pathTaken = true;
}
if(!pathTaken)
{
if(ptr1->getLeftChild() && ptr2->getLeftChild())
n01 = findMax(ptr1->getLeftChild(),ptr2->getLeftChild());
else
n10 = findMax(ptr1->getRightChild(),ptr2->getRightChild());
}
return n01>n10?n01 : n10;
}
else
{
return ptr1->getLeftChild()->getVal() ^ ptr2->getLeftChild()->getVal();
}
}
int findMaxValue()
{
return findMax(root,root);
}
};
int maxValue(int *arr,int n)
{
int max = 0;
for(int i=0; i<n-1; i++)
{
for(int j=0; j<n; j++)
{
if(max < (arr[i]^arr[j]))
max = (arr[i]^arr[j]);
}
}
return max;
}
int main()
{
int numberOfElements;
cout<<"\nNUMBER OF ELEMENTS : ";
cin>>numberOfElements;
Tree t ;
int *arr = new int[numberOfElements];
for(int i=0; i<numberOfElements;i++)
{
cin>>arr[i];
t.insert(arr[i]);
}
cout<<"\nEASY = "<<maxValue(arr,numberOfElements);
cout<<"\nHARD = "<<t.findMaxValue();
}
FILL BITS
/*
* Consider a new bitwise binary operator that we will denote as x $ y. The result of this operator is that the set bits of x "flood outwards" y bits to both the left and the right.
* More precisely, the i-th bit (the least significant bit is considered to be the 0-th) of x $ y will be 1 if and only if x has any bit whose value is 1 and whose position differs by at most y from i (it can differ in either direction).
*
* Write a program that given unsigned ints x and y, computes x $ y.
* Example Inputs:
* 8 2
* 8 4
* 17 1
* Outputs (respectively):
* 62
* 255
* 59
* Explanation:
* In the first case, 8 is 0000..00001000 in binary. The operation causes the only set bit in the number to spread 2 positions in each direction, with a final result of 111110 (original bit underlined), which is 62 in decimal.
* In the second case, we spread the same bit 4 positions in each direction. This results in 4 1s to the left of the original bit's position. All 3 available positions to the right of the original bit's position are filled (a 4th would normally be filled, but we have reached the end of the number). The final number is 11111111, the value of which is 255.
* In the third case, 17 is 10001 in binary, and spreading the 1s in each direction by 1 gives 111011, which is 59 in decimal.
*
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Moderate: O(k*y) time.
* Moderate: O(y) time.
* Hard: O(log(y)) time.
*/
#include <iostream>
using namespace std;
int getFillBitsMODERATE(int x,int y)
{
int mask = x;
for(int i=1; i<=y; i++)
mask |= mask<<1 | mask >> 1;
return mask;
}
int getFillBitsHARD(int x, int y)
{
int mask = x;
do
{
if(y%2)
{
mask |= mask<<1 | mask >>1;
y--;
}
y/=2;
mask |= mask<<y | mask >>y;
}while(y>0);
return mask;
}
int main()
{
int x = 8;
int y = 2;
int testCases;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cout<<"\n\nENTER NUMBERS : ";
cin>>x>>y;
cout<<"\nEASY : "<<getFillBitsMODERATE(x,y);
cout<<"\nHARD : "<<getFillBitsHARD(x,y);
}
}
RANGE OPERATION
/*
* Let us define A(m, n) = m & (m+1) & ... & (n-1) & n, where & is the bitwise AND operation.
* Write a program that, given 64-bit unsigned longs m and n, computes A(m, n).
* Example Inputs:
* 49 54
* 2 2
* 2 3
* Outputs (respectively):
* 48
* 2
* 2
* Explanation:
* A(49, 54) = 49 & 50 & 51 & 52 & 53 & 54 = 48
* A(2, 2) = 2. If m = n, A(m, n) = m = n.
* A(2, 3) = 2 & 3 = 2
* 3
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(n - m) time. Consider that since m and n can be any 64-bit numbers, this could be
* huge.
* Moderate-Hard: O(k) time.
* Hard: O(log(k)) time.
*/
#include <iostream>
using namespace std;
int RangeOperationEASY(long long int m,long long int n)
{
long long int result = n;
n--;
for(;n>=m; n--)
{
result &= n;
}
return result;
}
long long int getNextHighestPower(long long int diff)
{
long long int pow = 0;
while(true)
{
if(diff > (1<<pow))
pow++;
else
return pow;
}
}
long long int getNextHighestPowerlogn(long long int diff)
{
diff--;
diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff |= diff >> 32;
diff++;
return diff;
}
long long int RangeOperationHARD(long long int m, long long int n)
{
long long int result = m & n;
long long int diff = n-m+1;
long long int mask = ~(getNextHighestPowerlogn(diff)-1);
return result & mask;
}
int main()
{
long long int m;
long long int n;
int testCases;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>m>>n;
cout<<"\nEASY : "<<RangeOperationEASY(m,n);
cout<<"\nHARD : "<<RangeOperationHARD(m,n)<<endl;
}
}
COUNT BITS
/*
* Given a 64-bit signed number, count the number of bits that are set to 1.
* Bonus: In addition to the obvious approach, continue exploring till you find other efficient approaches.
*
* Example Inputs:
* 0
* -1
* 14
* Outputs (respectively):
* 0
* 64
* 3
*
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(k) time.
* Moderate: O(number of bits whose value is 1) time.
* Very Hard: O(log(k)) time
*/
#include <iostream>
using namespace std;
inline bool isSet(long long int n,int i)
{
long long int x = 1;
x <<=i;
if(x&n)
return true;
return false;
}
int countBitsEASY(long long int n)
{
int size = sizeof(n)*8;
int count = 0;
for(int i=0; i<size; i++)
{
if(isSet(n,i))
count++;
}
return count;
}
int countBitsMODERATE(long long int n)
{
int size = sizeof(n) * 8;
int count = 0;
if(n<0)
{
n &= n^(1LL<<size-1);
count = 1;
}
for(; n > 0; count++)
n &= n-1;
return count;
}
//found it to be Hamming weight problem on wiki.
int countBitsVERYHARD(long long int n)
{
long long int result = (n & 0x5555555555555555LL) + (n>>1 & 0x5555555555555555LL);
result = (result & 0x3333333333333333LL) + ((result>>2) & (0x3333333333333333LL));
result = (result & 0x0f0f0f0f0f0f0f0fLL) + ((result>>4) & (0x0f0f0f0f0f0f0f0fLL));
result = (result & 0x00ff00ff00ff00ffLL) + ((result>>8) & (0x00ff00ff00ff00ffLL));
result = (result & 0x0000ffff0000ffffLL) + ((result>>16)& (0x0000ffff0000ffffLL));
result = (result & 0x00000000ffffffffLL) + ((result>>32)& (0x00000000ffffffffLL));
return result;
}
int main()
{
long long int n = 15;
int testCases ;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>n;
cout<<"\nEASY : "<<countBitsEASY(n);
cout<<"\nMODERATE : "<<countBitsMODERATE(n);
cout<<"\nVERY HARDS : "<<countBitsVERYHARD(n)<<endl;
}
}
HIT BIT
/*
* Given a 64-bit signed long, find the position of the most significant set bit (a "set bit" means a bit whose value is 1). The least significant bit is considered to have position 0, the next least significant bit has position 1, and so on.
* If there are no set bits at all, print -1.
* Example Inputs:
* 0
* -1
* 25
* Outputs (respectively):
* -1
* 63
* 4
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(k) time.
* Moderate: O(log(k)) time.
*/
#include <iostream>
using namespace std;
inline bool isSet(long long int n,int i)
{
long long int x = 1;
x <<=i;
if(x&n)
return true;
return false;
}
//EASY
int getSetMSBPositionEASY(long long int n)
{
int size = sizeof(n);
size <<=3;
for(int i=size-1; i>=0; i--)
{
if(isSet(n,i))
return i;
}
return -1;
}
//MODERATE
int getSetMSBPositionMODERATE(long long int n)
{
int size = sizeof(n);
size <<=3;
int start = size-1;
int end = 0;
int mid = (start+end)/2;
while( start >= end)
{
long long int check = ~(0LL)^((1LL<<mid)-1);
if(n & check)
{
end = mid+1;
}
else
{
start = mid-1;
}
mid= (start+end)/2;
}
return mid;
}
int main()
{
long long int n;
int testCases;
//FIRST ENTER NUMBER OF TEST CASES
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>n;
if(!n)
cout<<-1;
else
{
cout<<"\nEASY = "<<getSetMSBPositionEASY(n);
cout<<"\nMODERATE = "<<getSetMSBPositionMODERATE(n);
}
}
}
Subscribe to:
Posts (Atom)