Homework #2 Solution

Homework should be submitted via Moodle in PDF, or plain text. To avoid reduced marks, please submit word/latex-formated PDF file, NOT scanned writing in pdf format. All assignments are due on 9 PM of the due date. Late homework will be accepted only in circumstances that are grounds for excused absence under university policy. The university provides mechanisms for documenting such reasons (severe illness, death in the family, etc.). Arrangements for turning in late homework must be made by the day preceding the due date if possible.




All assignments for this course are intended to be individual work. Turning in an assignment which is not your own work is cheating. The Internet is not an allowed resource! Copying of text, code or other content from the Internet (or other sources) is plagiarism. Any tool/resource must be approved in advance by the instructor and identified and acknowledged clearly in any work turned in, anything else is plagiarism.




If an academic integrity violation occurs, the offending student(s) will be assessed a penalty that is at least as severe as getting a 0 for the whole homework for which the violation occurred, and the case will be reported to the Office of Student Conduct.




Instructions about how to “give/describe” an algorithm (taken from Erik Demaine): Try to be concise, correct, and complete. To avoid deductions, you should provide (1) a textual description of the algorithm, and, if helpful, flow charts and pseudocode; (2) at least one worked example or diagram to illustrate how your algorithm works; (3) a proof (or other indication) of the correctness of the algorithm; and (4) an analysis of the time complexity (and, if relevant, the space complexity) of the algorithm. Remember that, above all else, your goal is to communicate. If a grader cannot understand your solution, they cannot give you appropriate credit for it.




1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms, implement an algorithm. In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1 cent.

a) (4 points) Give a recursive algorithm that generates a similar series of coins for changing n cents. Don’t use dynamic programming for this problem.




b) (4 points) Write an O(1) (non-recursive!) algorithm to compute the number of returned coins.




c) (1 point) Show that the above greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, and 10 cents.




d) (6 points) Given a set of arbitrary denominations C =(c1,...,cd), describe an algorithm that uses dynamic programming to compute the minimum number of coins required for making change. You may assume that C contains 1 cent, that all denomination are different, and that the denominations occur in in increasing order.




e) (5 points) Implement the algorithm described in d). We will use the AutoGradr site (https://app.autogradr.com/) for grading your programs. Instructions for signing up at the site and submitting the programming task are given at the bottom of this assignment.




2. Purpose: Practice solving recurrences. For each of the following recurrences, use the Master Theorem to derive asymptotic bounds for T(n), or argue why the Master Theorem does not apply. If not explicitly stated, please assume that small instances need constant time c. Justify your answers, ie. give the values of a, b, n^log_b(a) f, , for case 3 of the Master Theorem show that the regularity condition is satisfied. (3 points each)

(a) T(n) = 2T(n/2) + n3 if n is an even integer; 2T(n/2) + n2 if n is an odd integer.

(b) T(n)= 2T (n/4)+ n0.51.

(c) 2nT (n/2) + nn.

(d) T (n) = 3T (n/2)+ n2.

(e) T(n) = T(5n/6) + 1.




3. Purpose: Practice solving recurrences. Please solve the following recurrences. (3 points each)

a) Assume a1. T(0)=…=T(3)=1, T(n) = aT(n/4), otherwise. Give the exact solution for T(n). Justify your answer.




b) Assume c1. T(8)=…=T(0)=c, T(n) = 3T(n-2) otherwise. Give the exact solution and the asymptotic big-theta bound for T(n). Justify your answers.




c) T(0)=0, T(n) = T(n-1)+1+1/n otherwise. Give the exact solution and the asymptotic big-theta bound for T(n). Justify your answers.







4. Purpose: Often, recursive function calls use up precious stack space and might lead to stack overflow errors. Tail call optimization is one method to avoid this problem by replacing certain recursive calls with an iterative control structure. Learn how this technique can be applied to QUICKSORT. (2 points each) Solve Problem 7-4, a-c on page 188 of our textbook.




5. (5 points) Purpose: Practice algorithm design and the use of data structures. This problem was an interview question! Consider a situation where your data is almost sorted—for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. To simplify this problem assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order and uses only a constant amount of storage, i.e., the memory used should be independent of the number of time-stamps processed. Tip: solve the problem using a heap.




Instructions for signing up at the AutoGradr site (https://app.autogradr.com/) and submitting the programming task:




First, open an account in the site as a student using your NCSU email address. Also, in the ‘name’ field, instead of using your full name, use your unity ID. You will have to activate your account from your email. This step is crucial. We will un-enroll any student with a non-NCSU-email-address from our course created in the site.




Second, use the following code, “T7ZRGE”, without the quotation marks to enroll in the course named “CSC 505 Fall 2018 NCSU.” This step is also crucial. Our programming questions will be posted in this course.




Third, for the programming problem in homework 2, please submit your code in the “Homework 2: Coin Change” project posted in the course. Please follow the following instructions:

You can find the detailed description of the problem in the site, including input and output specifications, limits, and formatting. Some test cases are made visible to you as samples. The other test cases are hidden. Your program will run against each test case automatically, and you will receive an instant feedback on how many test cases you have passed. Usually, the percentage of passed test cases will be proportional to your grade in this question. We may cut off some marks for poorly written codes. The time limit is set sufficiently high, so you do not need to worry so long as you have correctly implemented a dynamic-programming-based solution with the expected time complexity.
Supported languages are: C++ 11, Python 2.7, Python 3, and Java 8. Use the following naming convention for your main file:

C++ 11: main.cpp
Python 2.7/3: main.py
Java 8: Main.java, with a public class named Main
You may submit a single file containing your code, or you may submit a zip file with the main file at the top-level. We encourage you to submit a single file to avoid complications.
Whichever language you use, you need to write code to read in a single test case from the console and write the corresponding solution for that test case to the console, maintaining the exact format specified in the problem statement and illustrated in the sample test cases. Note that the formatting is very important. An incorrectly formatted output might not receive any marks.
Submit early to avoid heavy load and complications on the site at the deadline. You may make as many attempts as you wish. However, the site will record only the very last attempt, not a submission history. So, make sure your last submission is the correct one and is submitted before the deadline. A submission past due date will be accepted by the site but we will apply penalties as per our general course policy.
You will not receive marks for your program if you fail to follow the above instructions.
Above all else, get familiar with the environment. It is your responsibility to ensure that your code correctly passes the test cases to receive marks. A piazza post will repeat the instructions. Feel free to discuss any issue you face.