Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Assn1 29 9 17

    Uploaded by

    lltv tv
    The document provides instructions for 5 assignments related to data structures and algorithms: 1. Dry run the provided radix sort source code. 2. Modify binary search to return the greatest value less than the search key K if K is not present. 3. Analyze timing data and determine algorithm complexities: a) O(n^2) and b) O(n). 4. Implement and time sequential and binary search on arrays of increasing size n to determine crossover point. 5. Implement bubble sort and graph run times for small, medium, and large n values.

    Copyright:

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

    Assn1 29 9 17

    Uploaded by

    lltv tv
    15 views3 pages
    The document provides instructions for 5 assignments related to data structures and algorithms: 1. Dry run the provided radix sort source code. 2. Modify binary search to return the greatest value less than the search key K if K is not present. 3. Analyze timing data and determine algorithm complexities: a) O(n^2) and b) O(n). 4. Implement and time sequential and binary search on arrays of increasing size n to determine crossover point. 5. Implement bubble sort and graph run times for small, medium, and large n values.

    Original Title

    assn1-29-9-17

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides instructions for 5 assignments related to data structures and algorithms: 1. Dry run the provided radix sort source code. 2. Modify binary search to return the greatest value less than the search key K if K is not present. 3. Analyze timing data and determine algorithm complexities: a) O(n^2) and b) O(n). 4. Implement and time sequential and binary search on arrays of increasing size n to determine crossover point. 5. Implement bubble sort and graph run times for small, medium, and large n values.

    Copyright:

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

    Assn1 29 9 17

    Uploaded by

    lltv tv
    The document provides instructions for 5 assignments related to data structures and algorithms: 1. Dry run the provided radix sort source code. 2. Modify binary search to return the greatest value less than the search key K if K is not present. 3. Analyze timing data and determine algorithm complexities: a) O(n^2) and b) O(n). 4. Implement and time sequential and binary search on arrays of increasing size n to determine crossover point. 5. Implement bubble sort and graph run times for small, medium, and large n values.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 3

    Data Structures and Algorithms

    Assignment No. 1
    Due Date: Thursday 5th October 2017

    1. Given below is the source code of radix sort. Dry run the following source code as
    discussed in the lecture:

    //Radix Sort:
    #include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>

    typedef unsigned uint;


    #define swap(a, b) { tmp = a; a = b; b = tmp; }
    #define each(i, x) for (i = 0; i < x; i++)

    /* sort unsigned ints */


    static void rad_sort_u(uint *from, uint *to, uint bit)
    {
    if (!bit || to < from + 1) return;

    uint *ll = from, *rr = to - 1, tmp;


    while (1) {
    /* find left most with bit, and right most without bit, swap
    */
    while (ll < rr && !(*ll & bit)) ll++;
    while (ll < rr && (*rr & bit)) rr--;
    if (ll >= rr) break;
    swap(*ll, *rr);
    }

    if (!(bit & *ll) && ll < to) ll++;


    bit >>= 1;

    rad_sort_u(from, ll, bit);


    rad_sort_u(ll, to, bit);
    }
    /* sort signed ints: flip highest bit, sort as unsigned, flip back */
    static void radix_sort(int *a, const size_t len)
    {
    size_t i;
    uint *x = (uint*) a;

    each(i, len) x[i] ^= INT_MIN;


    rad_sort_u(x, x + len, INT_MIN);
    each(i, len) x[i] ^= INT_MIN;
    }

    static inline void radix_sort_unsigned(uint *a, const size_t len)


    {
    rad_sort_u(a, a + len, (uint)INT_MIN);
    }

    int main(void)
    {
    int len = 16, x[16], i;
    // size_t len = 16, i;
    each(i, len) x[i] = rand() % 512 - 256;

    radix_sort(x, len);

    each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n');

    return 0;
    }

    2. Given an array storing integers ordered by value, modify the binary search algorithm to return
    the position of the integer with the greatest value less than K(K is the key to be searched) when
    K itself does not appear in the array. Return ERROR if the least value in the array is greater than
    K.
    3. The following run times were obtained when using two different algorithms on a data set of size
    n. Based on this timing data, guess the complexity of each algorithm as a function of n. Use big-
    O notation in its simplest form and briefly explain how you reached your conclusion.

    (a) n Execution Time (in seconds)

    1000 0.743

    2000 3.021

    4000 12.184
    8000 50.320

    (b) n Execution Time (in microseconds or millionths of a second)

    1000 0.01

    1000000 20

    1000000000 30000

    4. Implement sequential search and binary search algorithms on your computer. Run timings for
    each algorithm on arrays of size n = 10 i for i ranging from 1 to as large a value as your
    computer’s memory/compiler will allow. For both algorithms, store the values 0 through n - 1 in
    order in the array, and use a variety of random search values in the range 0 to n - 1 on each size
    n. Graph the resulting times. When is sequential search faster than binary search for a sorted
    array?

    5. Implement bubble sort in C/C++. Graph the resulting running times for small, medium and
    then the largest value of n.

    *****

    You might also like