DSA 2019

4th semester





DSA year 2019

Group A

  1. A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front
  2. Big-O notation is the language we use for talking about how long an algorithm takes to run (time complexity) or how much memory is used by an algorithm (space complexity). Big-O notation can express the best, worst, and average-case running time of an algorithm.
  3. Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.
  4. The skip list is a probabilisitc data structure that is built upon the general idea of a linked The skip list uses probability to build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer elements, but no new elements.
  5. B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red-Black Trees).
  6. The breadth first traversal visits and processes nodes at every level before moving on to the next
  7. linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. … In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
  8. The main advantage of using binary search is that it does not scan each element in the list. Instead of scanning each element, it performs the searching to the half of the list. So, the binary search takes less time to search an element as compared to a linear searc
  9. In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
  10. AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

 





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;
    }
}
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();
    }
}

Q.No 12

package folder2019;
import java.util.Scanner;
class DCLNode{
    int info;
    DCLNode previous;
    DCLNode next;
    DCLNode(int el){
        this.info=el;
        this.previous=null;
        this.next=null;
    }
    DCLNode(int el,DCLNode next,DCLNode previous){
        this.info=el;
        this.previous=previous;
        this.next=next;
    }
}
class DLList{
    public DCLNode head,tail;
    DLList(){
        head=tail=null;
    }
    public boolean isEmpty(){
        return head==null && tail==null;
    }
    public void insertattail(int el){
        if(isEmpty()){
            head=tail=new DCLNode(el);
            head.previous=tail;
            tail.next=head;
        }
       else{
           tail=new DCLNode(el,head,tail);
           tail.previous.next=tail;
            head.previous=tail;
        }
        }
    }
public class no12 {
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        DLList ob=new DLList();
        ob.insertattail(5);
  ob.insertattail(6);
    }
}

Q.no 13

Q.no 14

KurskalAlgorith(weighted connected undirected graph)
		tree=null;
		edges=sequence of all edges of graph sorted by weight;
		for(i=1;i<= |E| and |tree| < |V| -1;i++)
			if ei  from edges does not form a cycle with edges in tree add ei  to tree;




Q.no 15

The topological sorting for a directed acyclic graph is the linear ordering of vertices. For every edge U-V of a directed graph, the vertex u will come before vertex v in the ordering. Topological sorting is only possible on DAG. Eg:





Leave a Reply

Your email address will not be published.