Create a directed graph that 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.

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

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 this chapter), and accompany such code with the related test function and some executions with varying values of input.

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 the body of the Python function def find_missing_combination(n1, n2, n3, combinations) that takes three positive integers and a list of tuples (each tuple containing three integers) as input. The function should find and return the missing combination from the possible combinations generated by the three integers. Each integer (n1, n2, n3) represents the range (from 0 to n inclusive) for each position in the tuple. For example, if n1 is 4, the first number in each tuple can be 0, 1, 2, 3, or 4.

Execution example:

print(find_missing_combination(4, 4, 4, [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (0, 1, 2)]))
# {(3, 0, 2), (4, 2, 2), (4, 4, 1), (3, 0, 3), (1, 4, 4), (2, 2, 4), (4, 4, 0), (3, 0, 4), (1, 4, 2), (0, 2, 1), (1, 4, 3), (0, 2, 0), (2, 0, 4), (1, 4, 0), (0, 2, 3), (1, 4, 1), (3, 1, 4), (0, 2, 2), (3, 2, 2), (4, 1, 4), (2, 0, 1), (3, 1, 3), (3, 2, 3), (1, 2, 0), (3, 1, 2), (0, 2, 4), (2, 0, 0), (3, 2, 0), (1, 2, 1), (4, 4, 2), (2, 0, 3), (3, 1, 1), (3, 2, 1), (1, 2, 2), (3, 1, 0), (2, 0, 2), (4, 1, 0), (1, 2, 3), (4, 1, 1), (1, 2, 4), (0, 4, 3), (3, 2, 4), (4, 1, 2), (0, 4, 2), (4, 1, 3), (0, 4, 1), (0, 4, 0), (3, 4, 4), (1, 3, 4), (2, 3, 4), (0, 1, 0), (1, 0, 2), (1, 3, 3), (4, 3, 4), (1, 0, 3), (0, 1, 1), (1, 3, 2), (1, 0, 0), (0, 4, 4), (1, 3, 1), (4, 3, 2), (1, 0, 1), (3, 4, 0), (0, 1, 3), (3, 3, 1), (4, 0, 3), (1, 3, 0), (3, 4, 1), (0, 1, 4), (2, 3, 0), (4, 3, 3), (4, 0, 2), (3, 3, 0), (2, 4, 1), (4, 3, 0), (3, 4, 2), (2, 3, 1), (2, 4, 0), (4, 0, 1), (3, 4, 3), (2, 3, 2), (4, 3, 1), (1, 0, 4), (4, 0, 0), (3, 3, 2), (2, 4, 3), (2, 3, 3), (2, 4, 2), (3, 3, 4), (0, 0, 4), (0, 3, 2), (2, 4, 4), (0, 0, 3), (0, 3, 3), (4, 0, 4), (0, 0, 2), (0, 3, 0), (2, 1, 4), (0, 0, 1), (0, 3, 1), (2, 1, 2), (4, 2, 4), (2, 2, 3), (2, 1, 3), (1, 1, 0), (0, 3, 4), (2, 1, 0), (2, 2, 1), (1, 1, 3), (2, 1, 1), (4, 2, 1), (1, 1, 2), (2, 2, 0), (3, 0, 0), (4, 2, 0), (4, 4, 3), (3, 0, 1), (4, 2, 3), (1, 1, 4)}

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

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

Implement the binary search algorithm in Python – 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 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 central item is less than item, the algorithm continues the search in the part of the list that follows the middle item. Instead, if the central item is greater than item, the algorithm continues the search in the part of the list preceding the central 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 [Fekete, Morr, 2018a], which is useful to understand the rationale of the binary search steps.

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 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 that is useful to understand the rationale of the partition steps.

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 containing Tim Berners Lee as the central node, linking it to five nodes representing his top-five co-authors. Also, specify the weight of each edge as an attribute, where the weight value is the number of bibliographic resources (articles, proceedings, etc.) Tim Berners-Lee has co-authored with the person linked by that edge.

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 handle more than one activity simultaneously. A tuple defines each activity. The first element specifies the starting time (a value from 0 to 24, indicating the starting hour). The second element represents the finish time (a value from 0 to 24, marking the ending hour). Develop the Python function def select_activities(set_of_activities) 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 a Python function def find_max_element(number_list) that uses a divide-and-conquer approach to find the maximum element in a list of numbers. The use of loops (like for or while) is prohibited.

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”.

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

Write the body of the Python function def reverse_and_count(string) that takes a string as input, reverses it, and counts the number of vowels it contains. It returns a tuple containing the reversed string and the count of vowels.

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

Using a dynamic programming approach, write an extension of the multiplication function introduced in the chapter "Recursion", i.e. def multiplication(int_1, int_2, solution_dict). This new function takes in input two integers to multiply and a dictionary with 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.

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

Write down two objects or situations that refer 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?

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

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

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

Create a function named filter_long_words(sentence, length) that takes a sentence and an integer as input, and returns a list of the words in the sentence that are longer than the given number.

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols and returns 1 if the sequence contains at least three consecutive 1s, and returns 0 otherwise. Implement the algorithm with a Turing machine, where the cell corresponding 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 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 set in the table.

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

What is the result of the execution of the algorithm in Figure 4 of the chapter "Algorithms" 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?

Write in Python the function def my_reversed(input_list), which behaves 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.

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 result of applying the second natural language definition of the Fibonacci function in Section "Natural languages vs programming languages" using “7” as input?

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

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

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.

Implement the divide and conquer quicksort algorithm in Python – i.e. the recursive def quicksort(input_list, start, end)​. First, it takes a list and the positions of the first and last elements 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 includes the pivot value since it has already been correctly positioned through the partition execution). In addition, define the base case of the algorithm appropriately to stop if needed before running 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 [Fekete, Morr, 2018c], which is helpful to understand the rationale of the binary search steps.

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 tree's nodes according to a breadth-first order. The breadth-first order considers all the nodes of the first level, then those of the second level, and so forth. For instance, considering the nodes created in Listing 2 in Chapter "Organising information: trees", 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.

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 def 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 done. 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.

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols and returns 1 if the sequence contains at least three 1s in any order, while it returns 0 otherwise. Implement the algorithm with a Turing machine, where the cell corresponding 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 def multiply_elements(number_list) using a divide-and-conquer approach to multiply all the elements in a list of numbers. The use of loops is prohibited.

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

Develop a function def combine_characters(string1, string2) that alternately combines the characters of two strings. If one string is longer, the remaining characters should be added to the end of the result.

combine_characters("abc", "1234")
# a1b2c34

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

Write in Python the function def my_range(stop_number), which behaves 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.