CS 14 - Homework 2

Due Thursday, April 25 (at beginning of class)

1. A polynomial can be represented as a linked list, where each node contains the coefficient and the exponent of a term. For example, the polynomial 4x³ + 3x² - 5 would be represented by the linked list:

Write code to add two polynomials. Assume there is a class called polynomial and two objects of that type that already exist (P1 and P2). State any other assumptions you make. Give the Big-Oh notation.

2. Write a function called MoveToFront that moves a specified node to the front of the list (assume you already have a pointer to the node). Write this function for an array implemented list and a linked list. State any other assumptions you are making. Write the Big-Oh notation for each function.

3. 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)

4. 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 % - + -

5. Show how to implement a queue using two stacks. Describe the Enqueue and Dequeue functions and state their Big-Oh notation. You may assume the Stack has the functions Push, Pop, and Empty. You do not have to actually write the code, you may just describe the method and use pictures, but be sure you are clear.

6. Show how to implement a stack using two queues. Describe the Push and Pop functions and state their Big-Oh notation. You may assume the Queue has the functions Enqueue, Dequeue, and Empty. You do not have to actually write the code, you may just describe the method and use pictures, but be sure you are clear.