solutions1_2021

pdf

School

University of Waterloo *

*We aren’t endorsed by this school

Course

MISC

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by Dakshdult

CS 234 Fall 2021 Naomi Nishimura Assignment 1 Solutions WARNING: To receive credit for this assign- ment, you checked “I agree” to the academic integrity declaration. Please keep all the rules in mind as you complete your work. Coverage: Through Module 2 This assignment consists of a written component and a programming component. Please read the instructions on the reference page for assignments carefully to ensure that you submit each component correctly. Several of the questions will make use of the ADT Strange. This strange ADT behaves like a strange type of string: it is missing some of the functionality of a string, but has other functionality, such as being mutable. < , [ Name [ Preconditions [ Produces [ Effects | CREATE Starter is a string a new strange creates a strange (Starter) co;;}r}ir}léthe \(‘\hara, ers in Starter LENGTH (S) S'is a strange N “the length of § Look_Up S is a nonempty strange, character in (S, Pos) Pos is a non: cgat?\% " | position Pos integer less tgs\g thc} ngth of § . UPDATE S is a nonempty strange, updates character (S, Pos, Char) Pos is a nonnegative integer less than the length of S, Char is a string of length 1 in position Pos to Char ADpD(S, Char) S is a strange, Char is a string of length 1 adds Char to the back of § CROP_FRONT S is a nonempty strange, deletes from § integer less than the length of § (S, Pos) Pos is a nonnegative characters in integer less than the length positions 0 through of § Pos, inclusive CRrROP_BACK S is a nonempty strange, deletes from S (S, Pos) Pos is a nonnegative characters in positions Pos to the end of S, inclusive JOIN(S, Other) S is a strange, Other is a strange adds Other to the end of § This document is for the exclusive use of ddult.

CS 234: Assignment 1 Solutions 2 Note: The first character of S is in position 0 and the last in position LENGTH(S) - 1. The purpose of the assignment is for you to demonstrate your understanding of the role of the user of an ADT. To do so, and to receive full marks for your work, be sure to do the following: e Do not use strings other than as inputs to the operations that consume strings. e In programming questions, you have been provided repr to assist you in tests. Do not use repr in any other way. In particular, do not extract the contents of a Strange and then manipulate the data using string operations, functions, or methods. Written component For full marks, you are expected to provide a brief justification of any answer you provide. For asymptotic notation, informal arguments are sufficient (that is, using formal definitions is not required). WL. [4 marks] Determine the postconditions of the pse@ocode function MYSTERY. That is, if the function produces output, state what the 16putds and refer to specific line numbers to explain how the function produces what it produces.\If the function results in any side effects, state what the side effects are and refer to specific’line numbers to explain how the function achieves those side effects. You can assume that the COPY operation l'Odllf a new copy of a Strange (like the function copy.deepcopy in Python). s The lines have been numbered. for MYSTERY(S) / INPUT: A Strange S | OUTPUT: For you to find out / EFFECTS: For you to find out 1 Length «+ LENGTH(S) 2 if Length > 0 T+ Copy(S) CROP_BACK(S, 1) for Pos from 1 to Length - 1 if Pos % 2 == 0 Char < Look_UP(T, Pos) ADD(S, Char) %N D LA o Solution: The function mutates S by removing all but the data items in the even positions. It achieves the mutation by making a copy of S in Line 3, removing all but the first character of S (that is, the character in position 0) in Line 4, and then looping through all the remaining characters (Lines 5-8), checking to make sure the position is even (Line 6), and if so finding the character in the copy (Line 7) and adding it to S (Line 8). The function does not produce any output. This document is for the exclusive use of ddult.

CS 234: Assignment 1 Solutions 3 W2. [11 marks] In the subquestions below, n is the total number of characters in a strange S (the length) and the cost of copying a strange of length n is in ©(n). ) [9 marks] Using L, C, U, and A as the worst-case costs of the operations LENGTH, CRrOP_BACK, LOOK_UP, and ADD, respectively, express the worst-case cost of Mys- TERY in asymptotic notation (using ©) as a function of L, C, U, A, and n. Be sure to account for each line in the function. Do not make any assumptions about the relative values of L, C, U, A, and n. Solution: The total cost is the cost of the blocks consisting of Line 1 and Lines 2-8. Line 1 consists of an assignment, which has a constant cost, and the use of LENGTH at cost L. Thus, the total cost of the block is in ©(L). Lines 2-8 consist of branching. Since there is only a single branch, we determine the cost of assessing the condition in Line 2 and then the cost of Lines 3-8. Line 2 consists of a comparison and the management of branching, both of which are constant-time steps. The total cost for a cogtant number of constant-time steps is in ©(1). Lines 3-8 can be broken into blocks of Lines3 and Lines 5-8. Line 3 consists of an assignment, accessing the variable S, and the use of Copy. The cost is dominated by the cost of CopPY as the only non-constant-time step; the cost is linear in the size of S, or ©(n). The cost of Line 4 is dominated by the cost of CROP_BACK, or ©(C). Thus, the t cost of the block is ©(n+ C). Since Lines 5-8 form a loop, we first d ter ine the cost of the body of the loop in Lines 6-8. Line 6 consists of constant-time steps: a mathematical operation, checking for equality, and managing branching. The cost of Line 7 is dominated by U, the cost of L({K, , and the cost of Line 8 is dominated by A, the cost of ADD. In total, the lines have cost in O(U + A). Since we have a for loop, and)since Line 5 is not using any expensive function, the cost of iteration management is constant. The number of iterations is in ©(n), the size of Length. Because the condition in Line 6 is true about half the time, the number of iterations in which Lines 7 and 8 are executed is linear in n, and hence total cost of Lines 5-8 is in ©(n(U + A)). The total for Lines 3-8 is the sum of ©(n+ C) for Lines 3-4 and O(n(U + A)) for Lines 5-8, for a total in ©(C + n(U + A)), since n is dominated by n(U + A). The total for Lines 2-8 is thus ©(C'+n(U + A)), as the cost of Line 2 is dominated by the cost of Lines 3-8. Finally, since we do not know the relative values of ©(L) (the cost of Line 1) and the total for Lines 2-8 (©(C' + n(U + A))), we write the total cost as O(L + C + n(U + A)). (Note: We could have used max instead of summing terms, such as ©(max{L,C,n(U+ AN} b) [2 marks] Give the best-case running time of MYSTERY as a function of L, C, U, A, and n, assuming that the best-case costs of the operations are the same as the worst-case costs. As in part (a), do not make any assumptions about the relative values of the variables. Briefly justify your answer. Solution: There is no difference between the best case and the worst case, since This document is for the exclusive use of ddult.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS 234: Assignment 1 Solutions 4 W3. W4, the algorithm does not depend on the details of the input, only its length. [6 marks] Using the pseudocode interface for the ADT Strange given above, write a pseu- docode function REVERSE that consumes a Strange Strange-One and produces a new Strange with all the characters in Strange_One in reverse order. For example, if Strangest contains the characters in bad, the function call REVERSE(Strangest), will produce a Strange containing the characters in dab. Your function must not have side effects; e.g. Strange_One should not be mutated. Solution: REVERSE (Strange_One) INPUT: A Strange Strange_One OUTPUT: A Strange with characters in the reverse order of Strange_One 1 New < CREATE("") 2 Length < LENGTH(Strange_One) 3 for Pos from 0 to Length - 1 N 4 Location < Length - Pos - 1 P \ 5 Char < Look_Up(Strange_One, Location) 6 App(New, Char) D 7 return New \ [4 marks| - b ) Suppose that the provider has provided four-different options for the ADT Strange. The chart below gives the worst-case costs of spiée of the operations using each of the options. Here you should assume thz{n is the size of the Strange that is the input to the function you are describing. | Name ” Option A | Option B l Option C [ Option D | CROP_FRONT(S, Pos) || ©(1) o(1) O(n) o(1) CROP_BACK(S, Pos) | ©(n?%) O(n) O(n) o(1) JOIN(S, Other) o(1) O(n) o(1) O(n?) Each subquestion gives characteristics of an algorithm that uses the ADT Strange. (a) [2 marks] The algorithm uses CROP_FRONT n times, CROP_BACK one time, and JOIN n times. Which option has the worst worst-case running time? Briefly justify your answer by giving its worst-case running time in order notation. Solution: The n JOIN operations results in ©(n®) cost for Option D. None of the other options have more than n uses of an operation with a cost of more than ©(n). (b) /2 marks] The algorithm uses CROP_FRONT n times, CROP_BACK one time, and JOIN one time. Which option has the best worst-case running time? Briefly justify your answer by giving its worst-case running time in order notation. This document is for the exclusive use of ddult.

CS 234: Assignment 1 Solutions 5 Solution: Option B is the best option, as the total cost for each operation is in ©(n). Option A and D each have an operation with quadratic cost, and for Option C there are n uses of an operation with cost in ©(n). Programming component Please read the information on assignments and Python carefully to ensure that you are using the correct version of Python and the correct style. For full marks, you are required not only to have a correct solution, but also to adhere to the requirements of the assignment question and the style guide, including aspects of the design recipe. Although submitting tests is not required, it is highly recommended that you test your code. For each assignment question, create a testing file that imports your submission and tests the code. Do not submit your testing file. Several of the programming questions for this assignment use the ADT Strange, which has been implemented for you in the provided module strange.py. You have been provided with the method repr that you can use for testing. Do not use it in any other way: in particular, do not use it to extract the data and then manipulate it as a‘string. Unless stated otherwise, an ADT Strange can contain zero characters. For full marks, use strings only as inputs to th opér>ations that require them. Any other use of strings is not allowed and will'result in loss of marks. Your code should work with the followi: c&)e\interf e: ## Strange(starter) produces a /strange fro{starter. ## __init__: Str -> Strang Q def __init__(self, starter): ## repr(self) produces a string from self. ## __repr__: Strange -> Str def __repr__(self): ## self.length() produces the length of self. ## length: Strange -> Int def length(self): ## self.look_up(pos) produces the character in position pos. ## look_up: Strange Int -> Str ## Requires: self has length > 0 ## 0 <= pos < length of self def look_up(self, pos): ## self .update(pos, char) updates the character in position pos ## with char. ## Effects: Mutates self by updating the character in position pos ## with char. ## update: Strange Int Str -> None This document is for the exclusive use of ddult.

CS 234: Assignment 1 Solutions 6 ## Requires: self has length > 0 ## 0 <= pos < length of self ## char is a string of length 1 def update(self, pos, char): ## self.add(char) adds char to the end of self. ## Effects: Mutates self by adding char to the end of self. ## add: Strange Str -> None ## Requires: char is a string of length 1 def add(self, char): ## self.crop_front(pos) removes characters in positions O ## through pos from self. ## Effects: Mutates self by removing characters in positions 0 ## through pos. ## crop_front: Strange Int -> None N ## Requires: length of self > 0 p ## 0 <= pos < length of self D def crop_front(self, pos): ## self.crop_back(pos) removes ara\\ters in positions pos H## to length of self - 1 from self .. ## Effects: Mutates self by removing characters in positions pos ## to length of self - fQ ## crop_back: Strange Int —-> ## Requires: length of s{::. >0 it 0 <= pos < 1 kgth/Bf self def crop_back(self, pos): - ## self.join(other) adds other to the end of self. ## Effects: Mutates self by adding other to the end of self. ## join: Strange Strange -> None def join(self, other): For example, if you wish to create a new strange my_strange containing the word word, use my_strange = Strange("word") and if you wish to change d to k, use my_strange.update(3, "k") to change the strange to contain the characters work. To remove the letters in positions 0 through 1, use my_strange.crop_front (1) This document is for the exclusive use of ddult.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS 234: Assignment 1 Solutions 7 to obtain the strange containing the characteres rk. Each of your solutions to the programming questions should include the line from strange import *. For full marks, you must not directly manipulate any of the fields in the implementation of a Strange; use only the provided methods for access. For any of the programming questions in this assignment, you may import any of the fol- lowing files: check.py and strange.py. You can find check.py linked off of the section on the Style Guide in Reference material > Python > Python requirements on Open edX, and you can find strange.py linked off the page Assessments > Assignments > Assignment 1. You may also use the built-in Python module copy. For the function word_cost, you may also use multiset.py, pair.py, and linked.py, as linked off the page for Assignment 1. Be sure to read the instructions on the Python requirements page to ensure that you have imported the files as required. P1. [6 marks] Write a function shuffle that consumes two ADT Stranges one and two of the same length and produces an ADT Strange with the characters in one and two ap- pearing in alternating positions, starting with one./For example, if strange_one con- tains the characters in bird and strange two contains the characters in BIRD, then shuffle(strange one, strange two) will produce a Strange containing the characters in bBiIrRdD. \ Make sure that your function produc arN&iT Strange. Submit your work in a file with theg;amc hufflée.py. P2. [7 marks] Write a function £11 consyres an ADT Strange mutates it so that the front and back halves are flipped: The splitting point is defined so that if the length is odd, the front “half” is <galler; strings of length less than two are unchanged. For example, if examplel is an ADT Sté/ange that contains the characters in the word hello, after executing flip (examplel), the characters will be in the order 11lohe. Similarly for example2 containing the characters in basket and example3 containing the characters in baskets, after executing f1ip(example2) and flip(example3), the characters will be in the orders ketbas and ketsbas. Make sure that your function mutates the input. It should not produce a new Strange; it should change the input. Submit your work in a file with the name f1ip.py. P3. [12 marks] You have a business that makes signs out of wooden letters, and wish to have a function that produces the cost of a sign. There are two different costs for letters, depending on whether a letter is part of your inventory or if you have to make a special order for it. You store your inventory as an ADT Multiset and the name on the sign as an ADT Strange. Write a function word_cost that consumes a multiset inventory, a strange name, and integers inventory_cost and outsource_cost. Your function will produce the total cost of making the sign. For example, if M is a multiset containing two copies of A, one copy of R, two copies of V, and three copies of X and S is a strange containing the letters in the This document is for the exclusive use of ddult.

CS 234: Assignment 1 Solutions 8 name AARDVARKS, then word_cost(M, S, 1, 2) will produce 14 resulting from paying $1 for two of the A’s, one of the R’s, and the V, and $2 each for the D, one of the A’s, one of the R’s, the K, and the S, since 4 x 1 +5 x 2 = 14. Note: To compute the cost, you should assume that if a letter is in the inventory, you will use that letter instead of ordering a new one, even if the cost of a new one is cheaper. Remember that you are the user of both the ADT Multiset and the ADT Strange in this question. The code interface for the ADT Multiset is supplied; no other details are relevant for your work. Note: For multiset.py to function, you need to download linked.py into the same folder. You can find linked.py available to download from the page Reference material > Python > Modules on Open edX. Submit your work in a file with the name wordcost.py. class Multiset: N ## Multiset () produces a newly const: uz.‘tg%mpty multiset. ## __init__: -> Multiset > def __init__(self): . ## value in self produces Tr is an item in self. ## __contains__: Multiset Any def __contains__(self, value): ## self.add(value) iﬂ\ds value to self. ## Effects: Mutates 'self by’ adding value to self. ## add: Multiset Any —> Nz}rlle def add(self, value): ## self.delete(value) removes an item with value from self. ## Effects: Mutates self by removing an item with value from self. ## delete: Multiset Any -> None ## Requires: self contains an item with value value def delete(self, value): This document is for the exclusive use of ddult.

solutions1_2021

Related Documents