Programming & Algorithm
posted by Max 2 .
(1) How to design algorithms to implement the stack operations.
(2) Write a program to multiply any two matrices. (Using Basic)
(3) Consider the algebraic expression E=(2x+y)(5a-b)^3. Draw the tree T which correspond to the expression E and find the pre-order traversal of T.
I'm not exactly sure what (1) is asking. General considerations? An exemplar? Anyway, a stack has only two operations:
push something in;
pop something out.
You will need space in which to store the items on the stack. Start with the items. What data types will you be storing? Stacks are most commonly used for integer addresses, but you need to consider what your implementation will be. The space can be preallocated in one big lump, if you specify a limitation that your stack cannot grow beyond a certain size. That makes your implementation easier than the alternative, which is to allocate new space every time a new item is pushed, and possibly deallocate it when an item is popped, or let it grow, and then deallocate it when some threshold is reached.
Now you can consider the methods themselves. Let's assume you have the easiest case, which involves a fixed-size (or elastic, with the O/S doing the allocation work for you) linear array. You must have set up:
1) an array
2) a pointer to the latest entry in that array
a) increment pointer into the array
b) copy item to the array item of current pointer
and Pop implies
a) copy array item at current pointer position into return value
b) decrement pointer
Things to consider: what happens if the pointer is about to exceed its specified limit? what happens if a pop request would decrement the pointer below its zero value?
As for (2), I suggest you start, and ask again about any problems you have. It seems to me that the hardest part of this, like many programming issues, is the input and output - in this case, how to handle the ins and outs and organize the data for matrices of wildly different shapes, and validate that they can be multiplied at all - rather than the matrix multiplication itself, which is relatively easy.
Where to start? Work a simple case, to allow you to think about the method. How do you multiply two 2x2 matrices? Work that theough step by step. What data structure do you need? What algorithm? When you've done that, consider how to adapt it for a different shape of matrix. BASIC - well, most BASICs, I suppose, since I haven't used them all - are a bit limiting in terms of what you can DIM at runtime; in BASIC, I'd be inclined to DIM a whopping big single-dimension array for each of my matrices and manage the dimensions with a couple of pointers.
(3) is really very simple, when compared with the other two.