7WCM1078 Computational Algorithms and Paradigms

Assessment 1:

Question 1

‘Connect 4' is a game for two players. It consists of a 6x7 vertical grid into which a red or a yellow disc is placed by each player in turn. Each of the players take turns to place their coloured disc into the grid. The object of the game is to be the first to obtain a (winning) straight line consisting of their set of symbols, these being either 4 red discs or 4 yellow discs.

Using each stage of the HTTLAP procedure (or Polyas approach)

a) Establish the number of winning lines when playing Connect 4 on a 6 x 7 board. Include each of the stages from HTTLAP (or Polya) in your solution.

b) Extend your solution to describe the numberof winning lines when playing Connect 4 on an m x n grid, where m and n are positive whole numbers. Again, include each of the stages from HTTLAP (or Polya) in your solution.

c) How would your algorithm change for Connect P, in which a winning line is p units long?

d) Explore the game of Connect P played on a three-dimensional k x l x m grid, given that a winning (straight) line is P units long consisting of either red discs or yellow discs.

Include at least one imperative solution to the problem, either using control structures or using formulae.

e) Describe how your algorithm would change if your solution was developed in a different paradigm to the above. Would recursion work here? Justify.

Question 2

The Random Access Machine (RAM) is a hypothetical computer used as a model to estimate the run time of an algorithm. During our discussions on RAM we met the concepts of worst case, best case and average case complexity. Relating to these we met the O, Ω, and Θ notations.

a) Explain what is meant by a Random Access Machine and what is meant by the O, Ω, and Θ notations. Include diagrams where appropriate.

b) Given that f(n) = 5n⁹ - 100 n³ + 27 show that f(n) = Ο(n¹¹). Use the O definition for O(n¹¹).

c) Draw flowcharts for the following control structures:

i. a for loop followed by an if control structure
ii. a while loop containing a nested for loop with an internal nested do-while loop
Calculate McCabes Cyclotomic complexity metric for each of the code segments described.

d) The quantum paradigm is a relatively recent paradigm enabling developers to create analogues of classical based algorithms and to solve previously intractable problems using quantum based algorithms.

a. using a search engine of your own choosing find one example for a quantum based analogue of a classical algorithm and one example of a quantum based algorithm used to solve a previously intractable problem.

b. Compare the quantum paradigm to one of the following:
i. object orientated paradigm
ii. logic paradigm
iii. functional paradigm

e) Using an example of your own describe how either:

i. Haskell could be used to accomplish a task involving functional composition
or
ii. Lisp could be used to accomplish a task involving recursion.

Assessment 2:

Question 1

Various procedures may be followed in order to solve a problem. Two such procedures are the HTTLAP procedure and Polya's procedure.

a) Compare and contrast Polya's procedure for solving problems, with another procedure (of your own choosing), that has also been developed for solving problems. Include an explanation for each part of the Polya procedure.

The Tower of Hanoi is a game for two players. It consists of ‘n' discs of various size located on one of ‘p' posts. Each disc is of different size to each of the other discs and are initially arranged on a post with the largest disc on the bottom of the stack, with smaller discs only allowed to rest on a disc of larger size.

In this question I would like you to consider the Tower of Hanoi problem with p = 4.

b) Using the HTTLAP procedure or otherwise derive appropriate procedural algorithms, (using, if possible, an appropriate formula, or 'not using a formula') for the tower of Hanoi problem with 4 posts. Provide a final completed solution in pseudo-code.

c) Compare and contrast the approach taken above with the tower of Hanoi problem to one that would be generated in another paradigm of your own choosing. Would recursion be possible here?

Question 2

The Functional paradigm was introduced in the 1960's to address a range of different types of problem from a range of different disciplines. Two such disciplines were symbolic computation and natural language processing. Initial functional programming languages such as LISP have been described as examples of impure rather than pure functional languages.

a) Compare and contrast the pure functional paradigm to two of the following:
i. object oriented paradigm
ii. logic paradigm
iii. quantum paradigm

Following your initial observations on the two paradigms extend your discussion to include

iv. Source, domain, range and codomain. Include an explanation of the different types of relation that exist between such sets with examples for each type of relation
v. the representation of states in classical and quantum paradigms

b) Using an example of your own describe how Lisp or Haskell could be used to accomplish a task involving
i. functional composition, and
ii. recursion.

c) The Linear Search Algorithm and the Binary Search Algorithm are two examples of algorithms that can be used to find a particular value within a finite collection of numeric data. Explain what is meant by a linear search algorithm and a binary search algorithm. Establish the worst case complexity for each of these algorithms. Justify your answers.

d) Calculate McCabes cyclotomic complexity metric for the following code segments:

i. a for loop followed by a do-while loop
ii. a do-while loop containing a nested if control structure

Include appropriate flowcharts for each code segment.

Attachment:- Computational Algorithms and Paradigms.rar