MaximumSubArray – Dynamic programming

//aim of the program is to find the maximum subarray (contiguous sequence of number) in an array containing both positive and negative numbers

#include<iostream>
using namespace std;
int main(){
    int n;
    cout<<“enter the number of elements”;
    cin>>n;
    int arr[n],max[n],maxsum=0;
    cout<<“enter the elements”;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(arr[0]>0)
      max[0]=arr[0];
      else
      max[0]=0;
      for(int i=1;i<n;i++){
          if((max[i-1]+arr[i])>0){
              max[i]=max[i-1]+arr[i];
          }
              else
              max[i]=0;
          
      }
      for(int i=1;i<n;i++){
          if(max[i]>maxsum){
              maxsum=max[i];
          }
      }
      cout<<“\n maximun sum is “<<maxsum;
  }
 

Change Making problem-Dynamic Programming

Problem:

Given a value n, if we want to make change for n cents, and we have infinite supply of each of d = { d1, d2, .. , dm} valued coins, what is the minimum number of coins to make the change?

 

	#include<iostream>
	using namespace std;
	int d[4]={1,2,5,10};//denomination array
	int k=4;//number of denomination
	void getMinimumNumberOfChanges(int n){
	//c[i] => array to store the minimum number of coins required to value i
	//s[i] => array to store the last coin required to get the value i
	int c[n],s[n],min,coin;
	c[0]=0;
	//DP is all about splitting in the problem into many sub problems
	//here we first find no. of changes for p=1 then ,p=2 ,......till p= n which is the required value
	//so first for loop runs from p=1 to n
	for(int p=1;p<=n;p++){
	min=999;
	considering all possible denominations from array index 0 to k-1
	for(int i=0;i<k;i++){
	if(d[i]<=p){
	if(1+c[p-d[i]]<min){
	min=1+c[p-d[i]];
	coin=i;
	}
	}
	}
	c[p]=min;
	s[p]=coin;
	}
	cout<<"Minimum no. of coins required "<<c[n];
	cout<<"coins are"<<'\n';
	//this while loop is for tracing the coins.the code is self explanatory
	while(n>0){
	cout<<d[s[n]]<<"\n";
	n=n-d[s[n]];
	}
	}

view raw changemaking.cpp hosted with ❤ by GitHub

 

How cool Git is ?

Consider this scenario: You and your friend are developing an application. You code a module and use it in few source code files and send your work as a zipped file to your friend who in turn merge the code with his work. This might seem to be feasible and easy in the beginning. Eventually as you to get  into serious coding(lets assume end week of your project submission) compressing the project folder and mailing it to each other might seem to be a tiresome work. You might not know the files that your friend modified and whether it is compatible with your code.
Believe me (for those who haven’t developed an app or haven’t been in a project  yet) this job takes an hell lot of time and also leads to huge amount of confusion.

Isn’t there a solution??
Yes there is!!! Welcome to the magical world of version control tools!!
Using a version controller you can magically revert your source code back to any previous commits.

Git (revision control) is one of the most used version controller. It  is a open source tool developed by Linus Torvalds himself!!

How cool is Git?:

Since Git helps to undo any change that a developer has done in the source code, does it create a separate backup file after each successful commit ? Surprisingly not!
 With git, this all happens seamlessly in the  background using databases.
Also the space required by the database is quite small!!

Basic git terminologies :

Commit- making a set of tentative changes permanent in your computer
push – moving the committed code to your remote repository
pull- getting the latest code(last commit) from the remote repository

How Git helps to coordinate a development project?
You can have a remote(cloud) repository of your code using many online services like github , Bitbucket, etc.  where you can store your project files.

If your friend needs to work with your code in the project, you need not compress all the files you have modified and send it to him. Instead now since  you know git  can just commit -> push your code.
 
Your friend on the other side can pull it and it automatically merges with his project folder!! Cool eh??

How does it Git look?
 Git is mostly used via the command line. Though there are visual tools for adding and removing files, etc. for Git, it is best used via the command line. More than the GUI tools you will find the git commands easy! Skeptic? Try the commands you will know!

There are many exciting features of the Git such as branching, cloning, etc. that you can explore via @ where you can find a free book on Git

Whether you are a programmer, blogger or even a writer Git is the best way to handle all the documents and files!!

Level Order Traversal in BST

a level order traversal can be implemented using queues.

the following code is in java

 void levelOrder(Node node){//node is the root of the tree here
          Node temp;
          
        Queue<Node> q=new LinkedList<Node>();
        if(node!=null)
            q.add(node);
           
        while(!q.isEmpty()){
            temp=q.poll();
            if(temp.left!=null)
                q.add(temp.left);
            if(temp.right!=null)
                q.add(temp.right);
            System.out.println(temp.value);
            
            
        }
        
          
      }

Queue Interface in Java

Java comes with its own builtin Queue interface.

Lets see a simple program using Queue Interface

import java.util.*;
public class BuiltInQueue {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Queue<Integer> q=new LinkedList<Integer>();
int c,n;
Scanner S=new Scanner(System.in);
while(true){
System.out.println(“1)enqueue,2)dequeue,3)peek,4)exit”);

c=S.nextInt();

switch(c){
case 1: System.out.println(“enter number”);
n=S.nextInt();
q.add(n);
break;
case 2:System.out.println(q.poll());
break;
case 3:System.out.println(q.peek());
break;
case 4:System.exit(0);

}

}
}
}

Binary Search Tree in Java

import java.util.Scanner;

/**
*
* @author vishnu
*/
class Node
{

Node left;
Node right;
int value;

public Node(int value) {
this.value = value;
}
}
class BinarySearchTree{

Node root;
public BinarySearchTree(){
root=null;

}
void insertNode(int value){
insert(root,value);
System.out.println(“inserting!!!!”+value+” “+root.value);
}
void insert(Node root, int value) {
if(this.root==null){

this.root=new Node(value);

return;
}
if (value < root.value) {
if (root.left != null) {
insert(root.left, value);
} else {
root.left = new Node(value);
System.out.println(“inserted!!!!”+value);

}
} else if (value > root.value) {
if (root.right != null) {
insert(root.right, value);
} else {
root.right = new Node(value);
System.out.println(“inserted!!!!”+value);
}
}
}

void inOrder(){
inOrder(root);
}

void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.println( node.value);
inOrder(node.right);
}
}

}

public class BST {

public static void main(String[] args)

{

BinarySearchTree tree = new BinarySearchTree();
Node rootnode = null;
Scanner S=new Scanner(System.in);
int c,n;
while(true){
System.out.println(“menu:\n1)Insert\n2)Display\n3)Exit”);
c=S.nextInt();
switch(c){
case 1:
System.out.println(“enter the value”);
n=S.nextInt();
tree.insertNode(n);
break;
case 2:

System.out.println(“Traversing tree in order”);
tree.inOrder();
break;
case 3:
System.exit(0);
break;

}

}

}

}