Doubly Linked List using c++

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include<string>

struct _node_student;

#define CREATE_NODE  ( struct _node_student* ) malloc(sizeof(_node_student) )

using namespace std;

// a struct to represent a student in a queue as a node of a doubly linked list
struct _node_student{
    //the student number
    unsigned int _std_num = 0;
    //pointer to next student node
    _node_student* next;
    //pointer to previous student node
    _node_student* prev;

} *ptr;


//class implementing a doubly linked list for queue at the department


class Queue{
    //total students PROCESSED  in queue at any instance 
    unsigned int _ttl_stdnt_procsd;

    //pointer to front of the queue
    _node_student* front;
    //pointer to end of the queue
    _node_student* end;

public:

    //constructor
    Queue(){
        _ttl_stdnt_procsd = 0;

        //make fornt and end point eachother
        front = CREATE_NODE;
        end = CREATE_NODE;

        front->next = NULL;
        front->prev = NULL;

        end->prev = front;
        end->next = NULL;

        front->next = end;
    }

    //accessor and manipulation functions
    void  addAtHead(unsigned int _ttl_stud);
    void  addAfter(unsigned int _stud_num);
    void  addBefore(unsigned int _stud_num);
    void  removeStudent(unsigned int num);
    void display();

    //getter and setter for total student processed
    int getTtlStdProcsd(){ return _ttl_stdnt_procsd; };
    void incrmntTtlStdProcsd(){ ++_ttl_stdnt_procsd; };


};


//functions add students at the end of queue
void Queue::addAtHead(unsigned int _ttl_stud)
{
    //get the  student number of first student  to be added this time as index
    unsigned int  index = getTtlStdProcsd() + 1;

    // update total student
    _ttl_stud += getTtlStdProcsd();

    //add all students at at end of the queue
    while (index <= _ttl_stud)
    {


        //get  end  student node already in queue
        _node_student* u = CREATE_NODE;
        u = end->prev;


        //create a new student node and initialise its number
        _node_student* v = CREATE_NODE;

        //update the queue by adding student node v after u in the queue
        v->next = end;
        v->prev = u;
        v->_std_num = index;


        u->next = v;
        end->prev = v;


        ++index;

        //increment total student processed
        incrmntTtlStdProcsd();
    }


}



// test function to display the queue

void Queue::display()
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->next != NULL)
    {
        cout << ptr->_std_num << " ";
        ptr = ptr->next;
    }



}


// add a student node before his/her's best  friend ;)
void Queue::addBefore(unsigned int _stud_num) {

    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* u = CREATE_NODE;


    u = ptr->prev;

    //add v before his friend _stud_num
    v->next = ptr;
    v->prev = ptr->prev;

    ptr->prev = v;
    u->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();



}


// add a student node after his/her's best  friend :P
void Queue::addAfter(unsigned int _stud_num)
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* w = CREATE_NODE;

    w = ptr->next;

    //add v after student _stud_num
    v->next = ptr->next;
    v->prev = ptr;

    w->prev = v;
    ptr->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();


}


// kick out students from the queue
void Queue::removeStudent(unsigned int _stud_num)
{


    for (unsigned int i = 0; i < _stud_num; ++i)
    {
        _node_student* tmp = front;
        front = front->next;
        free(tmp);

    }


}

Bellman-Ford's single source shortest path algorithm

// program for Bellman-Ford's single source shortest path algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include<conio.h>

// a structure to represent a weighted edge in graph
struct Edge
{
    int src, dest, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
    // V-> Number of vertices, E-> Number of edges
    int V, E;

    // graph is represented as an array of edges.
    struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

    return graph;
}

// A utility function used to print the solution
void printArr(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm.  The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[5];

    // Step 1: Initialize distances from src to all other vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
    // to any other vertex can have at-most |V| - 1 edges
    for (int i = 1; i <= V - 1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // Step 3: check for negative-weight cycles.  The above step guarantees
    // shortest distances if graph doesn't contain negative weight cycle. 
    // If we get a shorter path, then there is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] + weight < dist[v])
            printf("Graph contains negative weight cycle");
    }

    printArr(dist, V);

    return;
}

// Driver program to test above functions
int main()
{
    /* Let us create the graph given in above example */
    int V = 5;  // Number of vertices in graph
    int E = 8;  // Number of edges in graph
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 (or A-B in above figure)
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    // add edge 0-2 (or A-C in above figure)
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    // add edge 1-2 (or B-C in above figure)
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    // add edge 1-3 (or B-D in above figure)
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    // add edge 1-4 (or A-E in above figure)
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    // add edge 3-2 (or D-C in above figure)
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    // add edge 3-1 (or D-B in above figure)
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    // add edge 4-3 (or E-D in above figure)
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    BellmanFord(graph, 0);
    getchar();
    return 0;
}

Warshall Algorithm - All pairs shortest path

//programme for floyd warshall algroithms -  all pair shortest path 
// Complexity - O(V ^ 3) where V is total vertices
#include<stdio.h>
#include<conio.h>

//number of vertices in ours graphh 
#define V 4 

/*
* Define Indefinite as large as possible to represent vertices
* not connected to eachother
*/

#define INF 99999

// a function to print solution matrix of  all pair shortest paths
void printSolution(int dist[][V]);

//solves the all- pair shortest path problem 
void floydWarshell(int graph[][V]){

//dist[][] will be the output matrix tht will  have shortest
//path 
int dist[V][V], i, j, k;

//initial solution matrix same as graph matrix
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];

for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix
printSolution(dist);








}


void printSolution(int dist[][V])
{
printf("Following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}



int main()
{
/* create the following weighted graph
     10
(0)------->(3)
|             /|\
   5   |              |1
|              | 
       \|/             |
      (1)------->(2)
     3         
 
*/
int graph[V][V] = 
{
{ 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 }
};

// Print the solution
floydWarshell(graph);
getchar();
return 0;
}

Dynamic Programming - Overlapping subprobelm paradigm

/* Dynamic programming explained using a simple Fibonacci numbers
* 1- Overlapping subproblem type 
*  Recrusive style 
*/

int fib(int n)
{
if (n <= 1)
return n;
else
return fib(n - 1) + fib(n - 2); 


}

Recursion tree for fib(5) -

Notice  that the fib(3) is being calculated two times
And many more are subproblem recalcualtion is present too .
So if we can save the result of subproblems, then the overlapped subproblems
can be solved efficiently .

Two ways -
1 - Memoization - top down
2 - Tabulationn - bottom up


//Memoizazed Fibonacci numbers evaluation 



#include<stdio.h>
#define NIL -1 
#define MAX 100 

int lookup[MAX];

// function to initialize the look up table 
void _intialize()
{
int i;
for (i = 0; i < MAX; ++i)
lookup[i] = NIL;

}



int fib(int n)
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n; 
else
lookup[n] = fib(n - 1) + fib(n - 2); 

}

return lookup[n];


}



 //driver main function
int main()
{
int n = 40; 
_intialize();
printf("the  40th  Fibbonacci number  %d  ", fib(n)); 
getchar();
return 0; 
 

 }



Tabulated version of nth Fibbonacci numbers


int fib(int n)
{
int f[n + 1];
int i; 
f[0] = 0; 
f[1] = 1;
for (i = 2; i <= n; ++i)
f[i] = f[i - 1] + f[i - 2];

return f[n];


}











//

Bucket Sort

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; 

void bucketSort(float arr[] , int  n) ;

int main()
{
float arr[] = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 };
int n = sizeof(arr)/ sizeof(arr[0]);

bucketSort(arr, n); 
cout << " sorted array is \n  ";
for (int i = 0; i < n; ++i)
{
cout << arr[i] << " "; 

}

getchar();
return 0; 


}

void bucketSort(float arr[],const int n ) { 
// make a vector of n  empty buckets
vector <float> bucket[6];

//put array elemnts in different buckets 
for (int i = 0; i < n; ++i){
int bi = n * arr[i];
bucket[bi].push_back[arr[i]];



}
//sort individual buckets
for (int i = 0; i < n; ++i)
sort(bucket[i].begin(), bucket[i].end());
int index = 0;
//concatanate all buckets into 
for (int i = 0 ; i < n ; ++i)
for (int j = 0; j < bucket[i].size(); ++j)
arr[index++] = bucket[i][j];

}

UVa - 10810 - Ultra-QuickSort

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
static long num = 0 ; 
public static void main (String args[] ){
Scanner scan =  new Scanner(new BufferedInputStream(System.in));
while(scan.hasNext()){
int n =  scan.nextInt();
if(n == 0 )
break ; 
num = 0 ; 
int data[] =  new int[n];
for(int  i = 0 ; i < n ; ++ i ){
data [i] =  scan.nextInt();

}
mergeSort(data , 0 , n - 1 );
System.out.println(num);
}

}

static void mergeSort(int array[] , int left , int right){
if( left  <  right ){
int center   = (left + right )  / 2 ; 
mergeSort(array , left , center );
mergeSort(array , left , center );
mergeSort(array , center+ 1 , right ); 
Merge(array , left ,center , right );
}


}

static void Merge (int array[] , int left  , int center , int right ){
int [] temp  =  new int[right - left + 1];
int  i = left ;
int j =  center + 1 ;
int k = 0 ;
while ( i <= center && j <= right ){
if (array[i]  > array [j])
{
temp[k++] = array[j++];
num += center - i + 1 ;
}else
{
temp[k++] = array[i++] ;
}
}
while ( i <= center )
temp[k++] = array[i++];

while (j <= right ){
temp[k++] = array [j++];
}

for(i = left , k = 0 ; i< right ; i++ , k++){
array[i] = temp[k];
}
}

}

A SIMPLE BROWSER USING JAVA

Main Class
import javax.swing.JFrame;


public class Main {
    public static void main(String args[]){
        ReadFile  dude =  new ReadFile();
        dude.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
}





Html page fetch and display class -

import java.awt.*;
import java.awt.event.*;

import javax.swing.*;
import javax.swing.event.*;


public class ReadFile extends JFrame {
    private JTextField addressBar; // address bar
    private JEditorPane display ; //  browser display pane
   
    // constructor
    public ReadFile(){
            // title for the browser window
        super("Jim's X-Browser");
       
        // initialise the guis
        addressBar = new JTextField("enter a URL hoss ! ") ;
        //add the action listner for the enter event by the user
        addressBar.addActionListener(
                new ActionListener(){
                   
                    @Override
                    public void actionPerformed(ActionEvent e) {
                        // TODO Auto-generated method stub
                        //getActionCommand Returns the command
                        //string associated with this action.
                            loadCrap(e.getActionCommand());
                    }
                   
                }
                );
        //add to the scrreen
        add(addressBar , BorderLayout.NORTH);
       
        //set the display as JEditor pane used
        display = new JEditorPane();
        //can be used for creating notepad and stuff like that
        display.setEditable(false);
        display.addHyperlinkListener(new HyperlinkListener(){

            @Override
            public void hyperlinkUpdate(HyperlinkEvent e) {
                // TODO Auto-generated method stub
                 if(e.getEventType() == HyperlinkEvent.EventType.ACTIVATED)
                     loadCrap(e.getURL().toString());
               
            }
           
        }
    );
        add(new JScrollPane(display) ,  BorderLayout.CENTER);
        setSize(500,300);
        setVisible(true);
    }

   
    //load crap to display html file on screen
    private void loadCrap(String userTextURL){
        try{
            display.setPage(userTextURL);
            addressBar.setText(userTextURL);
        }catch( Exception e){
            System.out.println("crap !");
        }
       
   
}
}

GENERIC METHODS IMPLEMENTATION

GENERIC METHODS - 
Allows us to overload the function any data type at a particualr instance , such that we need not to write many different overloaded functions for different data types involved  .

Example - 


public class Main {
public static void main (String args[]){

//initialise string for list collection
String i [] = {"cats" , "dogs" , "mouse" , "hamsters" , "dogs"};
Integer j[] = {1 , 2 };

printMe(i);
System.out.println();
printMe(j);

}

public static <E> void printMe(E i[] ){
for(E a : i )
System.out.print(a + " ");
}
}

JAVA COLLECTIONS FRAMEWORK

Introductions to Collections

Collections like array holds stuff , holds references to other objects  but unlike array its dynamic

Populat sets - 

Collection - 
The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements.
 Some collections allow duplicate elements and others do not. 
 Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: 
 it provides implementations of more specific subinterfaces like Set and List.
 This interface is typically used to pass collections around and manipulate them where maximum generality is desired. 



List -  
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element 
is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
Unlike sets, lists typically allow duplicate elements


Iterator -

 An iterator over a collection. Iterator takes the place of Enumeration in the Java Collections Framework. Iterators differ from enumerations like this that iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics. 

example
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;



public class Main {
public static void main (String args[]){

//initialise string for list collection
String i [] = {"cats" , "dogs" , "mouse" , "hamsters"};
String j[] = {"cats" ,  "dogs"};


// develope list interface for strings defined
List<String> list1 =  new ArrayList<>();
List<String> list2 =  new ArrayList<>();


//add the string objects in list collections
for(String a : i)
list1.add(a);
for(String a : j)
list2.add(a);

System.out.println("Before");
for (int k = 0  ; k < list1.size() ; k++)
System.out.printf("%s " , list1.get(k));

//edit the list1 , by deleting those entries which are present in list two
editlist(list1 , list2);

System.out.println();
System.out.println("After editing");
for (int k = 0  ; k < list1.size() ; k++)
System.out.printf("%s " , list1.get(k));



}

public static void editlist(Collection <String> l1 , Collection <String> l2){
Iterator <String> it =  l1.iterator();
while(it.hasNext()){
if(l2.contains(it.next()))
it.remove();

}

}

}



Collections -
Collections class consists exclusively of static methods that operate on or return collections. 
It contains polymorphic algorithms that operate on collections, "wrappers", which return a new 
collection backed by a specified collection, and a few other odds and ends. 
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null

Example - List<String> ll =  Arrays.asList(stringArrayName);
Collections.sort(ll); // aplpahbatically in ascending order
//polymorphic now
Collections.sort(ll, Collection.reverseOrder());

Other methods are Collections.reverse(); 
               Collections.copy( dest ,  src ) , Collections.fill()
Collections.addAll() -
Adds all of the specified elements to the specified collection. "Elements to be added                              may be
specified individually or as an array. "
The behavior of this
convenience method is identical to that of c.addAll(Arrays.asList(elements)),
but this method is likely to run significantly faster under most implementations

System.out.println(Collections.frequency(list,"digg"));
Returns the number of elements in the specified collection
                        equal to the specified object. More formally, returns the number of 
                         elements e in the collection
such that (o == null ? e == null : o.equals(e)).

Collections.disjoint(list1,list2);

Returns true if the two specified collections have no elements in common.