A. Write a pseudocode/function that will delete from an unsorted linked list of integers the node that contains the smaller integer. Can you do this with a single traversal of the list?

B. Write a pseudocode/function to count the number of items(assume Integer items) in a linked list- Iteratively.

C. Convert each of the following infix expression to postfix. Use normal rules for precedence and associativity.

a.                  (4-11)*(6/7)+15

b.                 13-8+3*9/12

c.                  a/b/(c-(d+c)*f+q*p%r

D. using the following postfix expressions, use a stack to solve them producing a final result.

a.                 69 5 7 25 7 * +-18 25 5 / 20 25 20% +*+ ++

b.                 4  7  3 + 8  10  * 2 6 / 9 3 % 11 - ++- +

E.Given a language: L ={w:w is of the  for some n>=0} write the pseudocode for a recursive function that will take as a parameter a string and test to see if that string belong to this language. The function will return true or false.

Using the following grammar (used for this specific assignment statement), graw a parse tree for the expression:

A=B-A/C * (A+C*B)

      →      =

            →        A | B | C

        →        + | * | () | -< | /

|

F. This grammar generates sentences(S) made up of nouns (N) and verbs(V). Generate two sentences that make sense and two that don't.

NOTE: NP is noun phrase and

            VP is verb Phrase

S         →         NP VP

NP        →        the N

VP        →         V NP

V          →         sings | eats

N          →         cat | song | canary

G. Show that you have two stacks - astack filled with data and auxstack which is empty-show how you can do each of the following tasks by using only the stack operations of the stack ADT we discussed in class. Make sure you also explain the steps you are doing in the order you are doing them.

a.   Display the contents of the astack in reverse order; that is display the top last.

Astack

b.         Count the number of items in astack, leaving astack unchanged.

c.           Delete every occurrence of 25 from astack leaving the order of the remaining items unchanged.

H. Given the following array consisting of the nodes of a tree, draw the tree consisting of NON-EMPTY NODES ONLY.

NOTE: the & indicates an empty node.