Practice assignments

Problem 1 [Stack sortable permutation]: 
Write codes for the following:

(a) Given an input sequence S={1, 2, ..., n}, generate all possible 
stack sortable permutations obtainable from S. Count the number of 
such possible sequences. As discussed in the class, stack sortable 
permutations are generated by using PUSH and POP operations on a 
single stack. 

(b) Given two input sequences S={1, 2, ..., n} and S', where S' is 
a permutation of S, (i) determine whether S' is obtainable from S by 
a sequence of PUSH and POP operations on a single stack; (ii) if the 
answer to (i) is yes, determine the exact sequence of PUSH and POP 
operations that take S to S'. 
=====================================================================

Problem 2 [Subset sum (backtracking)]: 
Write code for the following problem that is known as the subset sum 
problem: 

Given a set of n integers X = {x1, x2, ..., xn} and an integer y, find 
a subset Y (if it exists) of X, whose sum is equal to y.  
======================================================================

Problem 3 [n-queens (backtracking)]: 
Write code for the following problem: 

(a) Given n queens on an nXn chessboard for an arbitrary value of n>=1, 
find out all the placements of the queens on the board such that no two
queens can attack each other. Also find out the number of such placements.

(b) Following discussions in the class, generate all the permutations of
1, 2, ..., n.

=======================================================================

Problem 4 [Big Integer ADT]: 
Write code for the following problem: 

A "big integer" is an integer whose digits are stored as nodes of a 
linked list
(a) Represent integers with one digit per node of a linked list; 
(b) Compute addition, multiplication, subtraction and division of two 
integers stored as "big integers"; the resultant should also be stored 
as a "big integer"
(c) Find out the result of a^n; where a and n are both positive integers. 

========================================================================

Problem 5 [Polynomial ADT]:
Write code for the following problem:

(a) Represent a polynomial of a single variable in a linked list sorted 
on the powers; 

(b) Add two such polynomials to generate a polynomial represented in a 
linked list; 

(c) Multiply two such polynomials to generate a polynomial represented 
in a linked list; 

(d) evaluates a polynomial at any real value

(e) finds the derivative of a polynomial. 

========================================================================

Problem 6 [Sparse Matrix ADT]:
Write code for the following problem:

(a) Represent a sparse matrix using linked lists as discussed in the class; 

(b) Given two matrices A and B in such formats, generate a matrix C = AxB 
where C is also stored as a sparse matrix. 

=========================================================================