1st Lecture - BSCS 3 - Data Structure Lab

JAVA 10

1st Lecture - BSCS 3 - Data Structure Lab Guest on 28th September 2020 03:47:28 PM

Big O Notation - Determines the efficiency of the program.
Amount of execution is directly proportional to the time it takes to run the program.
For example, if there is a loop in program, it depends on how long the loop runs.
0(n)
Big O - depends on inputs
In case of two nested loops, n ~ 2 will be used - ALWAYS HAVE QUADRATIC GRAPHS
In case of three nested loops, n ~ 3 will be used - ALWAYS HAVE QUADRATIC GRAPHS
In case of multiple loops, 2n will be used for Big O Notation. Inputs MUST BE SAME EVERYTIME - LINEAR GRAPHS IN NORMAL
Based on the graphs, Quadratic graphs perform it more faster than Linear graphs.
Dynamic Arrays - Expand the size of an array
Best Case - the best part of the code
Code done in class:
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
// Assignment - Extend the array and find the largest number in array
ArrayDS array = new ArrayDS(3);
array.insert(1);
array.insert(2);
array.insert(3);
array.insert(4);
array.insert(20);
array.insert(50);
//array.removeAt(1);
//array.insert(3);
System.out.println("Index Of 2 ="+array.indexOf(2));
array.size();
array.print();
System.out.println("The largest number in an array is: "+array.largestNumber());
}
}
// CLASS ARRAYDS
package com.company;
public class ArrayDS {
private int[] items;
private int count;
public ArrayDS(int length){
items = new int[length];
}
public void print(){
for (int i=0;i<count;i++){
System.out.println(items[i]);
}
}
// Doubling the array size when array size exceeds
public void insert(int item){
if(items.length == count){
int[] newItems = new int[count*2];
for (int i=0;i<count;i++){
newItems[i] = items[i];
}
items = newItems;
}
items[count++] = item;
}
public void size(){
System.out.println("Size of an array: "+items.length);
}
public void removeAt(int index){ // index 1
if (index<0 || index >=count){
throw new IllegalArgumentException();
}
for (int i=index;i<count;i++){ // i=1
items[i] = items[i+1];
}
count--;
}
public int indexOf(int item){
for (int i=0;i<count;i++){
if(items[i] == item)
return i;
}
return -1;
}
public int largestNumber(){
int largest=0;
for (int i=0;i<count;i++){
if (items[i] > largest)
largest = items[i];
}
return largest;
}
}
Inside an array - to lookup o(1) - exact location
To insert o(n)
Delete o(1) in worst case.

Recent Pastes

Advanced Ethical[...]

Raw Paste

Big O Notation - Determines the efficiency of the program.

Amount of execution is directly proportional to the time it takes to run the program.

For example, if there is a loop in program, it depends on how long the loop runs.
0(n)

Big O - depends on inputs

In case of two nested loops, n ~ 2 will be used - ALWAYS HAVE QUADRATIC GRAPHS
In case of three nested loops, n ~ 3 will be used - ALWAYS HAVE QUADRATIC GRAPHS
In case of multiple loops, 2n will be used for Big O Notation. Inputs MUST BE SAME EVERYTIME - LINEAR GRAPHS IN NORMAL

Based on the graphs, Quadratic graphs perform it more faster than Linear graphs.

Dynamic Arrays - Expand the size of an array

Best Case - the best part of the code

Code done in class:
package com.company;

public class Main {

public static void main(String[] args) {
	// write your code here
        // Assignment - Extend the array and find the largest number in array
ArrayDS array = new ArrayDS(3);
array.insert(1);
array.insert(2);
array.insert(3);
        array.insert(4);
        array.insert(20);
        array.insert(50);
//array.removeAt(1);
//array.insert(3);
        System.out.println("Index Of 2 ="+array.indexOf(2));
        array.size();
array.print();
        System.out.println("The largest number in an array is: "+array.largestNumber());
    }
}

!highlight!// CLASS ARRAYDS

package com.company;

public class ArrayDS {
    private int[] items;
    private int count;

public ArrayDS(int length){
        items = new int[length];
    }

public void print(){
        for (int i=0;i<count;i++){
            System.out.println(items[i]);
        }
    }
// Doubling the array size when array size exceeds
    public void insert(int item){
        if(items.length == count){
            int[] newItems = new int[count*2];
            for (int i=0;i<count;i++){
                newItems[i] = items[i];
            }
            items = newItems;
        }
        items[count++] = item;
    }

public void size(){
    System.out.println("Size of an array: "+items.length);
}

public void removeAt(int index){ // index 1
        if (index<0 || index >=count){
            throw new IllegalArgumentException();
        }
        for (int i=index;i<count;i++){ // i=1
            items[i] = items[i+1];
        }
        count--;
}

public int indexOf(int item){
        for (int i=0;i<count;i++){
            if(items[i] == item)
                return i;
    }
        return -1;
}

public int largestNumber(){
        int largest=0;
        for (int i=0;i<count;i++){
            if (items[i] > largest)
                largest = items[i];
        }
        return largest;
}

}

Inside an array - to lookup o(1) - exact location
To insert o(n)
Delete o(1) in worst case.