7WCM1078 Computational Algorithms and Paradigms

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.

Attachment:- Def Assignment.rar