Knowledge in Data Structures & algorithms

Associative Arrays in PHP

<html> <body> <?php /* First method to associate create array. */ $salaries = array("mohammad" => 2000, "qadir" => 1000, "zara" => 500); echo "Salary of mohammad is ". $salaries['mohammad'] . "<br />"; echo "Salary of qadir is ". $salaries['qadir']. "<br />"; echo "Salary of zara is ". $salaries['zara']. "<br />"; /* Second method to create array. */ $salaries['mohammad'] = "high"; $salaries['qadir'] = "medium"; $salaries['zara'] = "low"; echo "Salary of mohammad is ". $salaries['mohammad'] . "<br />"; echo "Salary of qadir is ". $salaries['qadir']. "<br />"; echo "Salary of zara is ". $salaries['zara']. "<br />"; ?> </body> </html>

Multidimensional Arrays Using PHP

<html> <body> <?php $marks = array( "mohammad" => array ( "physics" => 35, "maths" => 30, "chemistry" => 39 ), "qadir" => array ( "physics" => 30, "maths" => 32, "chemistry" => 29 ), "zara" => array ( "physics" => 31, "maths" => 22, "chemistry" => 39 ) ); /* Accessing multi-dimensional array values */ echo "Marks for mohammad in physics : " ; echo $marks['mohammad']['physics'] . "<br />"; echo "Marks for qadir in maths : "; echo $marks['qadir']['maths'] . "<br />"; echo "Marks for zara in chemistry : " ; echo $marks['zara']['chemistry'] . "<br />"; ?> </body> </html>

Structures Using C#

using System; struct Books { public string title; public string author; public string subject; public int book_id; }; public class testStructure { public static void Main(string[] args) { Books Book1; /* Declare Book1 of type Book */ Books Book2; /* Declare Book2 of type Book */ /* book 1 specification */ Book1.title = "C Programming"; Book1.author = "Nuha Ali"; Book1.subject = "C Programming Tutorial"; Book1.book_id = 6495407; /* book 2 specification */ Book2.title = "Telecom Billing"; Book2.author = "Zara Ali"; Book2.subject = "Telecom Billing Tutorial"; Book2.book_id = 6495700; /* print Book1 info */ Console.WriteLine( "Book 1 title : {0}", Book1.title); Console.WriteLine("Book 1 author : {0}", Book1.author); Console.WriteLine("Book 1 subject : {0}", Book1.subject); Console.WriteLine("Book 1 book_id :{0}", Book1.book_id); /* print Book2 info */ Console.WriteLine("Book 2 title : {0}", Book2.title); Console.WriteLine("Book 2 author : {0}", Book2.author); Console.WriteLine("Book 2 subject : {0}", Book2.subject); Console.WriteLine("Book 2 book_id : {0}", Book2.book_id); Console.ReadKey(); } }

Iterate characters in reverse order

string_name = "Dehradun"    # slicing the string in reverse fashion  for element in string_name[ : :-1]:     print(element, end =' ') print('\n')   string_name = "Chandigarh"    # Getting length of string ran = len(string_name)    # using reversed() function for element in reversed(range(0, ran)):     print(string_name[element])

Python code to calculate age in years

from datetime import date    def calculateAge(birthDate):     today = date.today()     age = today.year - birthDate.year -           ((today.month, today.day) <          (birthDate.month, birthDate.day))     return age print(calculateAge(date(1997, 2, 3)), "years")

Activity Selection Problem

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem. If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, Fractional Knapsack problem (See this) can be solved using Greedy, but 0-1 Knapsack cannot be solved using Greedy. Following are some standard algorithms that are Greedy algorithms. 1) Kruskal’s Minimum Spanning Tree (MST): In Kruskal’s algorithm, we create a MST by picking edges one by one. The Greedy Choice is to pick the smallest weight edge that doesn’t cause a cycle in the MST constructed so far. 2) Prim’s Minimum Spanning Tree: In Prim’s algorithm also, we create a MST by picking edges one by one. We maintain two sets: a set of the vertices already included in MST and the set of the vertices not yet included. The Greedy Choice is to pick the smallest weight edge that connects the two sets. 3) Dijkstra’s Shortest Path: The Dijkstra’s algorithm is very similar to Prim’s algorithm. The shortest path tree is built up, edge by edge. We maintain two sets: a set of the vertices already included in the tree and the set of the vertices not yet included. The Greedy Choice is to pick the edge that connects the two sets and is on the smallest weight path from source to the set that contains not yet included vertices. 4) Huffman Coding: Huffman Coding is a loss-less compression technique. It assigns variable-length bit codes to different characters. The Greedy Choice is to assign least bit length code to the most frequent character. The greedy algorithms are sometimes also used to get an approximation for Hard optimization problems. For example, Traveling Salesman Problem is a NP-Hard problem. A Greedy choice for this problem is to pick the nearest unvisited city from the current city at every step. This solutions don’t always produce the best optimal solution but can be used to get an approximately optimal solution.

Level Order Successor of a node in Binary Tree

class Node:            def __init__(self, value):         self.left = None         self.right = None         self.value = value          def levelOrderSuccessor(root, key):              if root == None:         return None              elif root == key:                        if root.left:             return root.left                            elif root.right:             return root.right                      else:             return None                      q = []           q.append(root)         while len(q) != 0:          nd = q.pop(0)             if nd.left != None:              q.append(nd.left)            if nd.right != None:              q.append(nd.right)                if nd == key:              break        return q[0]      if __name__ == "__main__":         root = Node(20)     root.left = Node(10)     root.left.left = Node(4)      root.left.right = Node(18)      root.right = Node(26)     root.right.left = Node(24)      root.right.right = Node(27)      root.left.right.left = Node(14)      root.left.right.left.left = Node(13)      root.left.right.left.right = Node(15)     root.left.right.right = Node(19)        key = root.right.left # node 24         res = levelOrderSuccessor(root, key)         if res:          print("LevelOrder successor of " +                   str(key.value) + " is " +                   str(res.value))             else:         print("LevelOrder successor of " +               str(key.value) + " is NULL") 

Flatten a binary tree into linked list

#include <iostream> using namespace std;    struct Node {     int key;     Node *left, *right; }; Node* newNode(int key) {     Node* node = new Node;     node->key = key;     node->left = node->right = NULL;     return (node); }    void flatten(struct Node* root) {    if (root == NULL || root->left == NULL &&                         root->right == NULL) {         return;     }          if (root->left != NULL) {            flatten(root->left);               struct Node* tmpRight = root->right;         root->right = root->left;         root->left = NULL;              struct Node* t = root->right;         while (t->right != NULL) {             t = t->right;         }            t->right = tmpRight;     }     flatten(root->right); }    void inorder(struct Node* root) {     if (root == NULL)         return;     inorder(root->left);     cout << root->key << " ";     inorder(root->right); }    int main() {        Node* root = newNode(1);     root->left = newNode(2);     root->right = newNode(5);     root->left->left = newNode(3);     root->left->right = newNode(4);     root->right->right = newNode(6);        flatten(root);        cout << "The Inorder traversal after "             "flattening binary tree ";     inorder(root);     return 0; }

Check if a given tree graph is linear or not

import java.io.*; import java.util.*; class Graph {     private int V; // No. of vertices       private LinkedList<Integer> adj[];        Graph(int v)     {         V = v;         adj = new LinkedList[v];         for (int i = 0; i < v; ++i)             adj[i] = new LinkedList<Integer>();     }     void addEdge(int v, int w)     {         adj[v].add(w);         adj[w].add(v);     }                   boolean isLinear()     {              if (V == 1)             return true;         int count = 0;              for (int i = 0; i < V; i++) {             if (adj[i].size() == 2)                 count++;         }         if (count == V - 2)             return true;         else             return false;     }        public static void main(String args[])     {         Graph g1 = new Graph(3);         g1.addEdge(0, 1);         g1.addEdge(0, 2);         if (g1.isLinear())             System.out.println("YES");         else             System.out.println("NO");     } }

B tree

#include<iostream> using namespace std;    // A BTree node class BTreeNode {     int *keys;  // An array of keys     int t;      // Minimum degree (defines the range for number of keys)     BTreeNode **C; // An array of child pointers     int n;     // Current number of keys     bool leaf; // Is true when node is leaf. Otherwise false public:     BTreeNode(int _t, bool _leaf);   // Constructor        // A function to traverse all nodes in a subtree rooted with this node     void traverse();        // A function to search a key in the subtree rooted with this node.         BTreeNode *search(int k);   // returns NULL if k is not present.    // Make the BTree friend of this so that we can access private members of this // class in BTree functions friend class BTree; };    // A BTree class BTree {     BTreeNode *root; // Pointer to root node     int t;  // Minimum degree public:     // Constructor (Initializes tree as empty)     BTree(int _t)     {  root = NULL;  t = _t; }        // function to traverse the tree     void traverse()     {  if (root != NULL) root->traverse(); }        // function to search a key in this tree     BTreeNode* search(int k)     {  return (root == NULL)? NULL : root->search(k); } };    // Constructor for BTreeNode class BTreeNode::BTreeNode(int _t, bool _leaf) {     // Copy the given minimum degree and leaf property     t = _t;     leaf = _leaf;        // Allocate memory for maximum number of possible keys     // and child pointers     keys = new int[2*t-1];     C = new BTreeNode *[2*t];        // Initialize the number of keys as 0     n = 0; }    // Function to traverse all nodes in a subtree rooted with this node void BTreeNode::traverse() {     // There are n keys and n+1 children, travers through n keys     // and first n children     int i;     for (i = 0; i < n; i++)     {         // If this is not leaf, then before printing key[i],         // traverse the subtree rooted with child C[i].         if (leaf == false)             C[i]->traverse();         cout << " " << keys[i];     }        // Print the subtree rooted with last child     if (leaf == false)         C[i]->traverse(); }    // Function to search key k in subtree rooted with this node BTreeNode *BTreeNode::search(int k) {     // Find the first key greater than or equal to k     int i = 0;     while (i < n && k > keys[i])         i++;        // If the found key is equal to k, return this node     if (keys[i] == k)         return this;        // If the key is not found here and this is a leaf node     if (leaf == true)         return NULL;        // Go to the appropriate child     return C[i]->search(k); }

Insertion and deletion in b+ tree

Insertion: 1) Initialize x as root. 2) While x is not leaf, do following ..a) Find the child of x that is going to to be traversed next. Let the child be y. ..b) If y is not full, change x to point to y. ..c) If y is full, split it and change x to point to one of the two parts of y. If k is smaller than mid key in y, then set x as first part of y. Else second part of y. When we split y, we move a key from y to its parent x. 3) The loop in step 2 stops when x is leaf. x must have space for 1 extra key as we have been splitting all nodes in advance. So simply insert k to x. Deletion: Remove the required key and associated reference from the node. If the node still has enough keys and references to satisfy the invariants, stop. If the node has too few keys to satisfy the invariants, but its next oldest or next youngest sibling at the same level has more than necessary, distribute the keys between this node and the neighbor. Repair the keys in the level above to represent that these nodes now have a different “split point” between them; this involves simply changing a key in the levels above, without deletion or insertion. If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging. In either case, we will need to repeat the removal algorithm on the parent node to remove the “split key” that previously separated these merged nodes — unless the parent is the root and we are removing the final key from the root, in which case the merged node becomes the new root (and the tree has become one level shorter than before).

Linked list

#include <stdio.h> #include <stdlib.h>    // A linked list node struct Node {   int data;   struct Node *next; };    /* Given a reference (pointer to pointer) to the head of a list and     an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) {     /* 1. allocate node */     struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));        /* 2. put in the data  */     new_node->data  = new_data;        /* 3. Make next of new node as head */     new_node->next = (*head_ref);        /* 4. move the head to point to the new node */     (*head_ref)    = new_node; }    /* Given a node prev_node, insert a new node after the given     prev_node */ void insertAfter(struct Node* prev_node, int new_data) {     /*1. check if the given prev_node is NULL */     if (prev_node == NULL)     {       printf("the given previous node cannot be NULL");       return;     }        /* 2. allocate new node */     struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));        /* 3. put in the data  */     new_node->data  = new_data;        /* 4. Make next of new node as next of prev_node */     new_node->next = prev_node->next;        /* 5. move the next of prev_node as new_node */     prev_node->next = new_node; }    /* Given a reference (pointer to pointer) to the head    of a list and an int, appends a new node at the end  */ void append(struct Node** head_ref, int new_data) {     /* 1. allocate node */     struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));        struct Node *last = *head_ref;  /* used in step 5*/        /* 2. put in the data  */     new_node->data  = new_data;        /* 3. This new node is going to be the last node, so make next of           it as NULL*/     new_node->next = NULL;        /* 4. If the Linked List is empty, then make the new node as head */     if (*head_ref == NULL)     {        *head_ref = new_node;        return;     }        /* 5. Else traverse till the last node */     while (last->next != NULL)         last = last->next;        /* 6. Change the next of last node */     last->next = new_node;     return; }    // This function prints contents of linked list starting from head void printList(struct Node *node) {   while (node != NULL)   {      printf(" %d ", node->data);      node = node->next;   } }    /* Driver program to test above functions*/ int main() {   /* Start with the empty list */   struct Node* head = NULL;      // Insert 6.  So linked list becomes 6->NULL   append(&head, 6);      // Insert 7 at the beginning. So linked list becomes 7->6->NULL   push(&head, 7);      // Insert 1 at the beginning. So linked list becomes 1->7->6->NULL   push(&head, 1);      // Insert 4 at the end. So linked list becomes 1->7->6->4->NULL   append(&head, 4);      // Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL   insertAfter(head->next, 8);      printf("\n Created Linked list is: ");   printList(head);      return 0; }