|
For your help, a sample run of the program is provided with one possible case
of user input presented as underlined text. The difficulty of the problems are
indicated in the maximum marks allocated for each of them.
You are given two integers, m and n. You need to generate m random integers from the range [0-n]. There should be no duplicates in the output data set. You should not ideally use any standard random number source ( such as random() from the standard C library) but create your own.
Optimal solutions are linear in time and constant in space.
Example:
10 5
9
2
1
6
4
You are given an integer n and a string of characters of length n. You need to print out all the permutations of the characters that form the string. The total number of such permuations is n! that are possible.
Optimal solutions are linear in time and space.
Example:
3 cat
cat
cta
tca
tac
atc
act
The Knight's tour is a well known problem in chess. The problem is as follows - you are provided with an empty chess board and an initial starting position. From that position, you are required to traverse over the entire chess board, visiting each square once and only once using a knight as the piece. Consider that from a given position, a knight can only move to one of 8 possible moves in an ideal case. The possible moves are shown below in Figure 1.
You will accept from the user 3 integers, the first two are the starting position from where the Knight will begin the tour (the Co-ordinate system is numbered with the top left hand square being (1,1) and x and y increasing left to right and top to down respectively).
The second number is that of a square of dangerous terrain that the knight cannot visit. This second number ranges from 0-2. The dangerous terrain is shown in Figure 2 for cases of 0,1 2.
You need to find a sequence of moves that will provide a solution to a input. Please print out the moves as follows with the pair X Y. Invalid solutions will result in negative points. If no complete solution is possible, attempt to cover as much of the board as possible.
Optimal solutions are linear in space and quadratic in time.
Example:
1 1 0
2 3
1 5
2 7
... etc
The Towers of Hanoi is a well known programming problem. To summarize, there a total of three pegs (named A, B, C respectively) on which a number of disks can be placed. There are n disks (named D 1, D 2 ... D n), where n is the total number of disk, a quantity input from the user. These disks are proportional in size to the number associated with them. They are initially placed on peg A in ascending order, i.e. smaller to larger.
You need to find a iterative algorithm that will determine the sequence of moves by which all the disks are trasferred to peg C and stored in ascending order. At any point, you can access only the topmost disk on any peg. In no situation can a larger disk be placed on top of a smaller disk. Conversion of the recursive solution to an iterative one is encouraged, provided you can explain the same.
Optimal solutions to this problem are both linear in time and space.
Example:
3
D 1 from A to C
D 2 from A to B
D 1 from C to B
D 3 from A to C
D 1 from B to A
D 2 from B to C
D 1 from A to C
