Homework 1 - Due via Electronic Turnin Wednesday, January 21 at 8:00 pm
60 points total
Updated Monday Jan 19 at 6:00pm - Added clarification to problem #2
This homework will be turned in electronically. For the homeworks only
you will need to turn in
either a postscript file or a pdf (but this does not mean that you can't
still use Word if you want to). Please do not turn in
a Word document (we don't want any viruses =). It would be wonderful
if you did not do the homework in Word but rather learned LaTex or DIA,
however, Word is just fine as well. Click
here for information on creating postscript and pdf files.
1. (12 pts) Draw a singly linked list that contains three items A, B, and C.
The head
pointer points to the A item. Now explicitly write out the pointer operations
required for each of the following parts. You should have no loops, only a
set of explicit pointer operations. (Each part operates on the original
list):
a) insert D at end
b) insert D before B
c) insert D at head
d) delete B
e) delete C
2. (12 pts) A polynomial can be represented as a linked list, where each
node contains
the coefficient and the exponent of the term. For example:
Write code to add two polynomials which may be of different lengths and
can have any exponents (the two polynomials will not necessary only have the
same exponents). You may assume that the exponents are ordered from highest
(left/towards head) to lowest (right/towards tail). Assume there is a
class called polynomial
and three objects of that type already exist: P1 and P2 are the polynomials
to add and P3 will be the sum of the two. State any other
assumptions you make about the structure of the list (i.e. doubly linked,
singly linked/tail pointer/sentinal/etc).
3. (10 pts) A self-adjusting list is like a regular list, except that all
insertions
are performed at the head, and when an element in accessed through Search, it
is moved to the head of the list without changing the relative order of the
other items. The Search function returns either TRUE or FALSE based on whether
the item was found. Write the Insert and Search functions for a self-adjusting
list implemented with an array. (Your algorithm should not take into consideration
the type of item in the list.)
4. (10 pts) Write the Insert and Search functions for the self-adjusting
list implemented
with a singly linked list.
5. (8 pts) Use a stack to convert the following infix expression into a postfix
expression. Show the state of the stack at each step and show the current
postfix expression for the corresponding stack state.
a + (b - c * d) - (e - f)
6. (8 pts) Use a stack to evaluate the given postfix expression. Show the state
of the
stack at each step.
8 6 3 5 + 2 4 * 7 % - + -