Pre order, In order, Post order, Level order Tree Traversal Reference Sheet

The reference sheet below shows the print traversal order for preorder, inorder, postorder and levelorder tree traversal.

Code for printing preorder, inorder, postorder and levelorder traversal is available here. Instructions for inputting a graph can be found in this tutorial.

Both recursive and iterative algorithms for tree traversal are available here.

Tree Input:
tree traversal input
tree traversal input

Tree Traversal Reference Sheet:

pre-in-post-level-order-tree-traversal
pre-in-post-level-order-tree-traversal
Advertisements

Inputting directed, undirected, weighted and unweighted graph in C, C++ Adjacency Matrix

The codes below uses 2D array adjacency matrix. For both sparse and dense graph the space requirement is always O(v2) in adjacency matrix. The codes below can be used take input and store graphs for graph algorithm related problems.

Related to this have a look at,

DIRECTED, UNDIRECTED, WEIGHTED, UNWEIGHTED GRAPH REPRESENTATION IN ADJACENCY LIST, MATRIX REFERENCE SHEET


Input for Directed Weighted Graph:

directed weighted input
directed weighted input

Code Directed Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        Graph[u][v] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Directed Unweighted Graph:

directed unweighted input
directed unweighted input

Code Directed Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // For directed graph edges (u,v) != (v,u)
        Graph[u][v] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Undirected Weighted Graph:

undirected weighted input
undirected weighted input

Code Undirected Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        // For undirected edge (u,v) = (v,u)
        Graph[u][v] = Graph[v][u] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

 

Input for Undirected Unweighted Graph:

undirected unweighted input
undirected unweighted input

Code Undirected Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // Here value of 1 represents there is an edge (u,v)
        Graph[u][v] = Graph[v][u] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Directed, Undirected, weighted, Unweighted graph Representation in Adjacency list, matrix Reference Sheet

This is simple attempt to show Directed, Undirected, weighted, Unweighted graph Representation in Adjacency list, matrix. This can be helpful to understand how graph are represented or stored. The 2D adjacency matrix can be stored in 2D array and the adjacency list can be stored in linked list. A large value such as infinity may also mean there is no edge between two vertices. Graph representation in incidence matrix and list is not shown here.

For reference check out 10th chapter of DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H. Rosen.


 

Graph Representation Reference Sheet:

graph representation reference sheet
graph representation reference sheet

0-1 Knapsack Iterative and Recursive with Code

0-1 Knapsack:

This problem can be solved be dynamic programming. Given some weight of items and their benefits / values / amount, we are to maximize the amount / benefit for given weight limit.

Background:

Suppose we are thief trying to steal. We got a knapsack with a weight carry limit. We go to a house there are a few items. The items have weights and also resale value. Now with our limited weight in the knapsack and many valuable items to take, we need to maximize our gain. We can do so by trying all items and filling the weight limit.

We will be given a few things as input. Such as number of items, each of their weights, each of their monetary value / cost ( if it represents cost ) and a weight limit. We are to find that by trying all items and the weight limit what is the maximum possible benefit.

If it is unclear the Wikipedia article on 0-1 knapsack may be helpful. I will show the table fill and items taken in the knapsack in another post.


Recurrence Relation:

The recurrence relation for this problem follows,

cost[ i, w ] = cost[ i – 1, w ] if, Wi > w
cost[ i, w ] = max( cost[ i – 1, w ], cost[ i – 1, w – W] ) if, Wi <= w


Question:
items | weight | benefit
========================
1     | 6      | 10
2     | 1      | 5
3     | 2      | 7
4     | 5      | 12
5     | 4      | 8
6     | 3      | 6

For weight of 10 what is the maximum possible benefit by trying all item?


Answer:

For this problem max benefit is 26.

The answer is always found in cost[ item_count, total_weight ]
Our item_count was 6 and total_weight was 10.
Here the answer is in cost[ 6, 10 ] which is 26.

Table Fill:
knapsack table fill output
knapsack table fill output

Code:


Iterative:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack iterative
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

void dynamicKnapsack(){
    int i = 0;

    /*
     * Set each column in first(zeroth) row to zero
     */
    for(; i <= total_weight; ++i)
        CostTable[0][i] = 0;

    /*
     * Set each row in first(zeroth) column to zero
     */
    for(int i = 0; i <= item_count; ++i){
        CostTable[i][0] = 0;

        /*
         * calculate till required weight
         */
        for(int w = 1; w <= total_weight; ++w){
            /*
             * Get value from row above
             * or,
             * the value from a left column (w - Weight[i]) in the row above with added benefit
             */
            if(Weight[i] <= w)
                CostTable[i][w] = max(Benefit[i] + CostTable[i-1][w - Weight[i]], CostTable[i-1][w]);
            else
                CostTable[i][w] = CostTable[i-1][w];
        }
    }
}

void printCostTable(){
    for(int i = 0; i <= item_count; ++i){
        printf("%d:  ", i);
        for(int w = 0; w <= total_weight; ++w)
            printf("%d ", CostTable[i][w]);
        printf("\n");
    }
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    dynamicKnapsack();

    printf("Max Benefit: %d\n\n", CostTable[item_count][total_weight]);

    printCostTable();

    return 0;
}

Recursive:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack recursive
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
    if(i == 0 || w == 0)
        return 0;

    if(Weight[i] > w)
        return RecursiveKnapsack(i - 1, w);
    else
        return max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

    return 0;
}

Recursive Memoized:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Zero one knapsack recursive memoization
 */

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
    return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
    if(CostTable[i][w] != -1)
        return CostTable[i][w];

    if(Weight[i] > w)
        CostTable[i][w] = RecursiveKnapsack(i - 1, w);
    else
        CostTable[i][w] = max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;

    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;

    /*
     * Set all values of 2D matrix CostTable to Minus 1
     */
    for(int i = 0; i <= item_count; ++i)
        for(int w = 0; w <= total_weight; ++w)
            CostTable[i][w] = -1;

    printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

    return 0;
}

LCS Algorithm Practice Sheet With Solution Steps

LCS Algorithm blank sheet made with a sample input from uva 10405 longest common subsequence. See this and this tutorial to have a better understanding.


LCS Table with Little Hint:

lcs_algorithm_blank_sheet
lcs_algorithm_blank_sheet

LCS Table with Hints:

lcs_blank_sheet_with_hints
lcs_blank_sheet_with_hints

Completed LCS Table:

lcs_completed_table
lcs_completed_table

LCS Algorithm Table Fill and Print Code with short tutorial

NOTE:

LCS is a very important algorithm and has many uses in computer science. What is a longest common sub sequence? learn about it in Wikipedia.

This tutorial (although not a good one) is an attempt to try to clear concept for LCS Algorithm which is used in UVA problem 10405 (Solution). Here I have used example 3 from that problem.

The table filling method and a practice sheet for this problem can be found in here with better info-graphics.


Instructions:

For the LCS table we define a 2D matrix with a safe size. We can use one string row-wise ( tracked with i ) and another string column-wise ( tracked with j ). It doesn’t matter which way we layout the strings.


The way to fill the table or the 2D matrix is,

  1. If the characters match then take value from row above and left column then add 1 to it and set it as the value of current position.
  2. If characters do not match then take the biggest value from either the row above in the same column or from the left column in the same row, whichever may be the biggest.

We can also print the LCS string the same way in following this concept,

  1. We start at the bottom right corner position of the matrix then trace backwards.
  2. If the characters at the position of current row and column match then print that character and move to left column and row above in the matrix.
  3. If the characters at the position of current row and column do not match then either go to row above or left column depending on whichever is holding the biggest value.

 

Mechanism:

LCS table filling tutorial
LCS table filling tutorial
Print the longest common sequence from generated table tutorial
Print the longest common sequence from generated table tutorial

 

Code/Algorithm LCS String Print:

Please DO NOT try to submit this. This is not the required solution for problem 10405. If you want solution or the inputs to that problem visit this link. Input for this program is two strings. Inputs from problem 10405 will work fine.   

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: LCS Print
 * MUST READ: THIS IS NOT A SOLUTION TO UVA 10405
 */

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

/**
 * Print the LCS string
 */
void PrintLCS(int i, int j){
    if(i == 0 || j == 0)
        return;

    if(x[i-1] == y[j-1]){
        PrintLCS(i-1, j-1);
        printf("%c", x[i-1]);
    }
    else if(lcs[i][j-1] > lcs[i-1][j]){
        PrintLCS(i, j-1);
    }
    else
        PrintLCS(i-1, j);
}

int main(){
    register int i, j;

	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * Set the first row and column to zero
         */
        for(i = 0; i <= xlen; ++i)
            lcs[i][0] = 0;

        for(i = 1; i <= ylen; ++i)
            lcs[0][i] = 0;

        /*
         * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
         * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
         */
        for(i = 1; i <= xlen; ++i){
            for(j = 1; j <= ylen; ++j){
                if(x[i-1] == y[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        /**
         * Print the LCS string
         */
        printf("LCS String: ");
        PrintLCS(xlen, ylen);
        printf("\n");

        /*
         * The max length is at the bottom right corner of the table
         */
        printf("LCS Length: %d\n", lcs[xlen][ylen] );

	}
	return 0;
}