DSA 2018

4th semester

Group A

 

  1. A data structure is a collection of different forms and different types of data that has a set of specific operations that can be performed. It is a collection of data types. It is a way of organizing the items in terms of memory, and also the way of accessing each item through some defined logic.
Stacks Queues
Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.

 

  1. Doubly linked list allows element two way traversal. On other hand doubly linked list can be used to implement stacks as well as heaps and binary Singly linked list is preferred when we need to save memory and searching is not required as pointer of single index is stored.
  2. Recursion is much better than iteration for problems that can be broken down into multiple, smaller pieces. Precisely, in divide and conquer method using recursion can reduce your problem size at every step and would take less time than a naive iterative approach.
  3. a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.
  4. A multiway tree is a tree that can have more than two children. A multiway tree of order m (or an m-way tree) is one in which a tree can have m children.As with the other trees that have been studied, the nodes in an m-way tree will be made up of key fields, in this case m-1 key fields, and pointers to children.
  5. A weighted graph refers to one where weights are assigned to each edge. Weighted graphs can be represented in two ways: Directed graphs where the edges have arrows that show path direction. Undirected graphs where edges are bi-directional and have no arrows.
  6. Finite Graphs , , Infinite Graph , Trivial Graph: , Simple Graph , Multi Graph
  7. The tail recursion is basically using the recursive function as the last statement of the function. So when nothing is left to do after coming back from the recursive call, that is called tail recursion. We will see one example of tail recursion.
  8. Types of hash function :-Division method  ,Mid square method ,Digit folding method

Group B

Q.no 11

package folder2019;
import java.util.Scanner;
public class no11 {
    private int STACKSIZE;
    private Integer stack[];
    no11(int STACKSIZE) {
        this.STACKSIZE = STACKSIZE;
        stack = new Integer[this.STACKSIZE];
    }
    int TOP = -1;
    public void push(int data) {
        if (TOP == STACKSIZE - 1) {
            System.out.println("Stack overflow");
        } else {
            TOP++;
            stack[TOP] = data;
        }
    }
    public int pop() {
        if (TOP == -1) {
            System.out.println("Stack underflow");
        } else {
            System.out.println("Item deleted" + stack[TOP]);
            TOP--;
        }
        return 0;
    }
public void view(){
if(TOP==-1){
    System.out.println("Stack empty");
}
else{
    for(int i=TOP;i>=0;i--){
        System.out.print(stack[i]+" ");
    }
    System.out.println("");
}
}
}
class StackUsingArray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter the size of stack");
        int STACKSIZE = sc.nextInt();
        no11 ob = new no11(STACKSIZE);
        int data;
        System.out.println("enter a number to push");
        for (int i = 0; i < STACKSIZE; i++) {
            data = sc.nextInt();
            ob.push(data);
        }
        ob.pop();
       ob.view();
    }
}

Q.no 12

//node structure
class Node {
    int data;
    Node next;
    Node prev;
};
class LinkedList {
  Node head;
  LinkedList(){
    head = null;
  }
//Inserts a new element at the given position
void push_at(int newElement, int position) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null;
    newNode.prev = null;
    if(position < 1) {
      System.out.print("\nposition should be >= 1.");
    } else if (position == 1) {
      newNode.next = head;
      head.prev = newNode;
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      for(int i = 1; i < position-1; i++) {
        if(temp != null) {
          temp = temp.next;
        }
      }
      if(temp != null) {
        newNode.next = temp.next;
        newNode.prev = temp;
        temp.next = newNode;
        if(newNode.next != null)
          newNode.next.prev = newNode;
      } else {
        System.out.print("\nThe previous node is null.");
      }
    }
  }

 



Q.no 13

Q.no 14

import java.util.Scanner;
public class Hashing {
    int tablesize;
    Integer[] arr;
    public Hashing(int tablesize)
    {
        this.tablesize=tablesize;
        arr=new Integer[tablesize];
    }
    public int hashfunction(int key)
    {
        return key%this.tablesize;
    }
    public boolean collision(int index)
    {
        return (arr[index]!=null);
    }
    public void inserthash(int key)
    {
        int index=hashfunction(key);
        int i=1;
        while(collision(index))
        {
            index=(hashfunction(key)+i)%this.tablesize;
            i++;
        }
        arr[index]=key;
    }
    public void printAll()
    {
        for (Integer var:arr
             ) {
            System.out.println(var);
        }
    }
}
class Hashdemo
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int arr[]={24,20,37,84,50,47,67,74,52,53};
         int size=arr.length;
        Hashing h=new Hashing(size);
        for(int i=0;i<size;i++){
                   h.inserthash(arr[i]);
        }
        h.printAll();
    }
}

Leave a Reply

Your email address will not be published.