main thread
can someone *please* explain me what the hell is going on in here? specially dots 2-4:
what does it mean that the codewords are disjoint?
where did these "points" come from, and really why each ball (ball? anyone?) contains exactly n+1 balls?
and why there are 2^k such balls?
the balls are like those ugly yellow and blue ones from the figure from 21/52?
thanks * 4
:)
I cite bellow the paragraph related to the complexity of Karp-Rabin code. My question is: shouldn't it actually be O(n-m-1) + O(m)= O(n) ?
"Time complexity: O(m) operations to compute the two finger prints, finger print(P[0..m-1]) and finger print(T[0..m-1]).
O(m) operations for both, Additional n-m-1 finger prints to compute, each taking O(1) operations. Total cost is O(n) + O(m)= O(n + m)."
Thanks!
In reaspect to Q 2 from MOED B last summer, for a list of n arguments, how does ' concat = "".join(lst) ' workes?
Is it creating n sub strings, each time adding the next argument of the list, or, does it creates one new string at once, without creating any sublists?
האם יש אפשרות לצוות הקורס לעלות את מועד ב' של סמסטר קודם ?
באופן עקרוני יש לי את הטופס עצמו של סטודנט שנגש לבחינה אבל מסומנות התשובות שם והייתי שמח לעשות את הבחינה בלי להסתכל בתשובות ולנסות לבד
תודה רבה!
the function insert from linked list (lecture 15 slide 10) - it seems like the new node is insert to the location loc+1 instead of loc.. is it supposed to be like that or am i mistaken?
thank you!
LZ compression:
i've just read the example that amir wrote, but i don't fully understand it. the example was:
the string is "a"*k times ("aaaaaaaaaaaaaaaaaaaa")
so, the compressed string should look like: a,[1,31],…,[1,31],[1, (k-1)%31]
so far so good.
but it says that the numbers of "full" pairs ([1,31]) is (k-1) // 31 + 1.
but, *correct me if i'm wrong*, let's say that k = 70. then it should be only 2 full pairs, right? but (69)//31 + 1 = 3, and 3 is not equal to 2…
so… where did i get it wrong?
If I recall, we were calculating the total number of pairs, including the last one which may be "not full".
you're right…
but if k = 63, then the output will be: a,[1,31],[1,31]..(?) but according to the formula (k-1)31 + 1, it should be 3 pairs (6231 = 2…)… or not?
You're right. If k-1 is some multiplication of 31 then this formula is wrong.
Looking again at my notes for this class, it should indeed be ceil((k-1)/31), where ceil rounds up to the closest integer.
Not really relevant to the test, but the algorithm can be improved to allow lengths of up to 34 with the same 12:5 ratio - since repetitions of length 0-2 are not encoded, we can use those lengths to encode longer repetitions.
yes, but only on average (since dict is implemented as a hash table).
just to make sure- lecture 10 slides 38-50 are for refrence only?
Exam guidelines excludes Fermat’s little theorem, but it randomized primality testing uses basic ideas from Fermat's little theorem… so, should we or should we not understand the basics of Fermat's theorem and randomized primality testing?
You should know the algorithm and its basic properties (such as complexity, why it might fail, the probability for failure, etc.). But you don't need to know the proof.
בתרגול 8 של יואב, בתרגיל על סיבוכיות מציאת מחרוזת בעזרת פונקציית האש, הפונקציה היא
:
def repeat_hash1(st, k, m=0):
if m == 0: # default hash table size is ~number of substrings to be inserted
m = len(st) - k
htable = MyHashtable(m)
for i in range(len(st) - k + 1):
if htable.find(st[i : i + k]):
return True
else:
htable.insert(st[i : i + k])
return False
ורשום:
Average case complexity
Creating hashtable - O(m)=O(n−k). Number of iterations - O(n−k). Each iteration we search a list of length O(1) on average, so overall O(k). Total complexity on average O(k(n−k))=O(n).
השאלה שלי היא כדלקמן: אם יש
O(n-k)
,איטרציות
ובכל איטרציה הסיבוכיות היא קבועה,
אז סה"כ הסיבוכיות של האיטרציות היא
O(k), and not O(n-k). and it make the overall complexity to be O(n^2), and not O(n)
Was there an typing err. or did I misunderstand?
I didn't follow your logic completely.
But O(1) is the (average) number of substrings in each index of the hash table. For each one of these substrings, you compare 2 k-long strings which takes O(k), not O(1).
Hope that sorts it out.