The Algorithm Developer badge demonstrates that an earner is able to select appropriate algorithms for solving a range of problems, that they show ability to design and implement data structures for novel problems, as well as reason about the complexity and efficiency of algorithms. Please submit the evidence (source code files) as text files and make sure that the code is commented.

Issuer: | Coventry University |
---|

**Task 1**Algorithms, Strings and RecursionA) Write a program to predict the number of creatures in a fictional alien invasion. An alien lays X eggs each day (there are no genders in this species) and the eggs hatch after Y days. If X is 3 and Y is 5, how many aliens will there be 30 days after a single alien invades?

B) Given two strings of n and m integer elements, write the pseudocode to compute:

(a) The string that contains all the elements belonging to both strings.

(b) The string of all the elements of the two given strings, written once.

(c) The string of the elements from the first string, without the elements that are also in the second string.

What's the run time?

C) Write the pseudocode for a recursive program to generate the Cartesian product (product set, direct product, cross product) of n sets.

D) Consider having n cubes, each being characterized by their edge length and their colour. Use the cubes (not necessarily all of them) in order to build a tower of maximum height, under the following conditions:

(a) any two neighbouring cubes must be of different colours.

(b) the edge length of a cube is lower than the edge length of the cube placed below it.**Task 2**Algorithms and Big O NotationA) Write a function that takes four parameters representing the constant and multiplier of two linearly growing (as in O(m × n + k) ) functions and determines the critical value of n (which should be an integer) at which the relative run-time of the two algorithms switches. That is, at which input size is algorithm A slower than B and at which is B slower than A? Use an iterative approach rather than solving the equations.

B) Let's consider a labyrinth as a n × m matrix, where the corridors are denoted by 1s situated in consecutive positions on the same line or column. The rest of the elements are 0. Within the labyrinth, a person is considered to be in position (i, j). Write a program that lists all exit routes which do not pass the same place twice.

Input: n, m, the rows of the matrix, the coordinates of the exit and the coordinates of the person (row, column). Output: a sequence of row/column pairs representing the person's successive position.**Task 3**Sorting and PointersA) Adapt the quick sort algorithm to find the mth smallest element out of a sequence of n integers.

B) Write a function to calculate the kth power of a square matrix, using pointers to access to the elements of the matrix. The resulted matrix will be displayed in natural form.**Task 4**Lists and TreesA) Using the model of a circular single-linked list, implement the following scenario:

N children stand in a circle; one of the children starts counting the others clockwise. Every Nth child leaves the game. The winner is the one who remains.

Notes: Read the number of children, the childrens' names and the one starting to count from the standard input. Input: 4; Diana, Michael, David, Mary; Start: Diana; Winner: Michael.

B) Build a Binary Search Tree (BST) to hold English language words in its nodes. Use a paragraph of any text in order to extract words and to determine their frequencies.

Input: You should read the words and frequencies from a file in a suitable format, such as .csv. The following tree operations should be implemented:

(a) Listing (word, frequency) pairs for each of the tree nodes.

(b) Printing the tree in preorder.

(c) Finding a word.

Regardless whether found or not found your program should output the path traversed in determining the answer, followed by yes if found or no, respectively.**Task 5**GraphsA) Implement the structure for an unweighted, undirected graph G, where nodes consist of positive integers. Also, implement a function isPath(v, w), where v and w are vertices in the graph, to check if there is a path between the two nodes. The path found will be printed to a text file as a sequence of integer numbers (the node values).

B) Using the graph structure previously implemented, implement a function is Connected(G) to check whether or not the graph is strongly connected. The output should be simply 'yes' or 'no'.

C) Consider the structure of a directed weighed graph. Implement an algorithm to find its maximum cost spanning tree. The output should be the preorder and inorder traversal of the tree. Describe the running time of this algorithm.