Algorithms and Data Structures Assignment
1. The Chess Game
"Chess provides a setting for many fascinating diversions which are quite independent of the game itself. Many of these are based on the strange "L-shaped" move of the knight. A classic example is the problem of the knight's tour, which has captured the attention of mathematicians and puzzle enthusiasts since the beginning of the eighteenth century."- "Fundamentals of Data Structures", E Horowitz & S Sahni.
The problem is to move the knight, beginning from any given square on the chessboard, in such a manner that it travels successively to all 64 squares, touching each square once and only once.
It is convenient to represent a solution indicating a solution by placing the numbers 1, 2, ... , 64 in the squares of the chessboard indicating the order in which the squares are reached. Note that it is not required that the knight be able to reach the initial position by one more move; if this is possible the knight's tour is called re-entrant.
i. Discuss the data structures you would need to use to address this problem. Name these data structures and explain their purpose. Furthermore, give example values for each data structure to illustrate their purpose. For example, ask yourselves how you would represent the eight possible moves of a knight on square (5, 3) as shown below:
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
1
|
|
|
|
|
|
|
|
|
|
2
|
|
|
|
|
|
|
|
|
|
3
|
|
8
|
|
1
|
|
|
|
|
|
4
|
7
|
|
|
|
2
|
|
|
|
|
5
|
|
|
K
|
|
|
|
|
|
|
6
|
6
|
|
|
|
3
|
|
|
|
|
7
|
|
5
|
|
4
|
|
|
|
|
|
8
|
|
|
|
|
|
|
|
|
ii. Use the data structures named in (i) and devise an algorithm in ADL that calculates all the moves of the knight based on any one given square, such as the one shown above. Your algorithm needs to take into account the fact that some moves may not be possible they may be outside the scope of the chessboard.
iii. Devise an algorithm in ADL to solve the problem in the introduction of this question (i.e. The problem is to move the knight, beginning from any given square on the chessboard, in such a manner that it travels successively to all 64 squares, touching each square once and only once). You may use your algorithm in (ii) as part of the solution.
2. Priority Queues
A priority queue is a collection of elements such that each element has been assigned a priority in which elements are deleted and processed comes from the following rules:
1. An element of higher priority is processed before any element of lower priority
2. Two elements with the same priority are processed according to the order in which they were added to the queue.
An example of the use of a priority queue is in a time sharing operating system: programs of high priority are processed first, and programs with the same priority form a standard queue.
There are various ways of maintaining a priority queue in memory. In this assignment, you are expected to focus on one that uses a linked list.
i. Show a schematic diagram of a priority queue for the following "job elements". Note that the jobs are not in a particular order in this example. In your schematic diagram, clearly show the beginning and end of the priority queue.
|
Job Description
|
Priority
|
|
EEE
|
4
|
|
GGG
|
5
|
|
CCC
|
2
|
|
DDD
|
4
|
|
BBB
|
2
|
|
FFF
|
4
|
|
AAA
|
1
|
ii. Explain the properties of this data structure in relation to the position of each job element in the linked list.
iii. Devise an algorithm in ADL as an abstraction that adds a job element (i.e. its name and priority) to a priority queue. You can assume that preconditions have already been checked.
iv. Devise an algorithm in ADL as an abstraction that removes the highest priority job element from a priority queue.
v. Devise an algorithm in ADL as an abstraction that calculates the length of a priority queue.