Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    LAB1

    Uploaded by

    aleeyanarazi
    This document provides examples of Big O notation for various algorithms and tasks, including: - Shaking hands with people at a party is O(n) - Riding an elevator from the ground floor to the nth floor is O(n) - Displaying integers in an array in reverse order is O(n) - Comparing elements in an array to find the smallest is O(n) - A string comparison algorithm is O(1) - Printing a string twice for each element in an array is O(n) - A switch statement contains cases that are either O(n) or O(n^2) depending on the operation It also provides programming tasks to analyze algorithms

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    LAB1

    Uploaded by

    aleeyanarazi
    13 views3 pages
    This document provides examples of Big O notation for various algorithms and tasks, including: - Shaking hands with people at a party is O(n) - Riding an elevator from the ground floor to the nth floor is O(n) - Displaying integers in an array in reverse order is O(n) - Comparing elements in an array to find the smallest is O(n) - A string comparison algorithm is O(1) - Printing a string twice for each element in an array is O(n) - A switch statement contains cases that are either O(n) or O(n^2) depending on the operation It also provides programming tasks to analyze algorithms

    Original Title

    LAB1 (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides examples of Big O notation for various algorithms and tasks, including: - Shaking hands with people at a party is O(n) - Riding an elevator from the ground floor to the nth floor is O(n) - Displaying integers in an array in reverse order is O(n) - Comparing elements in an array to find the smallest is O(n) - A string comparison algorithm is O(1) - Printing a string twice for each element in an array is O(n) - A switch statement contains cases that are either O(n) or O(n^2) depending on the operation It also provides programming tasks to analyze algorithms

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views3 pages

    LAB1

    Uploaded by

    aleeyanarazi
    This document provides examples of Big O notation for various algorithms and tasks, including: - Shaking hands with people at a party is O(n) - Riding an elevator from the ground floor to the nth floor is O(n) - Displaying integers in an array in reverse order is O(n) - Comparing elements in an array to find the smallest is O(n) - A string comparison algorithm is O(1) - Printing a string twice for each element in an array is O(n) - A switch statement contains cases that are either O(n) or O(n^2) depending on the operation It also provides programming tasks to analyze algorithms

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    LAB & TUTORIAL 1 SKJ2023

    TUTORIAL

    1. Using the Big Oh Notation, indicate the time requirement of each of the following tasks in the
    worst case. Describe any assumption that you make.
    a. After arriving at a party, you shake hands with each person there.
    b. Each person in a room shakes hands with everyone else in the room.
    c. You climb a flight of stairs.
    d. You slide down the banister.
    e. After entering an elevator, you press a button to choose a floor.
    f. You ride the elevator from the ground floor up to the nth floor.
    g. Display all the integers in an array of integers in reverse order.
    h. Display all the integers in a chain of linked nodes in reverse order.
    i. Display the nth integers in an array of integers from end.
    j. Compute the sum of the first n even integers in a chain of linked nodes.

    2. For each of the following codes, find the Big Oh for the following pseudocode algorithm
    a) int CompareSmallestNumber (int array[ ])
    {
    int x, curMin;

    // set smallest value to first item in array


    curMin = array[0];
    /* iterate through array to find smallest value and also assume there are only 10
    elements*/
    for (x = 1; x < 10; x++)
    {
    if( array[x] < curMin) {
    curMin = array[x];
    }
    }

    // return smallest value in the array


    return curMin;
    }
    b. int CompareToAllNumbers (int array[ ])
    {
    bool isMin;
    int x, y;

    /* iterate through each element in array, assuming there are only 10 elements*/

    for (int x = 0; x < 10; x++)


    {
    isMin = true;
    for (int y = 0; y < 10; y++)
    {
    /* compare the value in array[x] to the other values if we find that array[x] is greater
    than any of the values in array[y] then we know that the value in array[x] is not the
    minimum . Remember that the 2 arrays are exactly the same, we are just taking
    out one value with index 'x' and comparing to the other values in the array with
    index 'y' */

    if( array[x] > array[y])


    isMin = false;
    }
    if(isMin)
    break;
    }
    return array[x];
    }

    c. Boolean IsStringHello (String string)

    {
    if(string.equal(“Hello”)
    {return true;}

    return false;

    d. void printJimmyTwice (int array[])

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

    System.out.println(”Jimmy One”);

    for(int i=0; i<array.size(); i++)

    System.out.println(”Jimmy Two”);

    }
    e. char key;

    int[] X = new int[n];

    int[][] Y = new int[n][n];

    ........

    switch(key) {

    case 'a':

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

    sum += X[i];

    break;

    case 'b':

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

    for(int j = 0; j < Y[0].length; j++)

    sum += Y[i][j];

    break;

    } // End of switch block

    PROGRAMMING TASK

    1. Three algorithms for computing the sum 1 + 2 + .. + n for an integer n>0 are as follow:
    Algorithm A Algorithm B Algorithm C
    sum = 0 sum= 0 sum = n * (n + 1) /2
    for i=1 to n for i=1 to n
    sum=sum+ i {
    for j=1 to i
    sum = sum + 1
    }

    a. Translate these algorithms into Java codes and calculate the time taken to run for
    each algorithms when n = 1000, n= 100,000 and n = 1,000,000.
    b. What can you conclude for these 3 algorithms?

    2. Consider the following two loops:


    //Loop A
    for (i=1; i<=n;i++)
    for(j=1; j<=10000;j++)
    sum= sum+j;

    //Loop B
    for (i=1; i<=n;i++)
    for(j=1; j<=n;j++)
    sum= sum+j;

    Although Loop A is O(n) and Loop B is O(n2), Loop B can be faster than Loop A for small values
    of n. Design and implement an experiment to find a value of n for which Loop B is faster.

    You might also like