comp-think / 2020-2021 Goto Github PK

Suppose to organise some of the elements in the set returned by the second exercise in two different sets: set_hobbit that refers to the set set({"Frodo", "Sam", "Pippin", "Merry"}), and set_magician defined as set({"Saruman", "Gandalf"}). Create a dictionary containing two pairs: one that associates the set of hobbits with the key "hobbit", and the other that associates the set of magicians with the key "magician".

What is the boolean value of not (not True or False and True) or False?

Define a recursive function def exponentiation(base_number, exponent) for implementing the exponentiation operation. Test (by implementing the related test case) it on the following inputs: 3⁴, 17¹, and 2⁰.

We define a labyrinth as a set of tuples representing the various cells of the paths within the labyrinth. The tuples are organised in an x/y grid, similar to the way used in Listing 1 for the peg solitaire, such as the one proposed as follows:

      (1,0)       (3,0) (4,0) (5,0)
(0,1) (1,1) (2,1) (3,1)       (5,1)
(0,2)       (2,2)       (4,2) (5,2)
(0,3)       (2,3) (3,3)       (5,3)
(0,4)                   (4,4)      
(0,5) (1,5) (2,5) (3,5) (4,5)      

Write the function solve_labyrinth(paths, entrance, exit, last_move), which takes as input the paths of the labyrinth (such as the ones mentioned above), two tuples representing the entrance and the exit of the labyrinth, and the last move did. The function returns the last move done to reach the exit if the labyrinth has an escape; otherwise, it returns None. Accompany the implementation of the function with the appropriate test cases.

What is the result of the execution of the algorithm in Figure 4 using "Peroni", "HTML", and "Peroni, S., Osborne, F., Di Iorio, A., Nuzzolese, A. G., Poggi, F., Vitali, F., Motta, E. (2017). Research Articles in Simplified HTML: a Web-first format for HTML-based scholarly articles. PeerJ Computer Science 3: e132. e2513. DOI: https://doi.org/10.7717/peerj-cs.132" as input values?

Suppose one has to address the maximum number of activities in a day choosing them from a set of available activities, considering that one cannot address more than one activity simultaneously. Each activity is defined by a tuple, where the first element defines the starting time (a value from 0 to 24, indicating the starting hour) while the second element defines the finish time (a value from 0 to 24, indicating the finish hour). Develop the Python function def select_activities(set_of_activities) by using a greedy approach. It takes in input a set of activities of a day and returns the list of the maximum number of non-overlapping activities one can address, ordered according to the starting time. Hint: think about the finish time of each activity and see how it may affect the selection. Accompany the implementation of the function with the appropriate test cases.

Write the table of instructions of a Turing machine with four states – A (initial state), B, C, and D (final state) – such that, once reached the final state, only the cells immediately on the left and on the right of the initial position of the head of the machine will have the value 1 specified. The final state must not have any instruction specified in the table.

Write a sequence of instructions in Python to create a list with the following elements ordered alphabetically: "​Harry"​, "​Draco"​, "​Hermione"​, ​"​Ron"​, "​Severus"​.

Write in Python the function def my_enumerate(input_list) which behaves like the built-in function enumerate() introduced in Section "Linear search" and returns a proper list, and accompany the function with the related test case. It is not possible to use the built-in function enumerate() in the implementation.

Write in Python the pure iterative version of the function defined in the previous exercise.

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols, and returns a 1 if the sequence contains at least three 1s in any order, and returns a 0 otherwise. Implement the algorithm with a Turing machine, where the cell correspondent to the starting position of the head is where the final result must be stored. Also, the five cells following the starting position of the head are initialised with the 0-1 sequence of five symbols used as input of the algorithm.

Write a code in Python to create a set of the following elements: "​Bilbo", "​Frodo", "​Sam", "​Pippin", "​Merry".

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols, and returns a 1 if the sequence contains at least three consecutive 1s, and returns a 0 otherwise. Implement the algorithm with a Turing machine, where the cell correspondent to the starting position of the head is where the final result must be stored. Also, the five cells following the starting position of the head are initialised with the 0-1 sequence of five symbols used as input of the algorithm.

Implement in Python the binary search algorithm – i.e. the recursive function def binary_search(item, ordered_list, start, end). It takes an item to search (i.e. item), an ordered list and a starting and ending positions in the list as input. It returns the position of item in the list if it is in it, and None otherwise. The binary search first checks if the middle item of the list between start and end (included) is equal to item, and returns its position in this case. Otherwise, if the middle item is less than item, the algorithm continues the search in the part of the list that follows the middle item. Instead, in case the middle item is greater than item, the algorithm continues the search in the part of the list that precedes the middle item. Accompany the implementation of the function with the appropriate test cases. As supporting material, Fekete and Morr released a nonverbal definition of the algorithm which is useful to understand the rationale of the binary search steps.

What are all the possible sentences that one can produce by using the regular grammar introduced in Section “Historic hero: Noam Chomsky”?

What is the result of applying the second natural language definition of the Fibonacci function in Section "Natural languages vs programming languages" using “7” as input?

Consider the set created in the first exercise, stored in the variable my_set. Describe the status of ​my_set after the execution of each of the following operations: ​my_set.remove("Bilbo"), ​my_set.add("Galadriel"), ​my_set.update(set({"Saruman", "Frodo", "Gandalf"})).

Create a test case for the algorithm introduced in Listing 2.

Choose any recursive algorithm introduced in the previous chapters and provide a new implementation of it in Python following the dynamic programming approach.

Implement in Python the partition algorithm – i.e. the non-recursive function def partition(input_list, start, end, pivot_position). It takes a list and the positions of the first and last elements in the list to consider as inputs. It redistributes all the elements of a list having position included between ​start and ​end on the right of the pivot value input_list[pivot_position] if they are greater than it, and on its left otherwise – note: pivot_position must be a value between start and end (included). Also, the algorithm returns the new position where the pivot value is now stored. For instance, considering ​​my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]), the execution of partition(my_list, 1, 4, 1) changes ​my_list as follows: ​list(["The Graveyard Book", "American Gods", "Coraline", "Neverwhere", "Good Omens"]) and 2 will be returned (i.e. the new position of "Coraline"). Note that "The Graveyard Book" has not changed its position in the previous execution since it was not included between the specified start and end positions (i.e. 1 and 4 respectively). Accompany the implementation of the function with the appropriate test cases. As supporting material, Ang recorded a video which is useful to understand the rationale of the partition steps.

Define a recursive function def fib(n) that implements the algorithm to find the n^th Fibonacci number. In particular, if n is less than or equal to 0, then 0 is returned as a result. Otherwise, if n is equal to 1, then 1 is returned. Otherwise, return the sum of the same function called with n-1 and n-2 as input. Please accompany the function with the related test case.

What is the boolean value of "spam" not in "spa span sparql" and not ("egg" > "span")?

Write down the execution steps of linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman"), as explained in Listing 7.

Write an extension of the multiplication function introduced in the chapter "Recursion", i.e. def multiplication(int_1, int_2, solution_dict), by using a dynamic programming approach. This new function takes in input two integers to multiply and a dictionary with solutions of multiplications between numbers. The function returns the result of the multiplication and, at the same time, modifies the solution dictionary adding additional solutions when found. Accompany the implementation of the function with the appropriate test cases.

Write down two objects or situations that are referring to the same pattern if analysed from an abstract point of view, as introduced in Section "Abstraction is the key". What features do they have in common?

Consider to have a queue obtained by processing, one by one, the elements included in the list of the first exercise, i.e. my_queue = deque(["Draco", "Harry", "Hermione", "Ron", "Severus"]). Describe the status of my_queue after the execution of each of the following operations: my_queue.popleft(), my_queue.append("Voldemort"), my_queue.popleft().

Implement the algorithm introduced in Section "Greedy algorithms" for returning the minimum amount of coins for a change. Accompany the implementation of the function with the appropriate test cases.

Write in Python the function def my_reversed(input_list) which behave like the built-in function reversed() introduced in Section "Insertion sort" and returns a proper list, and accompany the function with the related test case. It is not possible to use the built-in function reversed() in the implementation.

The previous lecture notes, entitled “Introduction to Computational Thinking”, illustrate two different algorithms, expressed in natural language, for implementing the Fibonacci function. Create two distinct flowcharts to implement both of them.

Consider to have a stack obtained by processing, one by one, the elements included in the list of the first exercise, i.e. my_stack = deque(["Draco", "Harry", "Hermione", "Ron", "Severus"]). Describe the status of my_stack after the execution of each of the following operations: my_stack.pop(), my_stack.pop(), my_stack.append("Voldemort").

Consider the list of co-authors of Tim Berners-Lee as illustrated in the right box at http://dblp.uni-trier.de/pers/hd/b/Berners=Lee:Tim. Build an undirected graph that contains Tim Berners Lee as the central node, and that links to five nodes representing his top-five co-authors. Also, specify the weight of each edge as an attribute, where the value of the weight is the number of bibliographic resources (articles, proceedings, etc.) Tim Berners-Lee has co-authored with the person linked by that edge.

Write the flowchart of an algorithm that takes in input two objects and returns the string "yes" whether the two objects are the same; otherwise, it returns the string "no".

Implement the function below in Python, that takes in input the colour of the player who has to play the turn (parameter colour), the sets of coordinates (i.e. sets of tuples) of all the black stones (parameter black) and white stones (parameter white) already positioned on the board, and returns the x, y coordinate (a tuple) of a free intersection where to place a new colour stone. The coordinates of the various positions of the board are those ones defined in "the board" as in the AlphaGo material available online.

def place_stone(colour, black, white):
    # study the board and calculate the
    # best place where to position the stone
    return x, y # the coordinates of the new stone

Additional information is available at https://doi.org/10.5281/zenodo.2204836.

Write in Python a recursive function def breadth_first_visit(root_node). This function takes the root node of a tree and returns a list containing all the nodes of the tree according to a breadth-first order. The breadth-first order considers all the nodes of the first level, then those ones of the second level, and so forth. For instance, considering the nodes created in Listing 2, the function called on the node book should return the following list: [book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]. Accompany the implementation of the function with the appropriate test cases.

Implement in Python the divide and conquer quicksort algorithm – i.e. the recursive def quicksort(input_list, start, end)​. It takes a list and the positions of the first and last elements in the list to consider as inputs. Then, it calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices. Finally, it executes itself recursively on the two partitions (neither of which includes the pivot value since it has been already correctly positioned through the execution of partition). In addition, define the base case of the algorithm appropriately to stop if needed before to run the partition algorithm. Accompany the implementation of the function with the appropriate test cases. As supporting material, Fekete and Morr released a nonverbal definition of the algorithm which is useful to understand the rationale of the binary search steps.

Propose some variation to the implementation of the peg solitaire exercise in order to make it more efficient – in particular, avoiding unsuccessful configurations if they have been already encountered previously while looking for a solution.

Write in Python the function def my_range(stop_number) which behave like the built-in function range() introduced in Section "Insertion sort" and returns a proper list, and accompany the function with the related test case. It is not possible to use the built-in function range() in the implementation.

Following the template in Listing 11, write in Python the algorithm proposed originally in Figure 4 of the chapter entitled "Algorithms" as a flowchart (which uses a different approach compared to the one discussed in the chapter about programming languages), and accompany such code with the related test function and some executions with varying values of input.

Create a directed graph which relates the actors Brad Pitt, Eva Green, George Clooney, Catherine Zeta-Jones, Johnny Depp, and Helena Bonham Carter to the following movies: Ocean's Twelve, Fight Club, Dark Shadows.