Tel-Aviv University
School of Computer Science
Introduction to Computer Science using Python
0368.1105
Fall Semester 2017-8
News
לא פורסם טסטר לתרגיל 6
במייל נשלח שפורסם טסטר לתרגיל 6, אך הוא לא נמצא במודל.
(01 Feb 2018 13:40)
Lecture Presentations
Hello, this message is mainly for the faculty,
I wanted to know if it is possible to add an option of downloading the lecture presentations as a zip file so it could be easier to study from them on the computer.
Thank you!
(31 Jan 2018 10:40)
2016 סמסטר ב' מועד ב שאלה 5
אשמח לפתרון של התרגיל הזה (התשובות בדרייב לא נכונות
(24 Jan 2018 18:23)
טסטים לתרגיל 6
from itertools import combinations import math import pytest from hw6_insert_id import choose_sets_gen, choose_sets_gen_specific, is_rotated_1, is_rotated_2, weighted_length, \ optimal, corpus, lz_Qa, lz_Qb, lz_Qc, test, upside_down, segment, dilate, edges, decode from matrix import * def test_choose_sets_gen(): for i in range(10): for k in range(5): lst = list(range(i)) expected_list = sorted([sorted(l) for l in combinations(lst, k)]) actual_list = sorted([sorted(l) for l in choose_sets_gen(lst, k)]) assert actual_list == expected_list with pytest.raises(StopIteration): assert next(choose_sets_gen(list(range(5)), 10)) assert sorted(next(choose_sets_gen(list(range(5)), 5))) == list(range(5)) def test_choose_sets_gen_specific(): for i in range(10): for k in range(5): for j in range(10): lst = list(range(i)) expected_list = sorted([sorted(l) for l in combinations(lst, k) if j in l]) actual_list = sorted([sorted(l) for l in choose_sets_gen_specific(lst, k, j)]) assert actual_list == expected_list with pytest.raises(StopIteration): assert next(choose_sets_gen_specific(list(range(5)), 10, 0)) with pytest.raises(StopIteration): assert next(choose_sets_gen_specific(list(range(5)), 10, 100)) assert sorted(next(choose_sets_gen_specific(list(range(5)), 5, 0))) == list(range(5)) def test_is_rotated_1(): text = "asdfghjkl;" for i in range(len(text)): s = text[i:] + text[:i] assert is_rotated_1(text, s) assert not is_rotated_1("asdfghjkl", "sdfghjkl") assert not is_rotated_1("asdfghjkl", "asdfghjk") assert not is_rotated_1("asdfghjkl", "asdfhjkl") assert not is_rotated_1("1234567890", "0988777654321") def test_is_rotated_2(): text = "asdfghjkl;" for i in range(len(text)): s = text[i:] + text[:i] assert is_rotated_2(text, s) assert not is_rotated_2("asdfghjkl", "sdfghjkl") assert not is_rotated_2("asdfghjkl", "asdfghjk") assert not is_rotated_2("asdfghjkl", "asdfhjkl") assert not is_rotated_2("1234567890", "0988777654321") def test_weighted_length(): assert weighted_length(["0", "11", "10"], [5, 1, 3]) == 13 def test_optimal(): assert optimal(["0", "11", "10"], [5, 1, 3]) assert optimal(["1", "00", "01"], [5, 1, 3]) assert not optimal(["00", "01", "0"], [5, 1, 3]) def test_corpus(): def char_count(text): d = {} for ch in text: if ch in d: d[ch] += 1 else: d[ch] = 1 return d w = [s[1] for s in sorted(char_count(corpus()).items())] c1 = ["0", "100", "101", "11"] c2 = ["00", "01", "10", "11"] assert weighted_length(c1, w) == weighted_length(c2, w) def test_lz_Q(): def inter_to_bin(lst, w=2 ** 12 - 1, max_length=2 ** 5 - 1): """ converts intermediate format compressed list to a string of bits""" offset_width = math.ceil(math.log(w, 2)) match_width = math.ceil(math.log(max_length, 2)) # print(offset_width,match_width) # for debugging result = [] for elem in lst: if type(elem) == str: result.append("0") result.append((bin(ord(elem))[2:]).zfill(7)) elif type(elem) == list: result.append("1") m, k = elem result.append((bin(m)[2:]).zfill(offset_width)) result.append((bin(k)[2:]).zfill(match_width)) return "".join(ch for ch in result) def get_new_code(new_k): def maxmatch(T, p, w=2 ** 12 - 1, max_length=2 ** 5 - 1): """ finds a maximum match of length k<=2**5-1 in a w long window, T[p:p+k] with T[p-m:p-m+k]. Returns m (offset) and k (match length) """ assert isinstance(T, str) n = len(T) maxmatch = 0 offset = 0 for m in range(1, min(p + 1, w)): k = 0 while k < min(n - p, max_length) and T[p - m + k] == T[p + k]: k += 1 # at this point, T[p-m:p-m+k]==T[p:p+k] if maxmatch < k: maxmatch = k offset = m return offset, maxmatch def LZW_compress2(text, w=2 ** 12 - 1, max_length=2 ** 5 - 1): """LZW compression of an ascii text. Produces a list comprising of either ascii characters or pairs [m,k] where m is an offset and k>3 is a match (both are non negative integers) """ result = [] n = len(text) p = 0 while p < n: m, k = maxmatch(text, p, w, max_length) if k < new_k: # modified from k<2 result.append(text[p]) # a single char p += 1 # even if k was 2 (why?) else: result.append([m, k]) # two or more chars in match p += k return result # produces a list composed of chars and pairs return LZW_compress2 funcs = [lz_Qa, lz_Qb, lz_Qc] original = get_new_code(3) improved = get_new_code(4) for func in funcs: s, o, i = func() assert len(inter_to_bin(original(s))) == o assert len(inter_to_bin(improved(s))) == i def test_upside_down(): matrix = Matrix(1, 1) assert upside_down(matrix) == matrix matrix = Matrix(1, 1) matrix.rows = [ [1, 2], [3, 4] ] assert upside_down(matrix).rows == [[3, 4], [1, 2]] def test_segment(): black_matrix = Matrix(10, 10) white_matrix = Matrix(10, 10, val=255) matrix = Matrix(10, 10, val=100) assert segment(matrix, 50) == white_matrix assert segment(matrix, 100) == white_matrix assert segment(matrix, 150) == black_matrix def test_edges(): m1 = Matrix(4, 4, 0) m1[0, 0] = 20 m1[1, 0] = 60 m2 = segment(m1, 10) assert m2.rows == [[255, 0, 0, 0], [255, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] m3 = dilate(m2, 1) assert m3.rows == [[255, 0, 0, 0], [255, 255, 0, 0], [0, 255, 0, 0], [0, 0, 0, 0]] m4 = m3 - m2 assert m4.rows == [[0, 0, 0, 0], [0, 255, 0, 0], [0, 255, 0, 0], [0, 0, 0, 0]] assert edges(m1, 1, 10) == m4 def test_decode(): assert decode("".join(["1" * 3, "1" * 3, "0" * 3]), 3) == "110" assert decode("".join(["1" * 3, "1" * 3, "100"]), 3) == "110" assert decode("".join(["1" * 3, "101", "0" * 3]), 3) == "110" assert decode("".join(["110", "1" * 3, "0" * 3]), 3) == "110" assert decode("".join(["110", "101", "100"]), 3) == "110" assert decode("".join(["1100", "1101", "0100"]), 4) is None def test_tester(): test()
(17 Jan 2018 19:53)
הרצאה מספר 21-מצגת
היי, להרצאה מספר 21 מצורפות 2 מצגות, אך המצגת השנייה מובילה ללינק שבור.
האם תוכלו לצרף את המצגת?
תודה רבה!
(16 Jan 2018 16:59)
תקציר תרגול 12
היי, תוכלו לפרסם את תרגול 12?
תודה רבה!
(12 Jan 2018 17:51)
טסטים לתרגיל 5
מעלה טסטים לתרגיל 5.
סקריפט להרצת הטסטים: לינק
הסבר על הטסטים ואיך מריצים ידנית: לינק
בחלק מהטסטים יש בדיקת תקינות קלט למרות שלא נדרש בשאלה אז אם אתם מקבלים את שגיאה שכתוב בה Did not raise… אז אתם יכולים לרוב למחוק את השורה הספציפית בטסט.
import pytest from hw5_<insert_id> import Matrix, SparseMatrix, mat2a, mat2b, mat2c, Func, Binary_search_tree, hash_sequence, \ intersects, test def _get_matrix(n, m): matrix = Matrix(n, m) for i, row in enumerate(matrix.rows): for j in range(len(row)): row[j] = i * 10 + j return matrix def _to_sparse_matrix(matrix): n, m = matrix.dim() sparse_matrix = SparseMatrix(n, m) for i in range(n): for j in range(m): if matrix[i, j] != 0: sparse_matrix.elements[i, j] = matrix[i, j] return sparse_matrix def test_minor(): matrix = _get_matrix(1, 1) assert matrix.minor(0, 0).rows == [] for i in range(2): for j in range(2): matrix = _get_matrix(2, 2) assert matrix.minor(i, j).rows == [[(1 - i) * 10 + (1 - j)]] matrix = _get_matrix(3, 4) assert matrix.minor(1, 1).rows == [ [0, 2, 3], [20, 22, 23] ] def test_det(): matrix = _get_matrix(1, 1) assert matrix.det() == 0 matrix.rows = [ [0, 2, 2], [2, 0, 2], [2, 2, 0] ] for i in range(3): assert matrix.det(i) == 16 matrix.rows = [ [1, 6, 0, 4], [1, 1, 7, 1], [3, 2, 1, 1], [0, 7, 0, 1] ] assert matrix.det() == -411 with pytest.raises(AssertionError): _get_matrix(2, 3).det() def test_sparse_matrix1(): for i in range(1, 12): for j in range(i, 12): assert SparseMatrix(i, j).dim() == Matrix(i, j).dim() assert SparseMatrix(i, j).__repr__() == Matrix(i, j).__repr__() assert SparseMatrix(i, j) == _to_sparse_matrix(Matrix(i, j)) def test_sparse_matrix2(): matrix = Matrix(4, 4) matrix.rows = [ [1, 6, 0, 4], [1, 1, 7, 1], [3, 2, 1, 1], [0, 7, 0, 1] ] sparse_matrix = _to_sparse_matrix(matrix) assert sparse_matrix.__repr__() == matrix.__repr__() assert sparse_matrix == _to_sparse_matrix(matrix) assert sparse_matrix[1, 2] == 7 with pytest.raises(AssertionError): sparse_matrix[5, 5] sparse_matrix[1, 1] = 2 assert sparse_matrix[1, 1] == 2 sparse_matrix[1, 1] = 0 assert (1, 1) not in sparse_matrix.elements sparse_matrix[1, 1] = 1 assert sparse_matrix[1, 1] == 1 def test_sparse_matrix3(): with pytest.raises(AssertionError): SparseMatrix(1, 1) + SparseMatrix(1, 2) with pytest.raises(AssertionError): SparseMatrix(1, 1) + 6 matrix1 = Matrix(1, 1) matrix1.rows = [ [1, 10], [100, 1000] ] matrix2 = Matrix(1, 1) matrix2.rows = [ [2, 20], [200, 2000] ] matrix3 = Matrix(1, 1) matrix3.rows = [ [3, 30], [300, 3000] ] sparse_matrix1 = _to_sparse_matrix(matrix1) assert sparse_matrix1 + _to_sparse_matrix(matrix2) == _to_sparse_matrix(matrix1 + matrix2) assert sparse_matrix1 + (-sparse_matrix1) == _to_sparse_matrix(matrix1 + (-matrix1)) assert sparse_matrix1 - sparse_matrix1 == _to_sparse_matrix(matrix1 - matrix1) for i in range(10): assert sparse_matrix1 * i == _to_sparse_matrix(matrix1 * i) assert i * sparse_matrix1 == _to_sparse_matrix(i * matrix1) assert sparse_matrix1 == _to_sparse_matrix(matrix1) def test_sparse_matrix4(): for i in range(2): for j in range(2): matrix = _get_matrix(2, 2) + Matrix(2, 2, 1) sparse_matrix = _to_sparse_matrix(matrix) assert sparse_matrix.minor(i, j).__repr__() == matrix.minor(i, j).__repr__() matrix = _get_matrix(3, 4) sparse_matrix = _to_sparse_matrix(matrix) assert sparse_matrix.minor(1, 1).__repr__() == matrix.minor(1, 1).__repr__() def test_sparse_matrix5(): matrix = _get_matrix(1, 1) assert _to_sparse_matrix(matrix).det() == 0 matrix.rows = [ [0, 2, 2], [2, 0, 2], [2, 2, 0] ] for i in range(3): assert _to_sparse_matrix(matrix).det(i) == 16 matrix.rows = [ [1, 6, 0, 4], [1, 1, 7, 1], [3, 2, 1, 1], [0, 7, 0, 1] ] assert _to_sparse_matrix(matrix).det() == -411 with pytest.raises(AssertionError): _to_sparse_matrix(_get_matrix(2, 3)).det() def test_mat_hash(): def hash1(matrix): sorted_keys = sorted(matrix.elements.keys()) keys_str = ",".join(str(i) + "," + str(j) for (i, j) in sorted_keys) vals_str = ",".join(str(matrix.elements[(i, j)]) for (i, j) in sorted_keys) print(keys_str + "," + vals_str) return hash(keys_str + "," + vals_str) def hash2(matrix): sorted_keys = sorted(matrix.elements.keys()) vals_str = ",".join(str(matrix.elements[(i, j)]) for (i, j) in sorted_keys) return hash(vals_str) def hash3(matrix): keys_sum = sum(i + j for (i, j) in matrix.elements.keys()) vals_sum = sum(matrix.elements[(i, j)] for (i, j) in matrix.elements.keys()) return hash(keys_sum + vals_sum) mat1 = SparseMatrix(3, 3) mat1[0, 0] = 1 mat1[1, 2] = 6 assert hash2(mat1) == hash2(mat2b()) assert hash3(mat1) == hash3(mat2c()) def test_get_row(): matrix = _to_sparse_matrix(_get_matrix(5, 5)) assert list(matrix.gen_row1(0)) == list(range(1, 5)) assert list(matrix.gen_row2(0)) == list(range(1, 5)) assert list(matrix.gen_row1(1)) == list(range(10, 15)) assert list(matrix.gen_row2(1)) == list(range(10, 15)) matrix = SparseMatrix(5, 7) assert list(matrix.gen_row1(2)) == [] assert list(matrix.gen_row2(2)) == [] def test_func_call(): f1 = Func(lambda x: 1 / x, lambda x: x != 0) assert f1(3) == 1 / 3 assert f1(0) is None f2 = Func(lambda x: x + 3, lambda x: True) assert f2(1) == 4 assert f2(0) == 3 f3 = Func(lambda x: 1 / x, lambda x: True) with pytest.raises(ZeroDivisionError): f3(0) def test_func_compose(): f1 = Func(lambda x: 1 / x, lambda x: x != 0) f2 = Func(lambda x: x + 3, lambda x: True) f3 = f1.compose(f2) assert f3(1) == 0.25 assert f3(-3) is None f4 = f2.compose(f1) assert f4(2) == 3.5 f5 = f1.compose(f1) assert f5(3) == 3 def test_func_exp(): f2 = Func(lambda x: x + 3, lambda x: True) f3 = f2.exp(4) assert f3(0) == 12 f4 = Func(lambda x: x + 3, lambda x: x != 0).exp(10) assert f4(-15) is None def test_func_exp_rec(): f2 = Func(lambda x: x + 3, lambda x: True) f3 = f2.exp_rec(4) assert f3(0) == 12 f4 = Func(lambda x: x + 3, lambda x: x != 0).exp_rec(10) assert f4(-15) is None def test_store_heights(): bin_tree = Binary_search_tree() bin_tree.insert(2, "a") bin_tree.insert(4, "b") bin_tree.insert(2, "c") bin_tree.insert(3, "d") bin_tree.insert(1, "e") bin_tree.store_heights() assert bin_tree.root.height == 2 assert bin_tree.root.left.height == 0 assert bin_tree.root.right.height == 1 assert bin_tree.root.right.left.height == 0 bin_tree = Binary_search_tree() bin_tree.insert(3, 3) bin_tree.store_heights() assert bin_tree.root.height == 0 def test_height_diff(): bin_tree = Binary_search_tree() bin_tree.insert(2, "a") bin_tree.insert(4, "b") bin_tree.insert(2, "c") bin_tree.insert(3, "d") bin_tree.insert(1, "e") bin_tree.insert(0, "f") bin_tree.insert(5, "g") bin_tree.insert(7, "h") bin_tree.insert(6, "i") assert bin_tree.height_diff() == 2 bin_tree.insert(4.5, "j") bin_tree.insert(3.5, "k") bin_tree.insert(-1, "l") bin_tree.insert(1.5, "m") assert bin_tree.height_diff() == 1 bin_tree = Binary_search_tree() bin_tree.insert(1, 1) assert bin_tree.height_diff() == 0 bin_tree.insert(2, 1) assert bin_tree.height_diff() == 0 bin_tree.insert(3, 1) assert bin_tree.height_diff() == 0 bin_tree.insert(0, 1) assert bin_tree.height_diff() == 1 bin_tree.insert(0.5, 1) assert bin_tree.height_diff() == 0 bin_tree = Binary_search_tree() for i in range(5): bin_tree.insert(i, 1) bin_tree.insert(-1, 1) assert bin_tree.height_diff() == 3 def test_hash_sequence(): assert hash_sequence("byebyeboy", 3) == {'yeb': [1, 4], 'boy': [6], 'bye': [0, 3], 'ebo': [5], 'eby': [2]} assert hash_sequence("aaaaa", 5) == {"aaaaa": [0]} assert hash_sequence("aaaaa", 1) == {"a": list(range(5))} assert hash_sequence("ababababa", 3) == {"aba": list(range(0, 7, 2)), "bab": list(range(1, 7, 2))} assert hash_sequence("", 3) == {} assert hash_sequence("aa", 3) == {} def test_intersects(): assert intersects("byebyebaboonboy", "babyboy", 4) is None assert intersects("byebyebaboonboy", "babyboy", 3) in ["bab", "boy"] def test_tester(): test()
(03 Jan 2018 19:21)
קוד להרצת הטסטים
הוראות:
1. לשמור את הקוד המצורף כקובץ py בתיקייה עם הקוד שלכם מהתרגיל
2. לשמור את קובץ הטסטים המתאים לתרגיל באותה תיקייה בשם test_hwX.py כאשר X זה מספר התרגיל
3. להריץ את הקובץ py מסעיף 1
שימו לב שבהרצה הראשונה הקוד יתקין ספריות פייתון חסרות ותצטרכו להריץ את הסקריפט שוב
import os import sys from subprocess import call PACKAGES_TO_INSTALL = [ "pip", "pytest", "mock" ] try: import pip import pytest import mock except ModuleNotFoundError: pip_path = os.path.join(sys.exec_prefix, "Scripts", "pip.exe") for package in PACKAGES_TO_INSTALL: call([pip_path, "install", "-U", package]) print("Packages installed! Please rerun the script.") input("Press Enter to exit.") exit(0) pytest.main(["--capture=sys"]) input("Press Enter to exit.")
(03 Jan 2018 19:06)
Fermat Primality Testing and Trial Division
Why isn't the number of operations performed by the Fermat Primality Testing exponential as it is in Trial Division?
(28 Dec 2017 09:25)
פתרונות לתרגילים
[div style="direction:rtl;"]]
האם יפורסמו פתרונות מלאים לתרגילים מתישהו?
תודה
[[/div]]
(23 Dec 2017 09:37)
הבדל בין ממואיזציה ופונקצית מעטפת
מה ההבדל בין פונקצית מעטפת לבין ממואיזציה?
(18 Dec 2017 21:44)
טסטים לתרגיל 4
מעלה טסטים לתרגיל 4.
הערות:
- הסבר על איך להריץ את הטסטים תוכלו למצוא פה
- בטסטים test_rw_stats ו-test_win_mem יש אלמנט רנדומי אז יש סיכוי מאוד נמוך שהם יכשלו מדי פעם
- השתמשי בספרייה mock בשביל הטסטים, יכולים להתקין אותה עם הפקודה pip install mock
- אם יש שאלות מוזמנים לכתוב פה ואני אנסה לענות כשאוכל:)
import time from mock import mock from hw4_<insert_id> import acc, myProd, compose, profit, profit2, profit3, win, win2, walk, rw_stats,test class MockFunc(object): def __init__(self, values): self._values = values[::-1] def __call__(self, *args, **kwargs): return self._values.pop() def test_acc(): assert acc(lambda x, y: x + y, 0, [2, 3, 7]) == sum([2, 3, 7]) assert acc(lambda x, y: x + y, -12, [2, 3, 7]) == 0 assert acc(lambda x, y: x + y, 0, []) == 0 assert acc(lambda x, y: x * y, 1, [2, 3, 7]) == 2 * 3 * 7 assert acc(lambda x, y: x * y, 1, []) == 1 assert acc(lambda x, y: x + y, 0, range(100)) == sum(range(100)) def test_myprod(): def assert_myprod(lst): value = 1 for i in lst: value *= i assert myProd(lst) == value assert_myprod(range(1, 100)) assert_myprod(range(100)) assert_myprod(range(1, 50, 2)) assert_myprod(range(-100, 0)) assert myProd([]) == 0 assert myProd([3, 4, 5]) == 60 assert myProd([10, 10, 10]) == 1000 assert myProd([10, -1, -1]) == 10 def test_compose(): assert compose([lambda x: x - 1, lambda x: x * 2, lambda x: x + 1])(5) == 11 assert compose([])(5) == 5 assert compose([lambda x: x - 1, lambda x: x + 1])(5) == 5 assert compose([lambda x: x, lambda x: x])(5) == 5 assert compose([lambda x: x + 1, lambda x: x * 0])(5) == 1 assert compose([lambda x: x + 1, lambda x: x * 0, lambda x: x + 1])(5) == 1 assert compose([lambda x: x + 1, lambda x: x + 1, lambda x: x + 1])(5) == 8 def test_profit(): assert profit([1, 5, 8, 9], 4) == 10 assert profit([2, 3, 7, 8, 9], 5) == 11 assert profit([1, 2, 3, 4, 5], 5) == 5 assert profit([1, 2, 4, 5, 6, 7], 6) == 8 assert profit([i + 1 for i in range(10)], 10) == 10 assert profit([2] + [i + 3 for i in range(9)], 10) == 20 assert profit([1, 3] + [i + 1 for i in range(8)], 10) == 15 assert profit([0, 2], 2) == 2 assert profit([1], 1) == 1 def test_profit2(): assert profit2([1, 5, 8, 9], 4) == 10 assert profit2([2, 3, 7, 8, 9], 5) == 11 assert profit2([1, 2, 3, 4, 5], 5) == 5 assert profit2([1, 2, 4, 5, 6, 7], 6) == 8 assert profit2([i + 1 for i in range(100)], 100) == 100 assert profit2([2] + [i + 3 for i in range(9)], 10) == 20 assert profit2([1, 3] + [i + 1 for i in range(8)], 10) == 15 assert profit2([0, 2], 2) == 2 assert profit2([1], 1) == 1 def test_profit3(): assert profit3([1, 5, 8, 9], 4) == 10 assert profit3([2, 3, 7, 8, 9], 5) == 11 assert profit3([1, 2, 3, 4, 5], 5) == 5 assert profit3([1, 2, 4, 5, 6, 7], 6) == 8 assert profit3([i + 1 for i in range(10)], 10) == 10 assert profit3([2] + [i + 3 for i in range(9)], 10) == 20 assert profit3([1, 3] + [i + 1 for i in range(8)], 10) == 15 assert profit3([0, 2], 2) == 2 assert profit3([1], 1) == 1 def test_win(): assert win(9, [1, 4, 2]) == False assert win(5, [3, 1]) == True assert win(1, [1]) == True assert win(2, [1]) == False assert win(2, [1, 2]) == True assert win(5, [1, 2, 3]) == True assert win(5, [1, 3]) == True assert win(7, [1, 4, 2]) == True def test_win2(): assert win2(9, [1, 4, 2]) == False assert win2(5, [3, 1]) == True assert win2(1, [1]) == True assert win2(2, [1]) == False assert win2(2, [1, 2]) == True assert win2(5, [1, 2, 3]) == True assert win2(5, [1, 3]) == True assert win2(7, [1, 4, 2]) == True def test_win_mem(): a = time.clock() win(40, [1, 3, 5]) b = time.clock() t1 = b - a a = time.clock() win2(40, [1, 3, 5]) b = time.clock() t2 = b - a assert t2 < t1 def test_walk(): with mock.patch("random.choice", lambda _: 1): assert walk(10, 2) == ((10 ** 2 + 10 ** 2) ** 0.5, False) assert walk(0, 3) == (0, False) with mock.patch("random.choice", MockFunc([ 1, 0, 0, 0, 1, 0, 0, 0, 1 ])): assert walk(3, 3) == (3 ** 0.5, False) with mock.patch("random.choice", MockFunc([ 1, 0, 1, 0, -1, 0, -1, 0, 0, 0, 1, 0 ])): assert walk(3, 4) == (1, True) with mock.patch("random.choice", MockFunc([ 1, 0, 1, 0, 0, 1, 0, 1, -1, 0, -1, 0, 0, -1, 0, -1 ])): assert walk(4, 4) == (0, True) with mock.patch("random.choice", MockFunc([ 1, 0, 1, 0, 0, 1, 0, 1, -1, 0, -1, 0, 0, -1, 0, -1, 1, 1, 1, 1, ])): assert walk(5, 4) == (2, True) def test_rw_stats(): run_length, average_dist, average_dist_divided, \ min_dist, max_dist, origin_frequency = rw_stats(100, 3, 10 ** 3) assert run_length == 100 assert 1.5 <= average_dist_divided <= 1.8 assert 0.2 <= origin_frequency <= 0.3 def test_tester(): test()
(18 Dec 2017 18:53)
טסטים לתרגיל 3
אני אשתף לכל תרגיל (או אנסה לפחות) קובץ טסטים שנועד לבדוק שהקוד בתרגילים עובד כמו שצריך.
הטסטים יהיו כתובים בpytest (למי שלא מכיר ניתן להתקין עם הפקודה pip install -U pytest)
על מנת להריץ את הטסטים צריך להכניס את הת"ז שלכם בשורה הראשונה ולשמור את הקוד בקובץ py בתיקייה שבה נמצא הקוד שלכם ולהריץ את הפקודה:
pytest test_hw3.py
(בהנחה ששמרתם את הקובץ בשם test_hw3.py)
מידע נוסף על התקנת pip:
https://pip.pypa.io/en/stable/installing/
מידע נוסף על pytest:
https://docs.pytest.org/en/latest/usage.html
שימו לב:
א. אני לא חלק מסגל הקורס אז הטסטים לא רשמיים.
ב. כנראה שיש עוד מקרים שלא נבדקים על ידי הטסטים.
ג. יכולים להיות מקרים מיוחדים שבהם הטסטים יכשלו אבל הקוד שלכם יהיה נכון
מוזמנים לשאול כאן שאלות על הקוד ואני אנסה לענות כמה שאוכל:)
הקוד:
import random from hw3_<insert_id> import find_root1, find_root_range, find_root2, generate_sorted_blocks, merge_sorted_blocks, \ sort_triplets1, sort_triplets2, equal, test, source, inverse def is_equal(a, b, epsilon=10 ** (-8)): return abs(a - b) < epsilon def test_find_root1(): f1 = lambda x: x - 100 assert find_root1(f1) == 100 f2 = lambda x: x assert find_root1(f2) is None f3 = lambda x: 2 * x - 101 assert find_root1(f3) is None f4 = lambda x: x ** 2 - 10000 assert find_root1(f4) is 100 f5 = lambda x: 2 * x + 1 assert find_root1(f5) is None def test_find_root_range(): assert find_root_range(lambda x: x - 10, 1, 12) == 10 assert find_root_range(lambda x: x - 10, 12, 20) is None assert find_root_range(lambda x: x - 10, 1, 1000) == 10 assert find_root_range(lambda x: x - 1, 1, 1) == 1 assert find_root_range(lambda x: x - 1, 1, 1) == 1 assert find_root_range(lambda x: 2 * x / x, 1, 1) is None def test_find_root2(): assert find_root2(lambda x: x - 10) == 10 assert find_root2(lambda x: x - 10) == 10 assert find_root2(lambda x: x - 1) == 1 assert find_root2(lambda x: x - 1) == 1 assert find_root2(lambda x: 1) is None assert find_root2(lambda x: 2 ** 100 - x) is None assert find_root2(lambda x: 2 * x / x) is None assert find_root2(lambda x: x - 2 ** 99) == 2 ** 99 assert find_root2(lambda x: x - 2 ** 100) == 2 ** 100 assert find_root2(lambda x: x + 1 - 2 ** 100) == 2 ** 100 - 1 assert find_root2(lambda x: 2 * x - 101) is None assert find_root2(lambda x: x - 2 ** 103) is None def test_generate_sorted_blocks1(): assert generate_sorted_blocks(list(range(10)), 3) == [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]] assert generate_sorted_blocks(list(range(10)), 1) == [[i] for i in range(10)] assert generate_sorted_blocks(list(range(10)), 10) == [list(range(10))] assert generate_sorted_blocks(list(range(10, 0, -1)), 3) == [[8, 9, 10], [5, 6, 7], [2, 3, 4], [1]] assert generate_sorted_blocks(list(range(10, 0, -1)), 1) == [[i] for i in range(10, 0, -1)] assert generate_sorted_blocks(list(range(10, 0, -1)), 10) == [list(range(1, 11))] lst = [610, 906, 308, 759, 15, 389, 892, 939, 685, 565] assert generate_sorted_blocks(lst, 2) == [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]] assert generate_sorted_blocks(lst, 3) == [[308, 610, 906], [15, 389, 759], [685, 892, 939], [565]] assert generate_sorted_blocks(lst, 10) == [[15, 308, 389, 565, 610, 685, 759, 892, 906, 939]] def test_merge_sorted_blocks1(): for k in range(1, 101): for n in range(k, 101): lst = list(range(n)) random.shuffle(lst) assert merge_sorted_blocks(generate_sorted_blocks(lst, k)) == list(range(n)) block_lst1 = [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]] assert merge_sorted_blocks(block_lst1) == [15, 308, 389, 565, 610, 685, 759, 892, 906, 939] def test_sort_triplets(): for k in range(2, 25, 5): for n in range(1, 100, 11): input_list = [(random.randint(0, k - 1), random.randint(0, k - 1), random.randint(0, k - 1)) for _ in range(n)] random.shuffle(input_list) output_list1 = sort_triplets1(input_list, k) output_list2 = sort_triplets2(input_list, k) assert output_list1 == output_list2 == sorted(input_list) def test_equal(): result = equal(lambda x: 4 * x, lambda x: x ** 2 + 3) assert is_equal(result, 1) or is_equal(result, 3) result = equal(lambda x: x, lambda x: -x) assert is_equal(result, 0) result = equal(lambda x: x, lambda x: x + 1) assert result is None result = equal(lambda x: 100 - x, lambda x: x) assert is_equal(result, 50) result = equal(lambda x: -50, lambda x: x) assert is_equal(result, -50) def test_source(): assert is_equal(source(lambda x: x, 5), 5) assert is_equal(source(lambda x: x + 3, 5), 2) assert is_equal(source(lambda x: 2 * x, 9), 4.5) assert is_equal(source(lambda x: x, -100), -100) assert is_equal(source(lambda x: 50 - x, 0), 50) def test_inverse(): assert is_equal(inverse(lambda x: x)(5), 5) assert is_equal(inverse(lambda x: x + 3)(5), 2) assert is_equal(inverse(lambda x: 2 * x)(9), 4.5) assert is_equal(inverse(lambda x: x)(100), 100) assert is_equal(inverse(lambda x: 50 - x)(0), 50) assert is_equal(inverse(lambda x: 50 - x)(50), 0) assert is_equal(inverse(lambda x: 50 - x)(50), 0) def test_tester(): test()
(02 Dec 2017 21:16)
צירוף בכתב יד
היי,
ראיתי במייל ששלחתם שמותר להוסיף דברים בכתב יד רק לסעיף א בשאלה 1.
לדוגמא בשאלה 3 שצריך לנתח זמן ריצה
אי אפשר לשים פתרון בכתיב ברור שכותב ביד ולסרוק ולצרף לPDF?
אני לא רואה שום דרך לכתוב את זה בוורד שיצא קריא
(01 Dec 2017 12:02)
האם ניתן להשתמש ברקורסיה בתרגיל 3?
היי,
האם ניתן להשתמש ברקורסיה במטלה 3?
תודה,
פלג
(30 Nov 2017 22:44)
סיבוכיות זיכרון של פיבונצי איטרטיבי
The Presentation of lecture 12 in slide 25 says that the memory complixity of iterative fibonacci is o(1)? Why? I thought its o(n).
(30 Nov 2017 19:23)
מתי שעות הקבלה של המתרגלים והמרצים?
מתי שעות הקבלה של המתרגלים והמרצים?
(28 Nov 2017 19:36)
שאלה לגבי מקרי קצה
רציתי לשאול האם העובדה שפונקציית הטסט לא בדקה את כל מקרי הקיצון בשיעורי הבית הראשונים מכוונת, והאם זה יישאר כך.
אם כן, האם ישנם איזשהם קווים מנחים על מנת לוודא כי פגענו בכל מקרה קיצון?
תודה מראש,
עידו
(19 Nov 2017 16:31)
לא מוצא הערות על תרגיל 1
נכנסתי לטבלה עם הציונים בקורס ואני אכן רואה שורה בה בצד ימין יש "הגשת תרגיל בית 1" ואיזשהו ציון אבל אני לא רואה שם סימוני הערות.
תודה.
(18 Nov 2017 23:03)
שאלה 3 סעיף א - הפנייה לנוסחה מהתרגול
אשמח מאוד אם מישהו יוכל להפנות למצגת הרלוונטית כאן באתר.
תודה רבה.
(18 Nov 2017 14:08)
Forums (see tips on the right ----->)
Do not forget to click "preview" before posting your message!
General Forum
All HW forums