We will add some functionality to a binary search tree (BST) set in this lab, including using a generator for traversal. Our typical BSTs store key:value pairs. A BST set will just store keys. The textbook includes the full code for a binary search tree, including generator-based traversal. Avoid looking at the textbook during lab, but feel free to reference it afterwards if you are stuck. Spend the next 75 minutes trying to solve this problem with your lab partner. Tree Traversal Iterators Tree traversal is inherently recursive – we need to go left until we hit None, then right until we hit None, with a base case somewhere in the mix. Importantly, we need to keep track of the recursive stack of parent nodes. Classical iterators are not a great tool for recursive tree iteration, because any local variables (like a recursive stack) are lost as soon as an object is returned. The easiest method is to take a long time on our first iteration, recursively going through the entire tree to build a traversal queue, before we start returning items: # assume we want to iterate using in-order traversal class BSTNode_Iterator: def __init__(self, node): self.queue = [] self.in_order(node) # build up the entire queue during initialization self.counter = 0 # recursive in-order traversal to build up the queue def in_order(self, node): if node.left is not None: self.in_order(node.left) self.queue.append(node) if node.right is not None: self.in_order(node.right) # once the queue is finished, we can iterate through it def __next__(self): if self.counter < len(self.queue): self.counter += 1 return self.queue[self.counter-1].key raise StopIteration The queue initialization can be very slow for large trees. Ideally, we would like to “return” as soon as we find the next appropriate node, while keeping track of our current recursive stack. Generators Python uses a special keyword yield to return a value, while keeping track of the current state (e.g. all local variables) for the next call to a function. Functions that use yield instead of return are called generator functions. 1 >>> def gen_func(x, _max): >>> while x < _max: >>> yield x # return this value, but remember the value of x >>> x += 1 >>> >>> for item in gen_func(5, 8): >>> print(item) 5 6 7 >>> Generator functions: • are defined by using the keyword yield • remember local variables between calls • begin where they left off on subsequent calls (from the line after the most recent yield) • return generators, a special type of iterator. This means generator functions can be used in for loops There is a lot going on here conceptually, and it may take a few read throughs and some experimentation to fully internalize all of it. The conceptual load is worth it though – generators make it almost trivial to traverse trees, because we can keep track of a recursive stack between yield statements. Deliverables Most of your work will be adding methods to the class BSTNode. • put – adds a specified key to the BST – ignores duplicate keys • post_order – iterates through the subtree rooted at this node in post-order • pre_order – iterates through the subtree rooted at this node in pre-order You will also need to make minor modifications to the public-facing class BSTSet, so the examples given below appropriately call the BSTNode methods. Do not add any rotation/weight balancing to your BST for this assignment; that will cause the pre-order and post-order autograder tests to fail. Examples Any examples below are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own tests, and think carefully about edge cases. Some other test cases that may be helpful (not for a grade, but they’ll help you debug): • a balanced tree with the integers 0-7. What order should you add keys to get this result? • trees where you have added the same key multiple times • trees with non-standard keys (negative integers? characters?) 2 # unbalanced tree # 0 # `-1 # `-2 # `-3 bst = BSTSet() for i in range(4): bst.put(i) # test in-order ino = [] for key in bst.in_order(): ino.append(key) assert ino == [0, 1, 2, 3] # test pre-order preo = [] for key in bst.pre_order(): preo.append(key) assert preo == [0, 1, 2, 3] # test post-order posto = [] for key in bst.post_order(): posto.append(key) assert posto == [3, 2, 1, 0] Submitting At a minimum, submit BSTSet.py and BSTNode.py. Students must submit individually by the due date (typically, Friday at 11:59 pm EST) to receive credit.
This week, we’ve been introduced to our second recursively-defined data structure, trees! (As a reminder, the first one was linked lists.) Recall from lecture that a tree is either: • the empty tree, represented by None in Python, or • a node that points to other trees. Nodes usually contain some data as well. Important Note As trees have a natural recursive definition and structure, functions that operate on tree often have simple and elegant recursive definitions. For this homework, all of your function implementations must be recursive and you cannot use any iteration (i.e. for/while loops). Part 1: Simple Tree Functions In the starter code file, simple_tree_functions.py, implement the following functions. • height(t) – Returns the height of the tree t. – Returns -1 for the empty tree. • size(t) – Returns the number of nodes in the tree t. • find_min(t) – Returns the minimum element contained within a node in the tree t. – Returns float(“inf”) for the empty tree. • find_max(t) – Returns the maximum element contained within a node in the tree t. – Returns float(“-inf”) for the empty tree. • contains(t, k) – Returns True if and only if k is contained within one of the nodes of t (returns False otherwise). • in_order(t) – Returns a list containing contents of each node in the tree in the order of an in-order traversal of the tree. • pre_order(t) – Returns a list containing contents of each node in the tree in the order of an pre-order traversal of the tree. • post_order(t) – Returns a list containing contents of each node in the tree in the order of an post-order traversal of the tree. 1 Examples “”” 0 / 1 4 / / 2 5 3 “”” >>> n1 = TreeNode(1, left=TreeNode(2)) >>> n4 = TreeNode(4, left=TreeNode(5), right=TreeNode(3)) >>> tree = TreeNode(0, left=n1, right=n4) >>> height(tree) 2 >>> size(tree) 6 >>> find_min(tree) 0 >>> find_max(tree) 5 >>> contains(tree, 3) True >>> contains(tree, 6) False >>> in_order(tree) [2, 1, 0, 5, 4, 3] >>> pre_order(tree) [0, 1, 2, 4, 5, 3] >>> post_order(tree) [2, 1, 5, 3, 4, 0] Part 2: Higher-Order Tree Functions A higher-order function is a function that does at least one of the following: • takes one or more functions as arguments, or • returns a function as its result. In this part of the homework, we will explore some functions that take other functions as input and also operate on trees. Often times the functions passed to our higher-order functions will take the form of a lambda expression, (e.g. lambda x: x < 4). These expressions provide an elegant way for us to create small anonymous functions. For a little more info on lambda expressions, check out: • https://docs.python.org/3/reference/expressions.html#lambda • https://www.w3schools.com/python/python_lambda.asp In the starter code file, higher_order_tree_functions.py, implement the following functions. • count_failures(pred, t) 2 – Takes a predicate function (a function that returns either True or False) pred, and returns the number of nodes in the tree t whose data fails the predicate. ∗ If t is a non-empty tree node, then its data fails the predicate if pred(t.data) returns False. • tree_map(f, t) – Takes a function f, and returns a new tree consisting of the nodes from t such that f has been applied to the data within each of the nodes in t. – This function does NOT mutate the tree t, it returns a new tree. • tree_apply(f, t) – Takes a function f, and applies it to the data held with each node of the tree t. – This function mutates the tree t. Examples “”” 0 / 1 4 / / 2 5 3 “”” >>> n1 = TreeNode(1, left=TreeNode(2)) >>> n4 = TreeNode(4, left=TreeNode(5), right=TreeNode(3)) >>> tree = TreeNode(0, left=n1, right=n4) # Count Failures >>> count_failures(lambda x: x % 2 == 0, tree) 3 # ˆ 3 nodes contain integers that are not even >>> count_failures(lambda x: x < 4, tree) 2 # ˆ 2 nodes contain integers that are not less than 4 >>> count_failures(lambda x: x < 0, tree) 6 # ˆ 6 nodes contain integers that are not less than 0 # Tree Map >>> another_tree = tree_map(lambda x: x**2, tree) >>> in_order(another_tree) [4, 1, 0, 25, 16, 9] >>> in_order(tree) [2, 1, 0, 5, 4, 3] # ˆ original tree was not mutated by tree_map # Tree Apply >>> tree_apply(lambda x: x**3, tree) 3 >>> in_order(tree) [8, 1, 0, 125, 64, 27] # ˆ original tree was mutated by tree_apply Testing Note that we are not requiring unit tests in your submission. At this point in the semester, we expect that you are developing your own test suites for these questions as we do not provide any unit tests on Gradescope. Therefore, your tests will not be graded, but developing a thorough suite of tests is the only way that you will be able to ensure your function implementations exhibit the correct behavior. Imports No imports allowed on this assignment, with the following exceptions: • Any modules you have written yourself. • typing – this is not required, but some students have requested it. Submission Submit the following files to Gradescope: • simple_tree_functions.py • higher_order_tree_functions.py Please note this assignment is 100% manually graded. Students must submit individually by the due date (Tuesday, April 9th at 11:59 pm EST) to receive credit.
Impliment a class CustomSet that mirrors the python set. The starter code contains skeleton code for all necessary functions with instructions. TestLab8.py contains tests to help you debug. Do not use the built-in set or dict classes in this assignment. Examples Examples below are intended to be illustrative, not exhaustive. >>> from lab8 import CustomSet >>> s = CustomSet() >>> “hello” in s False >>> s.add(“hello”) >>> len(s) 1 >>> “hello” in s True >>> s.remove(“hello”) >>> s.remove(5) Traceback (most recent call last): … KeyError : Attempt to remove non-extant item 5 >>> Submitting At a minimum, submit a file named lab8.py containing a class CustomSet. Students must submit individually by the due date (typically Sunday at 11:59 pm EST) to receive credit.
Overview We’ll resolve hash collisions using two techniques: 1) Separate chaining – when multiple items hash to the same bucket, we put them into that same bucket • In class and the textbook, we used lists as our buckets, resulting in a “list of lists” • Here, we’ll use linked lists as our buckets, resulting in a “list of linked lists” 2) Open addressing – store only a single item in each “bucket”. When a collision occurs, find the next open address by. . . • linear probing – scan ahead for the next empty bucket, 1 item at a time • other techniques for finding an open address include quadratic probing and double hashing, but we’ll only do linear probing here. Part 1: Separate chaining We’ll need linked list and node classes appropriate for hashing. class UniqueRecursiveNode We’ll practice recursion by implementing recursive methods for a linked list of nodes with unique keys. • Store keys and values when initialized • __eq__ and __hash__ methods must be overloaded – two nodes are equal if they have the same key, even if their values or links are different. – two nodes with the same key should hash to the same number, even if their values or links are different. – Custom classes inherit __eq__ and __hash__ methods from the default Object class, but these methods do not work here because they are based on memory ID. • Add recursive implementations for: – add(key, value) ∗ O(n) ∗ updates value of node with key or addes a new node with key:value pair, as appropriate ∗ Returns the number of nodes added (either 0 or 1), so the LinkedList class can update _len appropriately – get(key) ∗ O(n) ∗ Returns value associated with key ∗ Raises a KeyError if key not found – remove(key) 1 ∗ O(n) ∗ removes node containing key and returns tuple of new_link, value · new_link – the node the preceding node should link to after this operation · value – the value associated with key ∗ raise a KeyError if this key is not found – contains(key) ∗ O(n) ∗ returns True iff key is in the linked list starting at this node • __iter__() – This is implemented for you. We’ll discuss iterators more during Mod 9. class UniqueLinkedList You don’t need to change anything here; it’s implemented for you. Look over the methods to familiarize yourself with how a linked list uses recursive nodes – we may ask you to code something like this on an exam. Note that we do not use a tail pointer. Our ideal use case is a large number of short linked lists, so the tail pointers add significant memory overhead without improving speed. SeparateChainingHashTable • Use the LinkedList class implemented above for your buckets • Resolve hash collisions via separate chaining • __init__ – O(1) – Include optional parameters with the following names and default values: ∗ MINBUCKETS: 2 – the minimum number of buckets in your hash map ∗ MINLOADFACTOR: 0.5 – the minimum allowable load factor (unless removing buckets would move you below MINBUCKETS) ∗ MAXLOADFACTOR: 1.5 – the maximum allowable load factor – Initialize with a list of MINBUCKETS UniqueLinkedLists • __setitem__(key, value) – O(1) amortized – adds or updates (key, value) pair, as appropriate • __getitem__(key) – O(1) amortized – returns value associated with key or raises a KeyError, as appropriate • __contains__(key) 2 – O(1) amortized – returns True or False, as appropriate • pop(key) – O(1) amortized – removes key:value pair and returns value or raises a KeyError, as appropriate • get_loadfactor() – O(1) – Returns the current load factor • Maintain O(n) memory overhead by ensuring MINLOADF ACT OR ≤ α < MAXLOADF ACT OR, where α is the load factor (number of items / number of buckets) Part 2 – Open Addressing LinearProbingHashTable Use the same public interface as LinkedListHashTable. However, resolve hash collisions with open addressing via linear probing: • Initilalize the HashTable with a list of None objects. • After hashing a key, if the desired bucket is empty, replace the appropriate None with a tuple of (key, value). • If the bucket is occupied, iterate through the list to find the next empty spot. • When removing, replace the tuple with -1 instead of None to denote that something used to be there. – This is necessary for e.g. O(1) amortized contains, since you cannot return False until you find a spot this key could have been in but isn’t. Here, that is equivalent to finding the None object (but not a -1) in a bucket. – If you find a -1 while probing for an empty spot during e.g. setitem, you can overwrite it – do not keep scanning for a None. • Your load factor must be < 1 to avoid infinite loops while probing: – Use default values of MINLOADFACTOR = 0.1 and MAXLOADFACTOR=0.75 – If a user specifies a MAXLOADFACTOR ≥ 1, raise a ValueError Testing Tests for UniqueRecursiveNode and UniqueLinkedList are provided for you. Remember to only test the public interface – do not test or access private variables or methods in your unittests. Test Hash Tables • SeparateChaningHashTable and LinearProbingHashTable have the same public interface, so use a test factory to factor out redundant unittests. 3 • “Test behavior, not implementation” is an important idiom here – there’s not a great way to write unittests for amortized running times of O(1) or memory usage of O(n), but these are results of implementations, so we don’t need to test them. Just test the input/output behavior for every method. • The starter code includes skelteon code for tests you should write, including: – test_put_get_sequential – iteratively add items, and test that you get correct results from: ∗ __getitem__ (call w/ the public interface e.g. my_hashtable[key]) ∗ __len__ ∗ __contains__ ∗ get_loadfactor() ∗ pseodo code: # Create empty hash map # for i in range n: # assert i not in n # add i, value to hash map # assert hm[i] gives correct value # assert i in hm # assert len is correct # assert load factor is in correct range – test_put_get_remove_sequential – iteratively add items, then remove ∗ build a hash map as above, then iteratively pop all keys, testing as you go – LinearProbingHashTable needs 1 additional test – ensure a ValueError is raised if a user specifies MAXLOADFACTOR >= 1. – Not required for this assignment, but if you really want to test that your code works: ∗ Test how you handle duplicate key:value pairs (should update value but not length). See TestUniqueLinkedList for an example ∗ Test how you handle random adds. It’s helpful to use a python dictionary as a template for your “expected” value here: # Create empty hash map # Create empty dictionary # for i in range n: # generate random key:value # add to dictionary # add to hash map # test that dictionary and hash map are the same Imports No imports are allowed on the assignments, with the following exceptions: • unittest and random – for testing. • typing for type validation – not required, but feel free to use it if you’d like. 4 Submission At a minimum, submit the following files with the specified classes: • UniqueLinkedList.py – class UniqueRecursiveNode – class UniqueLinkedList unmodified from the starter code • SeparateChainingHashTable.py – class SeparateChainingHashTable • LinearProbingHashTable.py – class LinearProbingHashTable • TestHashTables.py – class TestHashTableFactory – class TestSeparateChainingHashTable.py – class TestLinearProbingHashTable.py This assignment is 100% manually graded. Students must submit individually by the Tuesday after Exam
Differentiate 5 sorting algorithms (bubble, selection, insertion, merge, and quick) based on how long they take to sort certain lists. When you submit a file called numbers.txt to Gradescope, it will sort the numbers inside with these 5 algorithms, aliased as alg_a, alg_b, alg_c, alg_d, and alg_e: ================ n = 1000 —————- alg t (ms) —————- alg_a 24.6 alg_b 1.35 alg_c 57 alg_d 2.12 alg_e 40.1 —————- You need to 1) Create lists of different lengths and patterns 2) Determine which alias corresponds to which sorting algorithm Answers Write your answers in answers.py. It contains a dictionary where the keys are the aliased algorithms; you just need to enter the correct values (‘bubble’, ‘selection’, ‘insertion’, ‘merge’, or ‘quick’): answers = {‘alg_a’: ”, ‘alg_b’: ”, ‘alg_c’: ”, ‘alg_d’: ”, ‘alg_e’: ”} Lab Notes • generate_numbers.py contains code to automate the generation of numbers.txt. • Each algorithm is used exactly once. • The bubble and insertion sorts are adaptive – they can sort in O(n) in the best case. • The quicksort algorithm always uses the last element in a sublist as the pivot. • The largest list you can create is 2000 items due to resource constraints on Gradescope. Submitting Students must submit individually by the due date (typically, Sunday at 11:59 pm EST) to receive credit. Grading This assignment is entirely auto-graded: 20 points per correct algorithm.
So far in CSE 2050, we’ve analyzed five different sorting algorithms: bubble, selection, insertion, merge, and quick. Each of these sorting algorithms has their own set of strengths and weaknesses. Namely, each algorithm works best for certain categories of inputs (e.g., insertionsort has a O(n) running time on lists that have a constant number of items out of place.) But, which algorithm should you use for general purpose sorting (where you may not know of lot of information about the input sequences)? In many programming languages, the general purpose sorting algorithm used is actually a hybrid sorting algorithm that utilizes several different sorting algorithms under the hood. For instance, Python uses Timsort as its general purpose sorting algorithm. In this homework, we will be creating our own hybrid sorting algorithm: magicsort. None of the individual pieces of magicsort are too complicated on their own, but we need to proceed through this assignment methodically with test-driven development to ease the debugging burdens that may arise. As such, we’ll break down each piece of the overall magicsort algorithm into its own function and develop tests for that function alone. This ensures that it is working on its own before we move on and start calling it in subsequent functions. Part 1: linear_scan Step One In magicsort.py, implement a function named linear_scan(L) that takes a list as input and returns the particular MagicCase that applies to it. In the starter code, we’ve already defined MagicCase as an enumeration, which is just a set of symbolic names that are bound to unique values. Using enumerations, rather than plain integers, allows us to have much more readable and maintable code. If you are curious, the Python documentation for enumerations can be found here. The particular MagicCase that linear_scan should return is given by the following rules: • If L is already sorted, return MagicCase.SORTED. • If L is has fewer than e.g. 10 adjacent elements that are inverted (L[i-1] > L[i]), return MagicCase.CONSTANT_NUM_INVERSIONS. There is a global constant INVERSION_BOUND already defined in the starter code that you should utilize during this check. • If L is reverse sorted, return MagicCase.REVERSE_SORTED. • If none of the above cases apply, return MagicCase.GENERAL. Step Two In test_magicsort.py, create a test class for linear_scan and use the tests to ensure it exhibits the correct behavior on a variety of input lists before moving on. Examples Several examples of behavior shown below. >>> L = [1, 2, 3, 4, 5] >>> linear_scan(L) MagicCase.SORTED >>> L = [5, 4, 3, 2, 1] >>> linear_scan(L) 1 MagicCase.REVERSE_SORTED >>> L = [1, 2, 4, 3, 5] >>> linear_scan(L) MagicCase.CONSTANT_NUM_INVERSIONS Part 2: reverse_list Step One In magicsort.py, implement a function named reverse_list(L) that takes a list as input and efficiently reverse it in-place. You function should proceed as follows: • swaps the first and last elements, then • swaps the second and penultimate elements, then • . . . repeats this pattern until the list is sorted. This function should run in O(n) time with O(1) memory overhead. Step Two In test_magicsort.py, create a test class for reverse_list and use the tests to ensure it exhibits the correct behavior on a variety of input lists before moving on. Part 3: magic_insertionsort Step One In magicsort.py, implement a function named magic_insertionsort(L, left, right) that takes an input list along with indices left/right and uses insertion sort to sort (in-place) ONLY the sublist given by L[left:right]. This function should: • have O(n) running time when O(1) items are out of place (i.e., when MagicCase.CONSTANT_NUM_INVERSIONS applies) • have O(n 2 ) worse-case running time • have O(1) memory overhead – since its in-place and writes directly to the input list Step Two In test_magicsort.py, create a test class for magic_insertionsort and use the tests to ensure it exhibits the correct behavior on a variety of input lists before moving on. Examples Example behavior shown below. >>> L = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> magic_insertionsort(L, left=2, right=5) >>> print(L) [9, 8, 5, 6, 7, 4, 3, 2, 1, 0] 2 Part 4: magic_mergesort Step One In magicsort.py, implement a function named magic_mergesort(L, left, right) that takes an input list along with indices left/right and uses merge sort to sort ONLY the sublist given by L[left:right]. This function should: • call magic_insertionsort to sort sublists with 20 items or fewer, as quadratic sorting algorithms actually outperform merge sort on very small lists • have O(n log n) worse-case running time • have O(n) memory overhead Step Two In test_magicsort.py, create a test class for magic_mergesort and use the tests to ensure it exhibits the correct behavior on a variety of input lists before moving on. Examples Example behavior shown below. >>> L = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> magic_mergesort(L, left=2, right=5) >>> print(L) [9, 8, 5, 6, 7, 4, 3, 2, 1, 0] Part 5: magic_quicksort Step One In magicsort.py, implement a function named magic_quicksort(L, left, right, depth=0) that takes an input list along with indices left/right and uses quick sort to sort ONLY the sublist given by L[left:right]. This function should: • Use the last item in a sublist as the pivot element. This does not give optimal results, but it allows us to analyze how magicsort handles edge cases. • Keep track of the recursion depth. If depth ever gets too large, indicating that we are choosing poor pivots, this function should call magic_mergesort to sort that particular sublist (this prevents us from experiencing the dreaded O(n 2 ) worst-case running time of quick sort). – The best-case maximum depth for quick sort should be log2 (n) + 1. Since the pivot will not always be the median element, we expect the actual depth to be a bit higher. However, if the depth ever exceeds twice the best-case maximum depth, sort the sublist using magic_mergesort. You can use math.log2() for these calculations. • call magic_insertionsort to sort sublists with 20 items or fewer, as quadratic sorting algorithms actually outperform quick sort on very small lists. • have O(n log n) average and worse-case running times because we transition to magic_mergesort if the pivot selection is bad. • have O(log n) memory overhead, due to the function call stack (unless magic_mergesort is invoked). Step Two In test_magicsort.py, create a test class for magic_quicksort and use the tests to ensure it exhibits the correct behavior on a variety of input lists before moving on. 3 Examples Example behavior shown below. >>> L = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> magic_quicksort(L, left=2, right=5) >>> print(L) [9, 8, 5, 6, 7, 4, 3, 2, 1, 0] Part 6: magicsort Step One We’re finally ready to fully implement our hybrid sorting algorithm! In magicsort.py, implement a function named magicsort(L) that takes an input list and does the following: • Calls linear_scan on the list to determine which MagicCase it falls into. • If the input falls into the SORTED, CONSTANT_NUM_INVERSIONS, or REVERSE_SORTED cases, immediately return or call the approriate linear time sorting method. • If the input falls into the GENERAL case, call magic_quicksort on L with left and right set to 0 and len(L), respectively. Your magicsort algorithm should: • mutate the input list so that it is in a sorted state upon return. In other words, to sort a list L we would use magicsort(L) rather than L = magicsort(L). • keep track of which of the sub-algorithms are invoked during the overall sorting process and return them as a set. I recommend adding an additional alg_set=None default formal parameter to each of the sorting functions from parts 2-5 to help handle this. Step Two In test_magicsort.py, create a test class for magicsort and use the tests to ensure it exhibits the correct behavior on a variety of input lists. Examples Several examples of behavior shown below. >>> L = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> magicsort(L) {‘reverse_list’} >>> print(L) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> L = [1, 2, 4, 3, 5] >>> magicsort(L) {‘magic_insertionsort’} >>> print(L) [1, 2, 3, 4, 5] >>> # the following list is structured to give very poor pivots in quicksort >>> # when choosing the last element as the pivot. >>> # this should result in an invocation of magic_mergesort. >>> # once the sublists get small enough, magic_insertionsort will also be invoked. 4 >>> L = list(range(10)) + list(reversed(range(10,100))) >>> magicsort(L) {‘magic_quicksort’, ‘magic_mergesort’, ‘magic_insertionsort’} >>> print(L) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] Imports No imports are allowed on this assignment, with the exception of: • enum: for the MagicCase enumeration (this is already defined in starter code). • math: for calculating the best-case recursive depth for quick sort. • unittest and random: for testing purposes. • typing: not required, but students have requested it in the past. Grading This assignment is 100% manually graded. Your code will be graded on structure, efficiency, readability, and correctness. Submission Submit the following files: • magicsort.py • test_magicsort.py Students must submit individually to Gradescope by the posted due date (Tuesday, March 19th at 11:59pm) to receive credit.
The Ordered List ADT is similar to a list, but adds the requirement that items remain sorted: • add(item) – adds item to the list. • remove(item) – removes the first occurrence of item from the list. Raise a RuntimeError if the item is not present. • getitem(index) – returns the item with the given index in the sorted list. This is also known as selection. • contains(item) – returns True iff there is an item of the list equal to item. • iter – returns an iterator over the ordered list that yields the items in sorted order. • len – returns the length of the ordered list. We have provided a working Ordered List in lab6.py. The starter code includes 3 ways of implementing contains: • _bs(???) – up to you to implement. Should be O(logn). • _contains_list(item) – uses python’s built-in list search. O(n). • contains_bs_slow(item) – uses a binary search built on slicing. O(n). def __contains__(self, item): return self._bs(item, 0, len(self)) # Requires _bs() for this to work # alternative search algorithms: # return self._contains_list(item) # uses python’s default list-search # return self._contains_bs_slow(item) # uses a slow version of binary-search (slicing) Deliverable – _bs() Implement a O(logn) binary search. You’ll need to pass left/right indices insted of list slices with each recursive call to do this. Note that TesetLab6.py, included with the starter code, tests the contains method. It may be helpful to write test cases of your own, especially if you are struggling to parse what the provided tests are doing. The basic flow for a test here is: my_list = OL() # (1) Create a list self.assertFalse(‘a’ in my_list) # (2) Assert an item *is not* in that list my_list.add(‘a’) # (3) Add that item to the list self.assertIn(item, my_list) # (4) Assert that item *is* in the list Submission At a minimum, submit the following files: • lab6.py Students must submit individually by the due date (typically, Sunday at 11:59 pm EST) to receive credit.
Part 1: Implementing Recursive Sorting Algorithms In this part of the homework, you will implement three sorting algorithms: bubble sort, selection sort, and insertion sort, recursively. Each sorting algorithm should return the sorted array and the number of swaps made during the sorting process. Your implementation should aim to be as efficient as possible, with no unnecessary comparison steps and no swaps if not needed. Additionally, you should ensure that both bubble sort and insertion sort maintain O(n) time complexity in the best case. Example on number of swaps: >>> sort_list = [i for i in range(5)] >>> sorted_arr, n_swaps = bubble_sort(sort_list) >>> print(n_swaps) 0 >>> rev_sorted =[i for i in range(5,0,-1)] >>> sorted_arr, n_swaps = bubble_sort(rev_sorted) >>> print(n_swaps) 10 >>> random_list =[3, 2, 5, 1, 4] >>> sorted_arr, n_swaps = bubble_sort(random_list) >>> print(n_swaps) 5 Part 2: Building Test Factory for Sorting Algorithms In this part of the homework, you will build a test factory to test the recursive sorting algorithms implemented in Part 1. The test factory should include test cases for an empty list, a sorted list, a reverse sorted list, and a randomly shuffled list. By using a test factory, you can avoid repeating the same tests for different sorting algorithms.Below is a graphical representation of how to structure the test factory: A test factory is a design pattern commonly used in software testing to streamline the creation of test cases and promote code reuse. It encapsulates the logic for generating test cases, making it easier to manage and maintain test suites, especially when dealing with multiple test scenarios or similar tests for different functions or classes. In the context of sorting algorithms, a test factory can be particularly useful for generating test cases to verify the correctness and performance of different sorting implementations. Instead of manually writing test cases for each sorting algorithm, a test factory allows us to define common test scenarios (e.g., empty list, sorted list, reverse sorted list, random list) once and reuse them across multiple sorting algorithms. It’s important to note that when using a test factory, certain test cases may need to be overridden or modified for specific classes or functions. For example, in the case of sorting algorithms like bubble sort and insertion sort, the test cases may be similar. However, for algorithms like selection sort, which works differently, some test cases in the TestSelection class may need to be overridden or adapted to accommodate these differences. This ensures that the test cases accurately reflect the behavior of each sorting algorithm being tested. Submission Submit the following files: hw6.py test_hw6.py Students must submit to Gradescope individually by the due date (typically Tuesday at 11:59 pm EST) to receive credit.
Model a circular board game consisting of numbered tiles. The numbers represent how many tiles you can move clockwise (CW) or counter-clockwise (CCW). It’s okay to loop around – moves that go before the first tile or after the last are valid. The goal is to reach the final tile (the tile 1 counter-clockwise from the start). Figure 1: (a) [3, 6, 4, 1, 3, 4, 2, 0] is solveable in 3 moves. (b) [3, 4, 1, 2, 0] is unsolveable. While not shown, moving 3 spaces CCW at the start would also be a valid first move. SolvePuzzle.py • solve_puzzle(board) returns a boolean denoting if board is solveable. >>> solve_puzzle([3, 6, 4, 1, 3, 4, 2, 0]) True >>> solve_puzzle([3, 4, 1, 2, 0]) False Tips • Use memoization to to avoid infinite loops • You can assume the numbers on tiles are non-negative integers (0 is valid, and may appear on any tile) • The modulo operator % is helpful for finding indices when you loop around • Add unittests to TestSolvePuzzle.py to help debug Submission At a minimum, submit the following files: • solve_puzzle.py • test_solve_puzzle.py Students must submit individually by the due date (typically Sunday at 11:59 pm EST) to receive credit.
Part 1 – Recursion on a Linked List Linked lists can be thought of as recursive structures. Every linked list is either: • the empty list, or • a node that links to a linked list This makes them a great playground for implementing various types of recursive functions. We provide starter code that demonstrates a few methods of recursion in a LinkedList, and you will implement a few more. Starter Code The LinkedList class is already fully implemented. It is essentially a wrapper – the LLNode class does all the interesting recursion. In LLNode, we have implemented: • __init__ • __len__() • __repr__() • get_tail() __len__(), __repr__(), and get_tail() show various examples of recursive LLNode functions. Study them to understand how they work, then implement the following LLNode methods. Note that we have listed the parameters you should use – this is a great hint into how you can efficiently structure your code. Do not change these. • add_last(self, item) – recursively call on linked node until you hit the tail, at which point you should add a new node – we are not keeping track of a tail node, so this has O(n) running time • sum_all(self) – recursively add all items in linked list and return the sum – O(n) • contains(self, item) – recursively call on linked node until you either: ∗ find the item and return True, or ∗ hit the end of the list without finding the item and return False – O(n) running time • remove_all(self, item) – recursively removes all nodes holding item in linked list – O(n) running time • reverse(self) – recursively reverses the linked list contained in self.link unless it is the tail node – after reversing the linked list in self.link, puts itself at the end of the reversed list – this method should return the new head of the list (i.e., the old tail) – O(n) running time 1 Part 2 – Rolling Dice to a Total Given an n-sided die, we want to determine how many different ways one could repeatedly sum die rolls and get to a given total. For instance, given a 4-sided die, we could obtain a total of 3 in four different ways: • 1 + 1 + 1 (rolling a 1 three times) • 1 + 2 (rolling a 1 and then rolling a 2) • 2 + 1 (rolling a 2 and then rolling a 1) • 3 (rolling a 3) We will write two different functions to solve this problem. Each functions takes n (the number of sides on the die) and total (the total to which we’ll sum rolls) as input. Each function must use its corresponding dynamic programming methodology in order to solve the problem. • ways_to_sum_memo(n, total) – must use memoization • ways_to_sum_tab(n, total) – must use tabulation >>> ways_to_sum_memo(n=4, total=3) 4 >>> ways_to_sum_tab(n=4, total=3) 4 Imports No imports allowed on this assignment, with the following exceptions: • Any modules you have written yourself • typing – this is not required, but some students have requested it • For testing only (do not use these for functionality in any other classes/algorithms): – unittest – random Submission Requirements Students must submit individually by the due date. At a minimum, you must submit the following files: • linked_list.py • ways_to_sum.py Additionally, you must include any other files necessary for your code to run, such as modules containing data structures you wrote yourself. Note that we are not requiring tests here. We have instead provided tests for you. We’ll begin requiring tests again for the next homework, but we are prioritizing giving you multiple chances to practice recursion this week, since it’s an area where we typically need a lot of practice. See here for some more practice problems. 2 Grading This assignment is 100% manually graded. Your code will be graded on structure, efficiency, readability, and correctness. Autograder results are not fully indicative of your submission’s grade. Egregiously poor structural descions, non-recursive solutions, or brute forcing unittests with will not receive any credit.
Create the fundamental Node and LinkedList classes using test driven development (TDD). Part 1 – class Node Create two files: linkedlist.py and test_linkedlist.py. Implement unittests and functionality for a Node class as described below. Figure 1: Class diagram for Node. Note the use of expected types after colons. Node | None denotes it can be a Node object or the None object. Optional[Node] means there is an optional Node parameter that defaults to None. • init(self, item:Any, link:Optional[Node]) -> None – Creates a new Node object. link is either another Node or the None object • repr(self) -> str – Returns a string representaiton of the object, e.g. Node(Jake) – This is a dunder method: __repr__() TDD Flow: 1) init • Red: test_linkedlist.py, TestNode class: – Create a node, and assert it has the correct attributes, e.g. node1 = Node(…) self.assertEqual(node1.item, …) self.assertEqual(node1.link, …) • Green: linkedlist.py, Node class: implement __init__ 2) repr • Red: test_linkedlist.py, TestNode class: – Create a node, and assert it has the correct repr() return, e.g. node1 = Node(…) self.assertEqual(repr(node1), “Node(…)”) • Green: linkedlist.py, Node class: implement __repr__ Readability Note You should (almost) always call dunder methods using their “magic” syntax. E.g.: 1 • repr(node1) instead of node1.__repr__() • x + y instead of x.__add__(y) • object1 == object2 instead of object1.__eq__(object2) • len(collection) instead of collection.__len__() This applies to test cases and functionality within a class. The magic syntax is preferred because it improves readability. The only common exception is when calling super().__init__. Part 2 – class LinkedList In the same files as above, but in different classes (LinkedList and TestLinkedList), implement the LinkedList class as described below. Figure 2: Class diagram for LinkedList. Note that items in LinkedList.__init__ is an optional paramter (it defaults to None, and it can be any iterable if included. This means lists, tuples, sets, dictionaries, strings, or even the range object are fair game.) • init(self, items: Optional[Iterable[Any]) -> None – optional collection items are sequentially added to LinkedList if included – use add_last() to add items in correct order • get_head(self) -> Any | None – Returns item stored in self._head, or None for an empty LinkedList • get_tail(self) -> Any | None – Returns item stored in self._tail, or None for an empty LinkedList 2 • add_first(self, item: Any) -> None – adds a node to the front of the LinkedList with item • add_last(self, item: Any) -> None – adds a node to the end of the LinkedList with item • remove_first(self) -> Any – removes first node from LinkedList and returns its item – raises a RuntimeError if LinkedList is empty when called • remove_last(self) –> Any – removes last node from LinkedList and returns its item – raises a RuntimeError if LinkedList is empty when called Flow: 1) Empty initialization • Red: test_linkedlist.py, TestLinkedList class: – Create empty LinkedList e.g. LL1 = LinkedList() – Assert length is correct (should be 0) – Assert get_head() and get_tail() return correct values (should be None) • Green: linkedlist.py, LinkedList class: – Implement __init__, __len__, get_head(), and get_tail() 2) add_last • Red: test_linkedlist.py, TestLinkedList class: – Create an empty LinkedList – Using a for loop, sequentially add items to end of LinkedList. With each add, assert that you get the correct values from: ∗ len() ∗ get_head() ∗ get_tail() • – Green: linkedlist.py, LinkedList class: ∗ Implement add_last 3) Non-empty initialization • Red: test_linkedlist.py, TestLinkedList class: – initialize a new linked list with some iterable, e.g.: ∗ LL1 = LinkedList([‘a’, ‘b’, ‘c’]) ∗ LL1 = LinkedList(range(10)) – Test you get correct values from len, get_head(), and get_tail() • – Green: linkedlist.py, LinkedList class: ∗ Finish implementing __init__ ∗ See note on default parameters below 4) add_first • Test similar to add_last • Implement 5) remove_first • Red: test_linkedlist.py, TestLinkedList class: – Build up a linked list (either create a non-empty list, or use add_first or add_last) – Iteratively call remove_first() until the LinkedList is empty. With every remove_first() call, assert you get correct values from: ∗ remove_first() (should return item in first node) 3 ∗ len() ∗ get_head() ∗ get_tail() • Green: linkedlist.py, LinkedList class: – implement remove_first() • Red: test_linkedlist.py, TestLinkedList class: – Assert that you get a RuntimeError when removing from an empty LinkedList. • Green : linkedlist.py, LinkedList class: – Implement that error in remove_first() 6) remove_last • test_linkedlist.py: similar to remove_first() above • linkedlist.py: similar to remove_first() Note on default parameters As we begin to make our own data structures, we will often want to give users the option to pass in a starting collection. It is tempting to use an empty list as a default value to allow this, but that is bad practice. Python only initializes default arguments for a method once, so mutable default arguments end up being shared across all instances of a class: >>> class MyListWrapper: … def __init__(self, L=[]): # Empty list is a BAD default, because it is mutable … self.L = L … >>> x = MyListWrapper() # x.L is the default empty list >>> y = MyListWrapper() # y.L is the SAME default list >>> x.L.append(3) >>> x.L [3] >>> y.L [3] >>> If we want to make a custom collection with an optional collection of arguments, we should use an immutable like None for our default list, and create an empty list on the fly inside of our constructor method init: >>> class BetterListWrapper: … def __init__(self, L=None): … if L is None: … self.L = [] # new empty list created for every object … else: … self.L = L # whatever the user passed in … >>> x = BetterListWrapper() >>> y = BetterListWrapper() >>> x.L.append(3) >>> x.L [3] >>> y.L 4 [] You should use a similar pattern for your LinkedList.__init__() method, e.g.: class LinkedList: def __init__(self, items=None): # …initialize LinkedList attributes # if user passed in a collection, add them one at a time if items is not None: for item in items: self.add_last(item) Submitting At a minimum, submit the following files: • linkedlist.py • test_linkedlist.py Students must submit individually by the due date (typically, Sunday at 11:59 pm EST) to receive credit. We are unfortunately not able to autograde your unittests – this means we cannot give you instant feedback on whether your tests are correct or not. Make good use of your lab time by asking your classmates and lab instructor to look over your tests. Learning to write good tests is one of the best ways to reduce the difficulty of coding.
Question 1: Reversable LinkedList Create a ReversableLinkedList class that extends your LinkedList class. In object-oriented programming, “extends” means you inherit from that class and add some functionality via starter attributes or new methods. The only method you need add to to the public interface is reverse(). This method should reverse the direction of the Linked List by redirecting all link attributes. Note that you should not create any new objects (no new nodes or lists) inside this method – just relink the nodes you already have, making sure to update _head and _tail as appropriate: Figure 2: The same ReversableLinkedList object rLL_1 before and after reversing. All that changes are node pointers: _head, _tail, and all .link attributes. No new node objects are created. reverse() should be O(n). Examples >>> rLL1 = ReversableLinkedList(‘abcd’) >>> isinstance(rLL1, ReversableLinkedList), isinstance(rLL1, LinkedList) (True, True) >>> rLL1.get_head(), rLL1.get_tail() # head->a->b->c->d>> rLL1.reverse() >>> rLL1.get_head(), rLL1.get_tail() # tail->a>> sLL1 = SortedLinkedList() >>> isinstance(sLL1, SortedLinkedList), isinstance(sLL1, LinkedList) (True, True) >>> sLL1.add_first(8) # don’t want this in the public interface anymore … NotImplementedError >>> sLL1.add_sorted(8); sLL1.add_sorted(3); sLL1.add_sorted(11); sLL1.add_sorted(1) >>> sLL1.add_sorted(9) >>> while sLL1: # sLL1 evaluates as true until empty becuase it provides __len__ print(sLL1.remove_first()) … 1 3 8 9 11 3 Question 3: UniqueLinkedList Write a class UniqueLinkedList that extends LinkedList and adds an additional method – remove_dups(). This method should remove any nodes with duplicate items from your LinkedList, only keeping the earliest node with that item. Return a dictionary of item:count representing how many copies of each item were removed, including a count of 0 for any items that only occured once. Note that you should not create any new new nodes or linked lists inside this method – just relink the nodes you already have. When the function ends, your linked list should not have any duplicates: remove_dups() should be O(n) Examples >>> uLL1 = UniqueLinkedList([‘d’, ‘a’, ‘d’, ‘b’]) >>> is_instance(uLL1, UniqueLinkedList) True >>> is_instance(ull1, LinkedList) True >>> len(uLL1) 4 >>> uLL1.get_head() ‘d’ >>> uLL1.get_tail() ‘b’ >>> print(ull1.remove_dups()) {‘d’:1, ‘a’:0, ‘b’:0} >>> while uLL1: # uLL1 evaluates as True until empty because it provides __len__ print(uLL1.remove_first()) d a b 4 Imports No imports are allowed on this assignment, with the following exceptions: • LinkedList and Node classes from linkedlist.py • typing (not required, but you’re welcome to use it if you’d like) • For testing only (do not use these for functionality in any other classes/algorithms) – unittest – random Submission Requirements Students must submit individually by the due date (Tuesday, February 20th at 11:59 pm EST) to receive credit. This deadline is after the first exam, but it will help you immensely to have solved these problems before the exam. At a minimum, you must submit the following files: • From Mod 4 Lab: – linkedlist.py ∗ class Node ∗ class LinkedList • Written for this assignment: – extendedlinkedlists.py ∗ class ReversableLinkedList(LinkedList) ∗ class SortedLinkedList(LinkedList) ∗ class UniqueLinkedList(LinkedList) Additionally, you must include any other files necessary for your code to run, such as modules containing data structures you wrote yourself.
Part 1 – Timing Functions Start by writing a basic function time_function(func, args) that returns the number of seconds to run func with args. TimeFunctions.py contains some trials that should have a running time ratio of ~10x to help test your function. Starter code if __name__ == ‘__main__’: def test_func(L): for item in L: item *= 2 L1 = [i for i in range(10**5)] t1 = time_function(test_func, L1) L2 = [i for i in range(10**6)] t2 = time_function(test_func, L2) print(“t(L1) = {:.3g} ms”.format(t1*1000)) print(“t(L2) = {:.3g} ms”.format(t2*1000)) Expected behavior in terminal: $ python3 TimeFunctions.py t(L1) = 4.99 ms t(L2) = 51.9 ms Part 2 – Better Results Running your function one time leaves a lot of room for noise – other processes are vying for resources on your computer. We can get a better reading by running the function multiple times and returning just the minimum. Note that we should use the minimum time from multiple trials, not the average, as that is probably the trial with the least amount of noise. Modify time_function to take an extra parameter, n_trials, which defaults to 10. Return the minimum time from 10 trials. Note – python let’s you use “infinity” with float(‘inf’). This may be helpful here. Part 3 – More flexible functions Your method as-is probably can only time functions that take a single argument. This is an issue if you want to handle functions with an arbitrary number of parameters. Say we have two addition methods: 1 def add_2_nums(p1, p2): return p1 + p2 def add_3_nums(p1, p2, p3): return p1+p2+p3 If we try to time these functions, we’ll get an error: >>> time_function(add_2_nums, 3, 4, n_trials=10) … TypeError : time_function() got multiple values for argument ‘n_trials’ Python thinks 4 is supposed to be the number of trials, rather than a second argument. We can use tuple unpacking to handle an arbitrary number of arguments instead. We’ll pack all of our arguments into a tuple, then unpack that tuple when we call the function we want to time: >>> def foo(f, args): … return f(*args) # The * unpacks “args” into separate arguments … >>> foo(add_2_nums, (3, 4)) 7 >>> foo(add_3_nums, (3, 4, 5)) 12 Add a function time_function_flexible() that operates as above, but it’s middle parameter should be a tuple of arguments: • f – the function to be executed • args – a tuple of an arbitrary number of arguments to be passed to f • n_trials – the number of trials you want to run Submitting At a minimum, submit the following files: • TimeFunctions.py Students must submit individually by the due date (typically, Sunday at 11:59 pm EST) to receive credit. 2
Problem 1 – remove_characters.py Write a function remove_characters(input_string, to_remove) that takes two inputs: • input_string : a string • to_remove: a string and returns a string that is exactly the same as the input_string but without any of the characters in to_remove. Your function must have a running time complexity of O(n), where n represents the length of input_string. For clarity, let m be the length of to_remove. Your code cannot have a running time complexity of O(mn) to receive full credit, it must be O(n). NOTE: you may not use any built-in string removal methods/functions in your code (e.g., str.strip()). Examples These examples are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own unittests to further test expected behaviors. >>> new_string = remove_characters(‘abcd’, ‘c’) >>> print(new_string) ‘abd’ Problem 2 – any_two_sum.py Write a function any_two_sum that takes two inputs: • numbers : a list of integers • total: an integer and returns True if any two integers in numbers sum to total and False otherwise. Your function must have a running time complexity of O(n), where n represents the length of numbers. Examples These examples are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own unittests to further test expected behaviors. >>> result = any_two_sum([1,3,4,5], 7) >>> print(result) True 1 >>> result = any_two_sum([1,3,4,5], 2) >>> print(result) False Problem 3 – contains_permutation.py Write a function contains_permutation that takes two inputs: • input_string : a string • pattern: a string and returns True if input_string contains a substring (group of consequtive characters) that is a permutation of pattern and False otherwise. Your function must have a running time complexity of O(n), where n is the length of input_string. For clarity, a permuation of pattern would be a string of equal length that use the exact same characters, but in any order. For example, ‘abc’ is a permutation of ‘cab’. Examples These examples are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own unittests to further test expected behaviors. >>> result = contains_permutation(‘abcdef’, ‘cab’) >>> print(result) True >>> result = contains_permutation(‘keyboard’, ‘boy’) >>> print(result) True >>> result = contains_permutation(‘patriots’, ‘sit’) >>> print(result) False Imports We do not allow imports on any homework or lab assignments, except for those explicitly specified by that assignment. Due to the ubiquitous nature of the problems we are solving, there are often modules that trivialize the assignments when imported, so we restrict imports to ensure you’re learning all relevant techniques. Do not import any modules except for those you write yourself, or any exceptions below: • You can import the unittest and random modules for testing purposes. • You may import typing – not required, but some students have requested this module. Grading Some of the functionality will be auto-graded. However, we will manually grade for structure, readability, efficiency, and testing – ensure that: • Every function has a docstring (more info) 2 • Code is well commented – you don’t need a comment on every line, but don’t assume because you know what something does that a stranger (or you in two months) will understand it. • You use consistent variable naming conventions (see the Python style guide) • Required running time complexities are met. • Every function has a set of comprehensive unit tests (submitted in a separate file as shown below). Submitting Submit the following files: • remove_characters.py • test_remove_characters.py • any_two_sum.py • test_any_two_sum.py • contains_permutation.py • test_contains_permutation.py Students must submit to Gradescope individually by the due date (typically Tuesday at 11:59 pm EST) to receive credit. Optional Challenge Problem – minimum_substring.py Write a function minimum_substring that takes two inputs: • input_string : a string • to_match: a string and returns the smallest substring (group of consequtive characters) of input_string that contains all of characters within to_match, if it exists. Otherwise, your function should return None. You function must have a running time complexity of O(n). Examples These examples are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own unittests to further test expected behaviors. >>> result = minimum_substring(‘abcdef’, ‘cab’) >>> print(result) ‘abc’ >>> result = minimum_substring(‘keyboard’, ‘boy’) >>> print(result) ‘ybo’ >>> result = minimum_substring(‘patriots’, ‘sit’) >>> print(result) ‘iots’ 3
By now, you’ve encountered the limitations of our autograder – it prints the results of our test cases, but those results can be difficult to interpret. In this assignment, you will create your own suite of test cases to serve as a local autograder. This is the core loop in this course: write a unittest, implement the funcitonality, repeat.Test-Driven Development Test-driven development, or TDD, involves three stages often referred to as Red-Green-Refactor: • Red – write a test, then run your code to verify that the test case fails • Green – modify your code until the test passes • Refactor – extract duplicate algorithms/classes into a parent function/superclass. Phase 1 – Red For instance, let’s say we are creating a class called Point to store a 2-D point. We might create the following skeleton code and unittest for our first TDD loop: Point.py class Point: def __init__(self, x, y): “””Initializes a 2-D point with x- and y- coordinates””” pass TestPoint.py import unittest from Point import Point # import class Point from file Point.py class TestPoint(unittest.TestCase): def setUp(self): “””Create some points for future tests””” self.p1 = Point(3, 4) self.p2 = Point(5, 6) def test_init(self): “””Tests that points are initialied with the correct attributes””” self.assertEqual(self.p1.x, 3) self.assertEqual(self.p1.y, 4) def test_eq(self): “””ADD YOUR OWN DOCSTRING””” def test_equidistant(self): “””ADD YOUR OWN DOCSTRING””” def test_within(self): “””ADD YOUR OWN DOCSTRING””” 1 Run TestPoint.py, and you should see something like the following: $ python3 ./TestPoint.py ..E. ====================================================================== ERROR: test_init (__main__.TestPoint.test_init) Tests that points are initialied with the correct attributes ———————————————————————- Traceback (most recent call last): File “.TestPoint.py”, line 12, in test_init self.assertEqual(self.p1.x, 3) ˆˆˆˆˆˆˆˆˆ AttributeError: ‘Point’ object has no attribute ‘x’ ———————————————————————- Ran 4 tests in 0.001s FAILED (errors=1) Now, we celebrate! Our test fails – it is a good test, and we are ready to move on to phase 2 – Green. Phase 2 – Green Next, we implement the init method. Modify Point.__init__ to store x- and y- attributes: class Point: def __init__(self, x, y): “””Initializes a 2-D point with x- and y- coordinates””” self.x = x self.y = y Run our code again to make sure it passes: python .TestPoint.py …. ———————————————————————- Ran 4 tests in 0.000s OK Everything works! We don’t have any code to refactor, so we are done with the first TDD loop. Now we write the second unittest, run it, implement functionality, and run it again. Practice TDD in pairs Your turn. Implement functionality one unittest at a time. Follow this flow: 1) Write a single unittest in TestPoint.py 2) Run TestPoint.py to verify you have 1 failure 3) Implement functionality in Point.py 4) Run TestPoint.py to verify you have 0 failures You should use pair programming for this lab (during lab time – you’ll have to do it solo if you are not 2 able to finish during lab). Only one partner should be logged on to their computer. The other partner looks on. The logged in partner (the coder) writes and runs the code, explaining what they are doing to the other partner (the observer), who can make suggestions and ask questions. Switch off after every test. Partners should share their code using e.g. a cloud link or email at the end of class, since both partners need to submit individually to receive creit. Use this flow until you have implemented the following functionality in Point.py: • Point.__eq__(self, other) – returns True iff self and other have the same x and y attributes – Use at least two assertions in your unittest method TestPoint.test_eq(): ∗ Use self.assertEqual() to confirm that 2 points with the same x- and y- compare as equal ∗ Use self.assertNotEqual() to confirm that 2 points with different x- and y- do not compare as equal • Point.equidistant(self, other): – returns True iff self and other are the same distance from the origin ∗ Use sqrt(x 2 + y 2 ) to find the distance from the origin (e.g. (x**2 + y**2)**(1/2)) – Use at least three assertions in your unittest method TestPoint.test_eq(): ∗ Use self.assertEqual() to confirm that 2 points with the same distance from origin and the same x and y attributes compare as equal ∗ Use self.assertEqual() to confirm that 2 points with the same distance from origin but different x and y attributes compare as equal ∗ Use self.assertNotEqual() to confirm that 2 points with different distances from origin do not compare as equal • Point.within(self, distance, other) – returns True iff self and other are within distance from each other – As above, use the pythagorean theorem to find the distance between two points; i.e. sqrt((x2 − x1)2 + (y2 − y1)2 ) – Use at least 2 assertions. As above, self.assertEqual() for two points that are within some distance of each other and self.assertNotEqual() for two points that are not within some distance of each other Reminders Do not import any modules except for those you wrote yourself (e.g. Point.py) and: • unittest If you are using the same point in multiple unittests, attach them to your unittest.TestCase object in the setUp method, as shown above. This method is run at the start of every unittest. Every method should have a docstring, including unittests. Grading Gradescope only looks at functionality here, but the goal of this lab is to get comfortable writing tests. Show your TA your tests as you go, and they’ll give you feedback on whether they’re good or not. To earn participation credit on this lab, you need to show your TA your full suite of test cases before leaving lab. 3 Submitting At a minimum, submit the following files: • Point.py • TestPoint.py Students must submit individually by the due date (typically, Sunday at 11:59 pm EST) to receive credit.
In this homework assignment, you will design and implement a basic social network system using objectoriented programming principles in Python. The focus will be on utilizing inheritance and composition relationships between classes to model the structure of the social network. +————-+ | Activity |
This lab will walk you through the process of: • navigating your computer’s file structure – create new files and folders • writing python code • running python code This lab is cooperative – talk with your partner as you go through, and make sure you are progressing together. It is fine for only one person to be coding during lab while the other looks on and discusses what’s happening – this is called pair programming. Make sure to share the files at the end, since both lab partners must submit individually to recieve credit. Part 1 – Setup your filesystem All modern operating systems use a hierarchal file structure. We can think of this as a tree – the top level directory, often referred to as root, contains all the files and folders on your computer. The exact names of various folders changes based on your operating system, but the general structure is a root directory which contains both the files necessary for various prorams to run and the files created and used by individual users: It’s often nice to collapse this visual diagram to a text-based one, like this: |root | |program files | | |python | | |–python.exe | | |–(other files/folders) | | | | |discord | | |–discord.exe | | |–(other files/folders) | | | | |firefox 1 | | |–firefox.exe | | |–(other files/folders) | | |users | | |jake | | | |documents | | | |–Resume.docx | | | |–Grades.xls | | | |–(other files/folders) | | | | | | |pictures | | | | |rachel | | | |documents (omitted for space) For this class, we want to create a folder called cse2050 in your user’s directory. On your lab PC, your username will be your netID (e.g. jas14034). Then, create a subfolder called labs, and another called lab1. Put a file called hello.py inside of that folder. Your ultimate file structure should look something like this: |root | |users | | |jas14034 | | | |cse2050 | | | | |labs | | | | | |lab1 | | | | | |–hello.py | (other users omitted) | | |program files | | (program files omitted) Open the folder lab1 in an integrated developing environment (IDE) of your choice, add some code to print something out, and run it. The lab PCs include Visual Studio and Spyder as IDEs, and you are free to use whatever you want on your local PC for homework assignments. This can all be a little overwhelming the first time you see it. If you’re not sure how to create a folder on your computer, ask around – another classmate or your TA can help. It’s important that we get used to asking each other for help; it will make the rest of this course much smoother. You can also see the attached video VisualStudio_hello.mp4 to see how to create a folder, open it, create a file in that folder, write some code, and run it on the lab PCs using Visual Studio. STOP – at this point, you and your partner should be able to navigate the file structure on your computer, including creating files. You should also be able to write a basic python script, run it, and see its output. Make sure you are comfortable with the above (ask classmates or the TA if you need assistance) before moving on. 2 Figure 1: Workspace set up video Part 2 – Modifying ‘hello.py“ Now that your comfortable with your comptuer’s file system, it’s time to write some more intricate Python code. Add a function say_hi() to the file hello.py you created in Part 2. This function should just return the string Hello, world for now. def say_hi(): return “Hello, world” Part 3 – Submit code to Gradescope Next, we’ll submit our code to Gradescope. Click the Gradescope link in HuskyCT, then select the appropriate assignment. Submit the file hello.py you made earlier. The autograder takes a minute or two to run. Once it completes, you should see 10/100 points for this assignment if hello.py is correct. Read over the error messages for the test cases you failed to get an idea of why they failed (largely, they depend on the file lab1.py, which you have not yet created and did not submit.) STOP – make sure your partner is done here before continuing. Rinse and repeat Now, we’ll continue to work on our code and re-submit until we pass all test cases. To complete this assignment, create a new file called lab1.py. This file should have a single function named generic_hi() 3 which takes one argument: a name to add to the return string: >>> generic_hi(‘jake’) ‘Hello, jake!’ >>> generic_hi(‘greninja’) ‘Hello, greninja!’ >>> generic_hi() ‘Hello, world!’ Note that your function needs a default value (‘world’ in this case) to plug in to the return string if the user does not specify one. External Modules Do not use any imported modules (math, collections, . . . ) when implementing functionality. It is okay to use imported modules for testing. It is okay to import modules you write yourself; e.g. any data structures you write yourself. Submitting STOP!. Before you go, make sure to backup your files using a cloud service like Onedrive. At a minimum, submit the following files for this lab: • hello.py • lab1.py Students must submit individually by the due date (typically, Friday at 11:59 pm EST) to receive credit.
You’ll write 3 functions in 3 different files (1 each, for a total of 3 functions) for this homework. We provide 1 of the files with skeleton code for the function; you will have to create the other two yourself. Gradescope will automatically check for correct file names, function names, and docstrings in required functions when you submit. (Note – every function you write in this class should have a docstring, but gradescope only automatically checks the functions we explicitly ask for. If you write extra functions, make sure to include docstrings for them as well). Neccesary files: • fizzbuzz.py (provided) • anagrams.py (not provided) • letters.py (not provided) We also provide some files you do not need to submit, but will be helpful for locally testing letters.py: • frost.txt • empty_file.txt Imports We do not allow imports on any homework or lab assignments, except for those explicitly specified by that assignment. Due to the ubiquitous nature of the problems we are solving, there are often modules that trivialize the assignments when imported, so we restrict imports to ensure you’re learning all relevant techniques. Do not import any modules except for those you write yourself, or any exceptions below: • You can import string for Problem 3 – count_letters Problem 1 – fizzbuzz.py Write a function fizzbuzz(start, finish) that prints numbers from start to finish. Replace multiples of 3 with “fizz”, multiples of 5 with “buzz”, and multiples of both with “fizzbuzz”. Once you have a working algorithm, edit it to also replace numbers that contain 3 or 5 (e.g. 13, 52) with “fizz”, “buzz”, or “fizzbuzz”, as appropriate. >>> fizzbuzz(1, 15) 1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 1 fizz 14 fizzbuzz Problem 2 – anagrams.py Write a function is_anagram(word1, word2) that compares two strings and returns a boolean denoting whether they are anagrams. >>> is_anagram(‘rat’, ‘tar’) True >>> is_anagram(‘rat’, ‘hat’) False >>> is_anagram(‘meat’, ‘team’) True Problem 3 – letters.py Write a Python function count_letters(file) for counting letters in a text file. • Input: name of file relative to the present working directory pwd (see below), e.g. count_letters(‘frost.txt’) if ‘frost.txt’ is in the pwd • Output: return the dictionary of letter:count pairs. Only include letters present in the file. • Use a dictionary to hold a mapping between a letter and its number of occurrences. • Ignore characters and symbols that are not standard ascii characters (only use characters that appear in string.ascii_lowercase) • Ignore case; e.g. consider ‘Treat’ as having 2 ‘t’s instead of 1 T and 1 t. • Reading files – You can use open to open a file. It creates an iterator that goes through the file, line by line. The example below shows how to iterate over the provided file frost.txt, printing every line: >>> f = open(‘frost.txt’) >>> for line in f: … print(line, end=”) … Fire and Ice Some say the world will end in fire, Some say in ice. From what I’ve tasted of desire I hold with those who favor fire. But if it had to perish twice, I think I know enough of hate To say that for destruction ice Is also great And would suffice. -Robert Frost 2 >>> f.close() Hints • frost.txt needs to be in your present working directory (pwd) for this to work. For instance, if your directory sturcure looks like this: cse2050/ |-homework/ | |homework1/ | | |-frost.txt | | |-count_letters.py | |homework2/ | … |-labs/ | |-lab1/ | | |-lab1.py | |-lab2/ | … there are a few directories we could be in: cse2050/, homework/, homework1/, homework2/, labs/, lab1/, and lab2/ are all valid directories in the tree pictured. Make sure your terminal is in the directory containing frost.txt, or you’ll get an error – this commonly happend when VSCode is open in a high level directory, like cse2050/, and you click the “play” button to run a python script in a nested directory: [jas14034@jas14034-vm cse2050]$ pwd /home/jas14034/cse2050 [jas14034@jas14034-vm cse2050]$ /bin/python3 /home/jas14034/cse2050/homework/homewor… …k1/count_letters.py Traceback (most recent call last): File “/home/jas14034/cse2050/homework/homework1/count_letters.py”, line 1, in f = open(‘./frost.txt’) FileNotFoundError: [Errno 2] No such file or directory: ‘./frost.txt’ My present working directory (pwd) is cse2050/, so my terminal cannot see frost.txt. It is able to find letters.py because VSCode supplies the absolute path (home/jas14034/…) to that file. An easy fix is to move into the directory containing the python script and text file you are interested in, then running your script with python3 from that directory: (use dir instead of cd and python instead of python3 on windows): [jas14034@jas14034-vm cse2050]$ cd homework/homework1/ [jas14034@jas14034-vm homework1]$ pwd /home/jas14034/cse2050/homework/homework1 [jas14034@jas14034-vm homework1]$ python3 ./count_letters.py Fire and Ice Some say the world will end in fire, Some say in ice. 3 From what I’ve tasted of desire I hold with those who favor fire. But if it had to perish twice, I think I know enough of hate To say that for destruction ice Is also great And would suffice. -Robert Frost Grading Most of the functionality will be auto-graded. We will manually grade for structure and readability – ensure that: • Every function has a docstring (more info) • Code is well commented – you don’t need a comment on every line, but don’t assume because you know what something does that a stranger (or you in two months) will understand it. • You use consistent variable naming conventions (see the Python style guide) Submitting Submit the following files: • fizzbuzz.py • anagrams.py • letters.py Students must submit to Gradescope individually by the due date (typically Tuesday at 11:59 pm EST) to receive credit. Challenges Hankering for more coding practice? We’ll occasionally provide stretch-goals or more difficult variants of homework problems. These are not for extra credit and are not required, they’re just here in case you want to dive a bit deeper into the content. Problem 3 Challenge Write a Python function letter_frequency(dict_letters) for finding the frequency of each letter in a dictionary. • As input, take a dictionary of letter:count pairs (output of the previous function) • Find the relative frequency of each letter (the ratio between the number of its occurrences and the total number of letters) • Return the new letter:frequency dictionary. • In Python, passing mutable objects like dictionaries can be considered as a call by reference – if you modify the dictionary passed to this function, the original dictionary will also be modified! In this problem, that’s a bad thing – don’t modify the original dictionary. Instead, create a new dictionary for holding frequencies. 4 • Example: >>> counts = letter_count(‘frost.txt’) >>> print(counts) {`a`: 13, `b`: 2, (24 letter:count pairs omitted)} >>> freqs = letter_frequency(counts) {‘a’: 0.06190476190476191, ‘b’: 0.009523809523809525, (24 pairs omitted)} Next, make a new file highest_freq.py. Import the functions you wrote in Part 1 and use them to implement a new function highest_freq(). highest_freq(file) should find the letter that has the highest frequency in a given txt file. • Return letter and its frequency. Example (‘e’, 0.12451162240025257) • Use the imported functions from letters.py to do this • Test your code with assert statements • Example: >>> ltr, freq = highest_freq(“frost.txt”) >>> print(ltr, freq) e 0.10952380952380952
