Day 15 (September 12, 2013)  
Assignment to be done in class and as exercises.

Assignment 1: 
Write a program in C that implements the abstract data type 
stack. The functions that you need to support are 
(i) creation of a stack, 
(ii) checking whether the stack is full, 
(iii) pushing an element onto the stack,  
(iv) checking whether the stack is empty,
(v) poping an element from the stack

Implement the above using dynamic arrays. 

Assignment 2: 
Write a program in C that uses stack to solve the maze problem. 
A maze is a 2D array (of size NxM) in which 0s represent open paths 
and 1s represent the barriers. The entrance is at the top left (0,0)
and the exit is at bottom right (N-1 x M-1). A movement to any of the 
(at most) 8 neighbours (N,E,W,S,NE,SE,SW,NW) are possible. We explore 
the maze by saving the current position and exploring unexplored 
locations. We do not visit an already visited location. 

Implement the above using stacks and other appropriate data structures. 
 
Assignment 3: 
Write a program in C that takes an input (say n) and generates all 
possible stack sortable permutations of the numbers 1, 2, ..., n. 
How many such permutations can one generate? Can you characterize the 
permutations that cannot be generated? Find it analytically. 


------------------------------------------------------------------------
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: 
--------------------------------------------------------------------*/