Bubble Sort Using Unix Shell Script

This script will sort the given input passed from command line based on bubble sort technique. You can give any number of inputs but only integers.

echo "Enter Values That You Want To Sort(eg. 3 2 1):"
read vals

set -- $vals
n=$#

k=0
for val in $* 
do
    a[$k]=$val
    ((k++))
done

flag=1

for (( i=0; i<$n-1 && $flag==1; i++ ))
do
    flag=0
    for (( j=0; j<$n-i-1; j++ ))
    do
        if [ ${a[$j]} -gt ${a[$j+1]} ]
        then
            temp=${a[$j]}
            a[$j]=${a[$j+1]}
            a[$j+1]=$temp
            flag=1
        fi
    done
done

echo "Sorted: "
for (( l=0; l<$n; l++))
do
    echo -ne "${a[$l]} "
done

echo

$ chmod +x bubble.sh
$ ./bubble.sh
Enter Values To Sort (eg. 3 2 1):
5 4 3 2 1 1 2 3 4 5
Sorted: 
1 1 2 2 3 3 4 4 5 5 

C++ Stack Implementation Using Template And Exceptions

#include <iostream>
#include <stdexcept>
#include <cstdlib>
#include <string>
using namespace std;

template <class T>
class Stack
{
    private:
        T *stk;
        int size, tos, maxsize;
    public:
        Stack(int);
        ~Stack() {delete [] stk;} 
        T top() const;
        void pop();
        void push(T);
        template <class sT> friend ostream& operator<<(ostream &, const Stack<sT> &);   
        bool isempty() const {
            return (size == 0);
        }   
};

template <class T>
Stack<T>::Stack(int s)
{
    size = 0;
    maxsize = s;
    tos = -1;
    if (s <= 0) {
        throw out_of_range("stack(): size cant be zero or nagative.");
    }
    else {
        stk = new T[maxsize];
    }
}

template <class sT>
ostream& operator<<(ostream &out, const Stack<sT> &s)
{
    int i;
    cout << '[';
    for (i = 0; i < s.size; i++) {
        out << s.stk[i] << "," << ends;
    }
    cout << "\b\b";
    cout << ']';
    return out;
}

template <class T>
T Stack<T>::top() const 
{
    if (isempty()) {
        throw out_of_range("top() error: stack is empty.");
    }
    else {
        return stk[tos];
    }
}

template <class T>
void Stack<T>::push(T elem)
{
    if(size == maxsize) {
        throw out_of_range("push error: Stack is full.");
    }
    else {
        stk[++tos] = elem;
        ++size;
    }
}

template <class T>
void Stack<T>::pop()
{
    if(isempty()) {
        throw out_of_range("pop() error: Stack is full.");
    }
    else {
        size--;
        tos--;
    }
}


int main()
{
    try {
        cout << "<For Integers>" << endl;
        Stack<int> s(5);
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        cout << "Stack:" << s << endl;
        
        cout << "\n<For Strings>" << endl;
        Stack<string> g(4);
        g.push("Superman");
        g.push("Batman");
        g.push("Flash");
        g.push("Spiderman");
        cout << "Stack:[";
        while(!g.isempty()) {
            cout << g.top() << "," << ends;
            g.pop();
        }
        cout << "\b\b]" << endl;
        
        cout << "\n<Exception>" << endl;
        Stack<int> j(0);
    }
    catch(exception &e) {
        cerr << e.what() << endl;
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

<For Integers>
Stack:[1, 2, 3, 4]
<For Strings>
Stack:[Spiderman, Flash, Batman, Superman]
<Exception>
stack(): size cant be zero or nagative.

--------------------------------
Process exited after 0.3268 seconds with return value 1
Press any key to continue . . .

Renaming Files In A Directory In Sequential Order Using Python Script

Before Running Script	After Running Script

import os

loc = 'E:/My Folder/'
path = os.path.abspath(loc)
i = 1
for file_name in os.listdir(path):
    new_filename = 'File ' + str(i) + file_name[-4:]
    old_filename = loc + file_name
    new_filename = loc + new_filename
    print 'old: ', old_filename
    print 'new:', new_filename
    os.rename(old_filename, new_filename)
    i += 1
print 'Job Done!'

Program To Check Whether A Graph (Undirected) Is Connected Or Not

---

Connected Component

---

For a undirected graph it is easy to check that if the graph is connected or not. To check that a graph is connected or not. We can simply do a depth-first traversal or a breadth first-first traversal on the graph and if the traversal successfully traversal all the nodes in the graph then we can conclude that the graph is connected else the graph has components. This way we can also count the number of components.

For Example:

G	G'

Here G is connected and has one component. But G' is not connected and has two component. 

---

C Implementation

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 //Function to create a graph... void createGraph(int G[][50], int v) { int i, j; printf("\nEnter The Adjacency Matrix: \n"); for(i = 0; i < v; i++) { for(j = 0; j < v; j++) { scanf("%d",&G[i][j]); } } } //Function to print the graph... void printGraph(int G[][50], int v) { int i, j; for(i = 0; i < v; i++) { putchar('['); for (j = 0; j < v; j++) printf("%3d ",G[i][j]); putchar(']'); putchar('\n'); } } //Function for Depth first search... void DFS(int G[][50], int i, int visited[], int v) { int u; visited[i] = TRUE; for(u = 0; u < v; u++) if(G[i][u] == TRUE && visited[u] != TRUE) DFS(G, u, visited, v); } //Call DFS on each single vertex and count the " #(calls) = #(components) "... int visitAll(int G[][50], int v) { int i, visited[50], count = 0; for(i = 0; i < v; i++) visited[i] = FALSE; for(i = 0; i < v; i++) { if(visited[i] != TRUE) { ++count; DFS(G, i, visited, v); } } return count; } //Checks if the graph is connected or not... int isConnected(int G[][50], int v) { return ((visitAll(G, v) > 1)? FALSE : TRUE); } int main() { int G[50][50], v, e; printf("Enter The Number Of Vertices: "); scanf("%d",&v); createGraph(G, v); printf("\nThe Adjacency Matrix:\n\n"); printGraph(G, v); printf("\n\nThe Given Graph Is%sConnected.",isConnected(G, v)?" ":" Not "); printf("\n\nThere Are %d Components.",visitAll(G, v)); return 0; }

---

Output

---

First Run(G):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

The Adjacency Matrix:

[  0   1   1   1 ]

[  1   0   1   1 ]

[  1   1   0   1 ]

[  1   1   1   0 ]

The Given Graph Is Connected.

There Are 1 Components.

Second Run(G'):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:
0 0 0 0
0 0 0 1
0 0 0 1
0 1 1 0

The Adjacency Matrix:

[  0   0   0   0 ]
[  0   0   0   1 ]
[  0   0   0   1 ]
[  0   1   1   0 ]


The Given Graph Is Not Connected.

There Are 2 Components.

Kruskal's MST Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It works by growing forest. Kruskal's algorithm finds a safe edge to add to the growing forest by finding an edge with least weight that connects two tree in the forest.

Algorithm

# here + means union of twp sets
KRUSKAL(G):
  A = NULL
  foreach v in G.V:
  MAKE-SET(v)
  foreach (u, v) ordered by weight(u, v), increasing:
    if FIND-SET(u) != FIND-SET(v):
      A = A + {(u, v)}
      UNION(u, v)
  return A

C Implementation Using Disjoint Set Data Structure

/* Kruskals MST Algorithm Implemented Using Disjoint Set Data Structure (Union & Find).....
 * Where Graph Is Represented In Adjacency Matrix Structure "AdjMa".....
 * Each Cell Has Two Members weight and visited.....
 * For Sorting The Edges WRT Its Weight A Edge: Structure Is Considered.....
 * Where 'u' & 'v' are each end of a vertex with corresponding 'weight'......
 */

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

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
    int weight;
    int visited;
}AdjMatrix;

typedef struct
{
    int weight;
    int u;
    int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
    int i,j;
    printf("Enter The Matrix:\n");

for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            scanf("%d",&graph[i][j].weight);
            if(graph[i][j].weight == 0) graph[i][j].weight = INF;
            graph[i][j].visited = FALSE;
        }
    }
}

void printGraph(AdjMatrix graph[][N])
{
    int i,j;
    for(i = 0; i < N; i++)
    {
        putchar('[');
        for (j = 0; j < N; j++)
        {   if(graph[i][j].weight == INF)
                printf("%3d ",0);
            else
                printf("%3d ",graph[i][j].weight);
        }
        putchar(']');
        putchar('\n');
    }
}

int find(int set[], int i)
{

    if (set[i] == -1)
        return i;
    else
        return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
        return 1;
    else
        return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
    int i, j, k=0, x, y, set[20], cost = 0, e=0;
    AdjMatrix tree[N][N];
    Edge edge[20];

    //Picking The Edges...
    for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            tree[i][j].weight = 0;
            if(graph[i][j].visited != TRUE)
            {
                edge[k].weight = graph[i][j].weight;
                edge[k].u = i;
                edge[k++].v = j;
                graph[j][i].visited = TRUE;

            }
        }
    }

    //Sorting the edges using quicksort()....
    qsort(edge, k, sizeof(Edge), myComp);

    //Setting all elements of parent = -1
    //each element of parent is a disjoint set..
    memset(set, -1, N * sizeof(set[0]));

    i = 0;
    //Loops untill all vertices are considered that is e = #(vertices) - 1
    while (e < N - 1)
    {
        x = find(set, edge[i].u);
        y = find(set, edge[i].v);

        if (x != y)
        {
            cost = cost + edge[i].weight;
            tree[x][y].weight = edge[i].weight;
            tree[y][x].weight = edge[i].weight;
            Union(set, x, y);
            e++;
        }
        i++;
    }

    puts("\nAdjMatrix For MST:\n");
    printGraph(tree);
    printf("\n\nMST Cost = %d",cost);
}


int main()
{
    AdjMatrix graph[N][N];
    system("cls");
    takeInput(graph);
    printf("\nGiven Graph In AdjMatrix Representation:\n");
    printGraph(graph);
    kruskalMST(graph);
    return 0;
}

Output

Enter The Matrix:
0 7 5 2
7 0 4 3
5 4 0 1
2 3 1 0

Given Graph In AdjMatrix Representation:
[  0   7   5   2 ]
[  7   0   4   3 ]
[  5   4   0   1 ]
[  2   3   1   0 ]

AdjMatrix For MST:
[  0   0   0   2 ]
[  0   0   0   3 ]
[  0   0   0   1 ]
[  2   3   1   0 ]

MST Cost = 6
--------------------------------
Process exited after 50.48 seconds with return value 0
Press any key to continue . . .

Discussion

• Time Complexity: Time complexity of Kruskals algorithm depends on how we implement each operation like cycle detection and union and sorting etc
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• WE can use Union-Find for cycle detection to keep track of which vertices are in which component, Which has at most e iterations. Union Find by rank or path compression take O(log(v)) time.
  • Total = O(ElogE + ElogV) = O(Elog E) or O(ElogV)

Difference Between BFS and DFS

Based On	Breadth First Search (BFS)	Depth First Search (DFS)
Description Of The Algorithm	Breadth first search (aka. BFS) is a searching method used to search (or. explore) for a node (or the entire structure) by traversing from root node and explore the search in level by level.	Depth first search (aka. DFS) is a searching method used to search (or explore) for a node (or the entire structure) by traversing from root node and explore the search as deep as possible until a dead end is found.
Data Structure Used	Breadth first search uses a Queue.	Depth first search uses a Stack.
Similar To	Breadth first search is similar to level-order traversal.	Depth first search is similar to pre-order traversal.
Speed	BFS is slower than DFS.	DFS is more faster than BFS.
Advantage	Breadth first search always finds a shortest path from the start vertex to any other for unweighted graphs.	Depth first search may not finds a shortest path.
Algorithm Type	A greedy algorithm. (update neighbors of closest nodes first).	A backtracking algorithm (explore one path until dead end).
Time & Space Complexity	BFS takes O(bd) time and O(bd) space	DFS takes O(bh) time and O(h) space
Applications	Finding the shortest path. Testing for bipartiteness. In spanning tree. Web crawler.	Topological sorting.  Finding the bridges of a graph. Maze generation. Finding strongly connected components.
Traversal Example	8, 3, 10, 1, 6, 14, 4, 7, 3	3, 1, 6, 4, 7, 10, 14, 13

Fully Parenthesized Infix Expression From Postfix Expression

The problem is that you are given a post fix expression and you need to convert it to a fully parenthesize infix expression.

Exmple:

• Input: ab+
• Output: (a+b)

The approach used in this program is to print the parenthesis durin infix traversal of the expression tree built from the postfix expression.

#include <iostream>
#include <stack>

using namespace std;

typedef struct Node
{
    char data;
    Node *lChild, *rChild;
}Node;

class ExpressionTree
{
    private:
        Node *root;
    public:
        ExpressionTree() { root = NULL; }
        ExpressionTree(char[]);
        Node* getRoot() { return root; }
        Node* createNode(char , Node*, Node*);
        friend bool isOperator(char);
        friend void inOrder();
};

bool isOperator(char opp)
{
    switch(opp)
    {
        case '+':
        case '*':
        case '/':
        case '^':
        case '-':
            return true;
        default:
            return false;
    }
}

Node* ExpressionTree::createNode(char ch, Node *l, Node *r)
{
    Node *tmp = new Node();
    tmp->data = ch;
    tmp->lChild = l;
    tmp->rChild = r;
    return tmp;
}

ExpressionTree::ExpressionTree(char arr[])
{
    stack<Node*> s;
    Node *ptr, *l, *r;
    int i = 0;
    while(arr[i])
    {
        if(isOperator(arr[i]))
        {
            l = s.top();
            s.pop();
            r = s.top();
            s.pop();
            ptr = createNode(arr[i], r , l);
        }
        else
        {
            ptr = createNode(arr[i], NULL, NULL);
        }
        s.push(ptr);
        i++;
    }
    root = s.top();
}


void inOrder(Node* T)
{
    if(T != NULL)
    {
        if(isOperator(T->data)) cout << "(";

        inOrder(T->lChild);
        cout << T->data;
        inOrder(T->rChild);

        if(isOperator(T->data)) cout << ")";
    }
}

int main()
{
    char exp[50];
    
    cout << "Enter A Postfix Expression:" << ends;
    cin >> exp;
    
    ExpressionTree t(exp);
    
    cout << "Given Postfix Expression:" << ends;
    cout << exp << endl;
    
    cout << "In-order Form: " << ends;
    inOrder(t.getRoot());
    
    return 0;
}

Enter A Postfix Expression: ab+c*
Given Postfix Expression: ab+c*
In-order Form:  ((a+b)*c)
--------------------------------
Process exited after 6.555 seconds with return value 0
Press any key to continue . . .