Assignment 3

COP 3530 - Data Structures

 

 

Instructions:

1.     Create a document (Word or pdf) that contains all your answers and all your code.

2.     Send, by the due date (midnight), a soft copy of the document, the java files and the class files by email to Ramakrishna ramakrishna@cis.fiu.edu (of course in a single email).

3.     Turn in a hard copy of your document in class on the due date. If you are unable to come to class leave it in my mailbox the same day.

The due dates are specified in the main class web page.

 

 

Questions

 

Note: For all questions which require you to provide an algorithm or pseudo code, you need to describe the basic idea behind the algorithm you are presenting in a few sentences before presenting the pseudo code.

 

  1. [15 points] Give an algorithm for finding the penultimate (one before the last) node in a singly linked list where the last element is indicated by a null next reference. Also give its time complexity.
  2. [15 points] Give an algorithm for concatenating two doubly linked lists L and M, with header and trailer sentinel nodes, into a single list LM.
  3. [30 points] Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if “(exp1) op (exp2)” is a normal fully parenthesized expression whose operation is op, then the postfix version of this is “exp1 exp2 op”. The postfix version of a single number or variable is just that number or variable. So, for example, the postfix version of “((5+2)*(8-3))/4” is “5 2 + 8 3 - * 4 /”. Describe an algorithm (pseudo code) for evaluating an expression in postfix notation. Formally define the problem in terms of input and output.  (Hint: Use stack as the data structure)
  4. [20 points] Create a Java class for a singly linked list that implements a list interface that contains the following methods:

A)    public void add(Object item, int position)

B)     public boolean contains(Object item)

C)    public boolean remove(int position)

D)    public int getLength()

Write the code for the interface, the class and a main method for testing the class.

 

 

 

  1. [20 points] Create a Tree class in Java that has the following structure (note that you do not need to study the lectures on trees to solve this problem):

 

You have to create a TreeNode class to represent each node of the tree. Each tree node has an int data element to store an integer value. Also, at all times, all elements in the left sub-tree are lesser than or equal to the root element and all elements in the right sub-tree are greater than the root element. This is true for all elements in the tree. In the tree class have the following methods:

A)    public void insert(int x)

B)     public Boolean search(int x)

Also have a main method to do a series of inserts and searches.