ECS-222A HW1 Grading Notes Part A. FAQ ========= Q1: Why it took so long to get my HW1 back? A1: The number of students in this class is about 50. There are 5 problems in HW1. Hence, the total time of grading depends how much time I can spend for each problem in average. If I spend 10 minutes (just imagine how fast you can finish a problem, 10 minutes is usually a good estimate to grade it) for each problem, the total time would be 50*5*10=2500 minutes > 40 hours. It's just the grading time. I also have to do additional things such as printing your papers, sorting them in alphabetical order, recording your scores, write grading notes(your are reading it now), and so on. Hence, I would appreciate very much if you can not only email your papers via emails (to show you turn in your homework on time), but also print them out and put in the homework box later (can be at most 2-day late). That will save me lots of time printing 30 papers, dealing with "out of paper" and/or paper jam, and also stapling your papers. In the future, it is obviously that I cannot always spend 10 minutes per question, the time might be shorten as short as only 3~4 minutes when I am really busy. Hence, it is very possible that I grade your papers wrongly. Please read Q2 if you think this happens to you. Q2: I think TA wrongly graded my papers. What should I do? A1: There actually might be several cases. Before you come to talk to TA, please make sure that you have read and understood the solution first, and also make sure you have done everything TA requires for homework answers. (I'll mention them later) I am very sorry that I usually cannot put too many comments on your paper because of my time constraints. If a question mark or line or "wrong" on your paper makes you confused, please come to my office hours. I basically grade your papers based on the solution. When you think your solution is actually better, or the solution is actually wrong, please discuss it with Prof. Martel first. Please also remember to check if I summed your scores correctly or not. I basically try to be as generous as possible, but I still have some strict requirements which I will point out later in Part B. Please avoid arguing with me that you should get "one more" point. However, if you think I took off too many points, we can review it together again. By the way, please do not bother me with different grading problems in different times, we should try to solve them all together in one time. Part B. Strict requirements of your answers. (MUST READ) =========================================== 1. Do NOT copy answers from your classmates. 2. You cannot just put the answer only in your paper. You have to explain why !! Remember the class is "DESIGN and ANALYSIS of algorithms". You have to do both!! 3. Do not forget to double check your answers before you print and submit your homework. 4. Do not use an example to do the "proof". 5. Do not use plots to do the "proof". 6. Give pseudo-code for your algorithm. 7. Do not forget to initialize variables in your algorithm (pseudo-code). 8. Do not forget to give base cases when you show the recursion equation, or when you do mathematical induction. 9. If your answers are correct, but your reasoning is totally wrong, you still get no points. 10. Although you have 2 free late days, that does NOT imply you can turn in your homework at most 4-day late. The due date is still the same. See Part D. for further information in HW1. Part C. Statistics of HW1 =================== High: 94 Low: 61 Average: 78 .7 Median: 78 Standard deviation: 8 Part D. Remarks for each problem in HW1 =============================== P1. Since you are required to solve this problem with Shortest-Path Problem. You have explain how do you construct the graph. Whats do the nodes, and the edges mean. Since it is a graph problem, you'd better express your answers with n (number of nodes) and m (number of edges). You also need to address the time and space complexities for the algorithm and the construction of the graph. You can NOT just say something like "the time complexity is O(mlogn) when we use Dijkstra...", you also have to explain why we can use Dijkstra algorithm. Some of you give answers in n and L. However, you have to do it correctly. It's true that m is O(L) [again, you have to explain why]. The answer O(n+m) is the general answer. O(n+L) is also acceptable. P2. Many of you forgot to give base cases in the algorithm. P3. Many of you forgot to give base cases in the algorithm. You also have to be careful about the indices (i and j) in your algorithm. P4. Many of you forgot to give base cases in the algorithm. In (b), many of you use the wrong OPT. Some seemed to try to maximize time. For example, if your algorithm has something like OPT(i,j)+ti, that's definitely wrong. It should maximize # jobs can be done. Hence, you can not just use subset sum algorithm directly. You have to modify it slightly. P5. You should be careful and not abuse Big-O notation. You should know when to use Omega and Theta. Since you are required to estimate the number of recursive calls, you'd better give me a equation, or something like Omega(3^n).