DSA

DSA 2018

August 5, 2021BIM NotesLeave a Comment

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

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

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.");
      }
    }
  }

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

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

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

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

}

DSA 2019 Makeup

August 5, 2021BIM NotesLeave a Comment

Group B Q.No 11.

package folder2019;
import java.util.Scanner;
class Stack {
    private java.util.LinkedList list = new java.util.LinkedList();
    public Stack() {
    }
    public void clear() {
        list.clear();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void push(Object el) {
        list.addLast(el);
    }
    public Object pop() {
        if (isEmpty()) {
            System.out.println("stack is empty");
        }
        return list.removeLast();
    }
    public String toString() {
        return list.toString();
    }
}
public class makeup2019no11 {
    public static void main(String[] args) {
        Stack ob = new Stack();
        int data;
        Scanner sc = new Scanner(System.in);
        ob.clear();
        System.out.println("the stack is empty:" + ob.isEmpty());
        System.out.println("enter a number to push in any stack");
        for (int i = 0; i < 3; i++) {
            data = sc.nextInt();
            ob.push(data);
        }
        ob.pop();
    }
}

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

package folder2019;

import java.util.Scanner;

class Stack {

private java.util.LinkedList list = new java.util.LinkedList();

public Stack() {

}

public void clear() {

list.clear();

}

public boolean isEmpty() {

return list.isEmpty();

}

public void push(Object el) {

list.addLast(el);

}

public Object pop() {

if (isEmpty()) {

System.out.println("stack is empty");

}

return list.removeLast();

}

public String toString() {

return list.toString();

}

public class makeup2019no11 {

public static void main(String[] args) {

Stack ob = new Stack();

int data;

Scanner sc = new Scanner(System.in);

ob.clear();

System.out.println("the stack is empty:" + ob.isEmpty());

System.out.println("enter a number to push in any stack");

for (int i = 0; i < 3; i++) {

data = sc.nextInt();

ob.push(data);

}

ob.pop();

}

Q.no 12

package folder2019;
import java.util.Scanner;
class Node
{
public int info;
 public Node next;
 public Node()
 {
 next = null;
 }
 public Node(int el)
{
 info = el;
 next = null;
 }
 public Node(int el, Node ptr)
{
 info =el;
 next = ptr;
 }
}
class List{
    Node head,tail;
public void deleteAtAny(int n)
{
Node previous = head;
int count=1, position=n;
while(count < position - 1)
{
previous = previous.next;
count++;
}
Node current = previous.next;
previous.next = current.next;
current.next = null;
}
}
public class makeup2019no12{
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Singly linked list created");
        List mylist = new List();
        System.out.println("Enter the position");
        int pos=sc.nextInt();
        mylist.deleteAtAny(pos);
    }
}

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

package folder2019;

import java.util.Scanner;

class Node

{

public int info;

public Node next;

public Node()

{

next = null;

}

public Node(int el)

{

info = el;

next = null;

}

public Node(int el, Node ptr)

{

info =el;

next = ptr;

}

class List{

Node head,tail;

public void deleteAtAny(int n)

{

Node previous = head;

int count=1, position=n;

while(count < position - 1)

{

previous = previous.next;

count++;

}

Node current = previous.next;

previous.next = current.next;

current.next = null;

}

public class makeup2019no12{

public static void main(String args[]) {

Scanner sc=new Scanner(System.in);

System.out.println("Singly linked list created");

List mylist = new List();

System.out.println("Enter the position");

int pos=sc.nextInt();

mylist.deleteAtAny(pos);

}

Q.n0 13 Q.no 14 Q.no 15

import java.util.Scanner;
public class SelectionSorting {
    public static void selectionSort(int[] data){
       int i,j,least,temp;
       for(i=0;i<data.length-1;i++){
           for(j=i+1,least=i; j<data.length;j++){
                if(data[j]<data[least])
                    least=j;
           }
                if(i!=least){
                        temp=data[least];
                        data[least]=data[i];
                        data[i]=temp;
                }
           }
        }
    static void result(int[] data){
         System.out.println("The array after selection sorting is: ");
        for(int i=0;i<data.length;i++)
            System.out.print(data[i]+ " ");
    }
    public static void main(String args[]){
        SelectionSorting obj1 =new SelectionSorting ();
        Scanner sc=new Scanner(System.in);
        System.out.println("enter the size of array for sorting");
        int size=sc.nextInt();
        System.out.println("Enter the element for array");
         int data[]=new int[size];
        for(int i=0;i<size;i++){
             data[i]=sc.nextInt();
        }
        selectionSort(data);
        result(data);
    }
}

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

import java.util.Scanner;

public class SelectionSorting {

public static void selectionSort(int[] data){

int i,j,least,temp;

for(i=0;i<data.length-1;i++){

for(j=i+1,least=i; j<data.length;j++){

if(data[j]<data[least])

least=j;

}

if(i!=least){

temp=data[least];

data[least]=data[i];

data[i]=temp;

}

static void result(int[] data){

System.out.println("The array after selection sorting is: ");

for(int i=0;i<data.length;i++)

System.out.print(data[i]+ " ");

}

public static void main(String args[]){

SelectionSorting obj1 =new SelectionSorting ();

Scanner sc=new Scanner(System.in);

System.out.println("enter the size of array for sorting");

int size=sc.nextInt();

System.out.println("Enter the element for array");

int data[]=new int[size];

for(int i=0;i<size;i++){

data[i]=sc.nextInt();

}

selectionSort(data);

result(data);

}

DSA 2019

August 5, 2021BIM NotesLeave a Comment

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

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

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

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

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;

1

2

3

4

5

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. […]

DSA Pre board Solution

August 20, 2019BIM Notes

Asian School of Management and Technology How queue can be considered as an ADT? An ADT is a set of value, well defined set of properties of values and set of operation needed for the processing of these values. A queue can be expressed as an ADT as : Values: order list and item. Properties: […]

Unit 5 : Part 3 Heap

September 11, 2018BIM Notes

> > >

Unit-4 Recursion

August 24, 2018BIM Notes

Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. In order to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second, the problem statement must include a stopping condition. Factorial Program using loop in […]

DSA 2015

August 24, 2018BIM Notes

DSA || 2017 Solution

August 23, 2018BIM Notes

Unit-5 Binary Trees

August 15, 2018BIM Notes

Binary tree AVL Tree Heap

Array

June 17, 2018BIM Notes

Sorting an Array Ordering data in an increasing or decreasing fashion. 1) Sort: Sorting an index array in ascending order. <?php $num=array(2,5,3,4,1); sort($num); $length=count($num); for($i=0;$i<$length;$i++) { echo $num[$i]; echo “<br>”; } ?> 2) rsort: Sorting an index array in descending order. <?php $num=array(2,5,3,4,1); rsort($num); $length=count($num); for($i=0;$i<$length;$i++) { echo $num[$i]; echo “<br>”; } ?> 3) asort: […]