Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    HWK 1

    Uploaded by

    Priyaranjan Pandey
    This document outlines 5 problems for a homework assignment on algorithms. It provides instructions on collaboration, due dates, and measuring functions. The problems cover: 1) analyzing time complexities of functions, 2) solving recurrence relations, 3) improving a multiplication algorithm, 4) analyzing comparisons in insertion sort based on input order, and 5) attaching a photo.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PS, PDF, TXT or read online from Scribd

    HWK 1

    Uploaded by

    Priyaranjan Pandey
    25 views2 pages
    This document outlines 5 problems for a homework assignment on algorithms. It provides instructions on collaboration, due dates, and measuring functions. The problems cover: 1) analyzing time complexities of functions, 2) solving recurrence relations, 3) improving a multiplication algorithm, 4) analyzing comparisons in insertion sort based on input order, and 5) attaching a photo.

    Original Title

    hwk1

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PS, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines 5 problems for a homework assignment on algorithms. It provides instructions on collaboration, due dates, and measuring functions. The problems cover: 1) analyzing time complexities of functions, 2) solving recurrence relations, 3) improving a multiplication algorithm, 4) analyzing comparisons in insertion sort based on input order, and 5) attaching a photo.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PS, PDF, TXT or read online from Scribd
    Download as ps, pdf, or txt
    25 views2 pages

    HWK 1

    Uploaded by

    Priyaranjan Pandey
    This document outlines 5 problems for a homework assignment on algorithms. It provides instructions on collaboration, due dates, and measuring functions. The problems cover: 1) analyzing time complexities of functions, 2) solving recurrence relations, 3) improving a multiplication algorithm, 4) analyzing comparisons in insertion sort based on input order, and 5) attaching a photo.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PS, PDF, TXT or read online from Scribd
    Download as ps, pdf, or txt
    You are on page 1of 2

    15-451 Algorithms, Fall 2000

    Homework # 1 due: September 7, 2000


    Groundrules: You should try to do the assignment as much as possible by yourself. If you
    get stuck you may ask for help from friends or TAs or the instructors. In any event, you
    should do your writeup by yourself, in your own words. If you did get help from others,
    please list their names at the top of the rst page of your assignment. Your assignment is
    due at the beginning of class on the due date.
    Problems:
    1. For each pair ha; bi of functions below, indicate whether a = o(b), a = (b), or b = o(a):
    hn ln n; n log10 ni; hn log2(nc); n(log2 n)c i; hlog2 n; pni;
    h(log2 n)log n; nlog log ni; h2n ; 22n i; h2n ; n!i:
    2 2 2

    Give brief reasoning for each answer.


    2. Solve the following recurrences, giving your answer in  notation. For each of them,
    assume the base case T (x) = 1 for x  2. Show your work.
    (a) T (n) = 2T (n=5) + n.
    (b) T (n) = 2T (n 1) + 1.
    (c) T (n) = 2T (n 2) + 1.
    (d) T (n) = T (n 3) + n2.
    p p
    (e) T (n) = n T ( n) + n. (E.g., we might get this from ap divide-and-conquer
    procedure that uses linear time to break the problem into n pieces of size n
    p
    each. Hint: write out the recursion tree.)
    p
    (f) T (n) = 4T ( n) + (lg n)2. Hint: de ne a new function S (i) = T (2i).
    3. An improvement to multiplication method given in class involves splitting each n-bit
    number into three pieces of n=3 bits each (i.e., write X as 22n=3A+2n=3B +C and write Y
    as 22n=3D +2n=3 E + F ). A straightforward product would now involve 9 multiplications
    of n=3-bit numbers, but by cleverly rearranging terms, it is possible to reduce this to
    5 multiplications of n=3-bit numbers, plus a constant number of additions and shifts.
    Write down the recurrence that results, and solve it using  notation. (We are not
    asking you to come up with the algorithm for rearranging the terms.)

    1
    4. [Insertion Sort] Here is the C code for a sorting algorithm called insertion sort:
    void insertionsort(int a[], int n) {
    int i,j,v;

    for (i=1; i<n; i++) {


    v = a[i];
    for (j=i-1; j>=0; j--) {
    if (v >= a[j]) break;
    a[j+1] = a[j];
    }
    a[j+1] = v;
    }
    }

    Roughly speaking, this algorithm works by sorting the rst i 1 elements, then inserting
    the ith element where it belongs among the rst i 1. In this problem we'll consider
    the number of comparisions between elements as our measure of the running time of
    the algorithm. (This is the number of times the code v >= a[j] is executed.)
    (a) If the initial array consists of n distinct elements in decreasing order, how many
    comparisons are done? Justify your answer.
    (b) If the initial array consists of n distinct elements in increasing (sorted) order, how
    many comparisons are done? Justify your answer.
    It turns out that if the array is \mostly" sorted then insertion sort also does well.
    Call a pair of indices hi; j i an inversion in an array A = (a0; : : : ; an 1) if i < j but
    ai > aj .
    (c) Let C be the number of comparisons used to sort an array A. Let I be the number
    of inversions in A. Prove that:
    I C n 1+I
    5. Attach a photo of yourself to your handin, or alternatively, write down the URL of a
    photo of yourself. Students not solving problem 5 may be subjected to spontaneous
    use of the instructor's digital camera at some point in the course.

    You might also like