12 Days of Xmas

Assignment 1
Note: you will demo your xmas project in class.

Objective: Understanding of efficient algorithmic thinking and analysis.

Assignments from Book: Do the following problems from the Cormen book:

• 1.2-2 - Suppose we are comparing implementations of insertion sort and merge sort on the same machine.  For inputs of size n, insertion sort runs in 8n² steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? How might one rewrite the merge sort  to make it even faster on small inputs?

• Consider a linear search.  How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array?  how about in the worst case?   Justify your asnwers.

• 2.2-2 - Express the function n³/1000 - 100n² - 100n + 3 in terms of Θ notation.

• 2.1-1 - Using the figure from the book as a model, illustrate the operation of merge sort on the array A = <3, 41, 52, 26, 38, 57, 9, 49>.

• 1-1 - For each function f(n) and time t in the following table,  determine the largest size of n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.  A hint to help you out:  f(n) = t, with t in milliseconds.  For example, when t = 1 second, cand f(n) = n² then,  n² = 1000, so n is the square root of 1000 (~31.62).. This means given an n² algorithm, you could only operate on 31 values! 

Program Description: In this assignment, you will create a program to calculate the total number of gifts received on the n^th day of xmas - a cumulative total - according to the song "The Twelve Days of Xmas":

1. Partridge in a pear tree

2. Turtle doves

3. French hens

4. Calling birds

5. Golden rings

6. Geese a-laying

7. Swans a-swimming

8. Maids a-milking

9. Pipers playing

10. Drummers drumming

11. Ladies dancing

12. Twelve lords a-leaping

So, on the first day of xmas, you receive only 1 gift - the partridge.  On the second day, however, you receive 3 gifts (2 turtle doves and a partridge), creating a total on the second day of 4.  Your job is to calculate the total number on day n.  This day can be well beyond 12 - so you can't hardcode that day 1 is 1, day 2 is 4, etc...  Note: you should not print out the song, just the total.

In addition to writing this program, you will analyze the efficiency of your program in terms of  either Θ, Ο,  Ω, explaining why you believe your program runs within the bounds you claim.  Can this problem be solved in Ο (nⁿ), Ο (n²), Ο (n lg₂n), Ο (n), or even Ο (1)?  How many presents would you have if this continued all year?

Program Requirements: The program should prompt the user for the day to calculate, and then produce the total number of gifts since day 1.

Example: xmas.exe

Extra Credit:  10 pts extra credit to the person who comes up with the most efficient algorithm!

Program Turnin: Use WebSubmit to submit your written assignment.  You will show your code demo your program in front of the class, explaining your answer.