Develop the divide and conquer algorithm def quicksort(input_list, start, end)​ that takes a list and the positions of the first and last elements in the list to consider as inputs, and that calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices, and then applies itself recursively on the two partitions (neither of which includes the pivot value since it has been already correctly positioned by means of the execution of partition). In addition, define appropriately the base case of the algorithm so as to stop if needed before to run the partition algorithm.

Accompany the implementation of the function with the appropriate test cases.

Write in Python a recursive function def breadth_first_visit(root_node) that takes the root node of a tree and returns a list containing all the nodes of the tree according to a breadth first order, which first consider 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.

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

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.

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

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

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").

Hi all, I have a question about an exercise in one of last year test.
We have to make the idf using only the document "d" (and in consequence of this fact we have to do the tf only on d) or we have to do the idf using all documents that contain a term?

Implement the informal algorithm introduced in Section "Greedy algorithms" for returning the minimum amount of coins for a change.

See: https://doi.org/10.5281/zenodo.2204836

Write an extension of the multiplication function introduced in the lecture "Recursion", i.e. def multiplication(int_1, int_2, solution_dict), by using a dynamic programming approach. This new function takes in input two integer numbers to multiply and a dictionary with solutions of multiplications between numbers, which can be used to retrieve directly the result of such multiplication if already present in it. 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.

Define a recursive function def fib(n) that implements the algorithm to find the n^th Fibonacci number – where if n is less than or equal to 0, then 0 is returned as result; 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 not (not True or False and True) or False?

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

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 so as to implement both of them.

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"})).

Write in Python the function def my_enumerate(input_list) which behave 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 a pseudocode in Python so as to create a set of the following elements: "​Bilbo"​, "​Frodo"​, "​Sam"​, "​Pippin"​, "​Merry"​.

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

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().

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.

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

Consider the list of co-authors of Tim Berners-Lee as illustrated in the write 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 is linked to other five nodes representing his top-five co-authors. In addition, 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.

Following the template in Listing 11, write in Python the algorithm proposed originally in Figure 4 of the lecture notes entitled "Algorithms" as a flowchart, and accompany such code with the related test function and some executions with different input values.

What are all the possible sentences that can be produced by using the regular grammar introduced in Section "Historic hero: Noam Chomsky"?

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.

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.

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

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?

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

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 in Python the pure iterative version of the function defined in the previous exercise.

Suppose that all the elements in the set returned by the second exercise have been organised in two different sets, i.e. 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 associate the set of hobbits with the key "hobbit", and the other that associates the set of magicians with the key "magician".

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.

Implement in Python the partition algorithm – i.e. def partition(input_list, start, end, pivot_position) – that takes a list and the positions of the first and last elements in the list to consider as inputs, and 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. In addition, the new position where the pivot value is now stored will be returned by the algorithm. 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.

Write an algorithm for using the merge sort (introduced in the previous lecture) so as to use a dynamic programming approach in case the same list of books must be ordered twice or more times during the algorithm execution – see the informal example introduced in Section "Remembering solutions to sub-problems" of this lecture notes.

Accompany the implementation of the function with the appropriate test cases.