.. (לתיקייה המכילה) | ||
Can we write Q1 by hand? | |
Yes you can write Q1 by hand and still get the 5 pt bonus. Note that all other questions must be printed (if you want to add drawings by hand, it is also accepted). |
In the first question, what should we prove? | |
For every two functions you should prove the relation between them. For example, if you decide that the right order is : f1, f2, f3, f4... and f2=Theta(f3) you should prove the following: f1 = O(f2) f2 = Theta(f3) f3 = O(f4) and so on... |
In Q1, can we use the limit definition to prove relationships between functions? | |
1. You can not use the limit method unless you prove it. 2. You can use the limit definitions of small omega and small o as given in class. |
How should we describe the data structure (question 5)? | |
Your description of a data structure should include (preferably, in that order): 1. Which structures are used. What data is stored in the nodes. Which keys are used (if there are any). What are the structure characteristics, for example, a sorted array. 2. For every operation - describe how it is performed. Show that the operations are correct and under the complexity requirements. Rule of thumb: a simple data structure description should take 1-2 pages. |
In question 5, should the method Tried(i,k) be called no more than once per day, or it might be called many times? | |
It might be called many times. |
Can we use stuff that was shown in class? | |
Yes. For example you can write: "We init an array in O(1)" without adding any further explanation. |
Hello, | |
No |