Assignment Set 6 (Uploaded on September 16, 2015)
Clarification deadline date: September 25, 2015
Submission deadline date:  October 5, 2015

[Total Marks: 100 {Problem 1} + 70 {Problem 2} + 100 {Problem 3} + 30 {Makefile} = 300]

-------------------------------------------------------------------------

Problem 1
This is a problem to simulate a single machine job scheduling system using
a queue. You have to read the problem description carefully and break it
into meaningful sub-modules and implement functions for them in C.

Each job, j_i has a processing time t_i and the jobs are stored in a queue.
The processing time t_i for a job j_i is generated randomly. Whenever a job
arrives, it is stored at the end of the queue. The machine attends to each
job for a fixed amount of time, say t seconds. Within t seconds, if the job
is finished, then it is removed from the queue; else it is added at the end
of the queue. While adding the job at the end of the queue, the processing
time of the job is reduced by the time t.

[Marks: 80 + 20 {Good programming habits} = 100]

-------------------------------------------------------------------------

Problem 2
This problem is about sorting using stacks. Write a C program

(a) that takes an input n from the user and generates a dynamic array A of
    size n and fills in the integer i, 1 <= i <= n, in the i-th position of A.

(b) for all permutations of the elements of A, implements the following algorithm:

    ALGORITHM STACKSORT(array A)

    Initializes a stack S;
    for(each element a_i of A){
      while((S is not empty) AND (a_i > the top element of S)){
          POP S to output;
      }
      PUSH a_i onto S;
    }
    while(S is not empty){
      POP S to output;
    }

(c) The above algorithm, if implemented correctly, will sort in ascending
    order some of the permutations of A. Find out the permutations that were
    sorted using the above algorithm; also find the number of such permutations.

[Marks: 50 + 20 {Good programming habits} = 70]

[Note: You can reuse the code for permutation that is in the course web-page;
this will not be treated as copying.]

-------------------------------------------------------------------------

Problem 3
Tower of Hanoi: There are three pegs A, B, C. Initially, Peg A contains n disks
(with holes at their centers). The disks have radii 1, 2, ..., n, and are arranged
in Peg A in increasing order of their sizes, from top to bottom. That is, the disk
of radius 1 is at the top, the disk of radius 2 is just below it, and so on, till
the disk of radius n is at the bottom. Your task is to move the disks from Peg A
to Peg B in such a way that you are never allowed to place a larger disk on top of
a smaller disk. You may use Peg C as an auxiliary location for the transfer.

Write a C program that takes as input the number of disks (n) from the user, and
completes the transfer following the aforesaid rules, using three Stacks A, B and C,
constructed using singly linked lists. You may treat each stack as the respective
peg in the problem, where stack A starts with all n disks in it, and your target
is to transfer all n disks to stack B at the end of the process, using stack C as
an auxiliary location. Your program should simulate every step of the transfer
process by printing all three stacks A, B, C after every disk transfer.

[Marks: 80 + 20 {Good programming habits} = 100]

[Note: You can reuse YOUR OWN code for stacks constructed using singly linked lists,
completed earlier as a part of this course; this will not be treated as copying.]

-------------------------------------------------------------------------
[Make your program multifile and write a proper makefile to compile your
program. Name your makefile as make15xx, where xx is your roll number.
Your makefile should be such that we can automatically run your makefile
with the make command.]

[Marks: 30 {Makefile}]
-------------------------------------------------------------------------

Naming conventions for program files. xx is your roll number:

For Problem 1:
The name of the src file for problem 1 of assignment 6 should be
``cs15xx-assign6-src-prog1.c''.

The name of the app file for problem 1 of assignment 6 should be
``cs15xx-assign6-prog1.c''.

The name of the include file for problem 1 of assignment 6 should be
``cs15xx-assign6-prog1.h''.


For Problem 2:
The name of the src file for problem 2 of assignment 6 should be
``cs15xx-assign6-src-prog2.c''.

The name of the app file for problem 2 of assignment 6 should be
``cs15xx-assign6-prog2.c''.

The name of the include file for problem 2 of assignment 6 should be
``cs15xx-assign6-prog2.h''.

For Problem 3:
The name of the src file for problem 3 of assignment 6 should be
``cs15xx-assign6-src-prog3.c''.

The name of the app file for problem 3 of assignment 6 should be
``cs15xx-assign6-prog3.c''.

The name of the include file for problem 3 of assignment 6 should be
``cs15xx-assign6-prog3.h''.
-----------------------------------------------------------------------

At the top of each of your program files, add the following. If you are
writing multi-file programs, then each file should have it.

/*------------------------------------------------------------------
Name:
Roll Number:
Date of Submission:
Deadline date:
Program description:
Acknowledgements:
--------------------------------------------------------------------*/