Question

1. Be able to explain how s Stack can be used to determine the validity of parentheses in an arithmetic expression such as:

3. *  ( 2 + 4 ) * ( 8 – 5 )

or a program code such as the following:

class ABC

{

    ABC( int x)

     {

     }

}

2. Be able to determine the runtime complexity of:

1. A Java assignment statement
2. A single loop
3. Nested loop

3. Given that for any polynomial of degree n, p(x) = a_nxⁿ + a_n-1 x^n-1 + …a₁x + a₀, p(x) = O(xⁿ).              Show that:      an expression such as the following                                                                     

4x³ + 7x² + 12 is O(x³), by finding the witnesses, C and k.      

4. Which of the following statements are true?                                              

1. The running time of a loop is, at most, the running time of the statements inside the loop times the number of iterations.   
2. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(1).                            

3. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(n).

5. Considering singly linked list, be able to determine if inserting nodes at the end of a LinkedList is less time-efficient than inserting them at the front of the list.

6. Be able to differentiate between the data structures Stack, Queue, and Linked List.

7. Determine between the acronyms LIFO and FIFO, and be able to give one real life example where each is applicable

8. As it pertains to programming know the difference between Recursion and Iteration

9. Be able to express in Java code an algorithm in a recursive method. For example:

10. Be able to trace and state what a recursive method does. For example:

Given the following method, describe what this method does.

public static String convert( int n )

{

if (n == 0)

return "";

else

return convert( n / 2 ) + ""+ ( n%2 );

11. As it pertains to Data Structures what a Tree is, in general, and particular what a Binary Tree is.

12 . Be able to construct a Binary Tree from an arithmetic expression such as:

4 * 5 – 6 / 8 + 2

Answer 1

How Stack can be used to determine the validity of parentheses in an arithmetic expression

1.Starting with an empty stack, process the parenthesis strings from left to right.

2.If a symbol is an opening parenthesis, push it on the stack as a signal that a corresponding closing symbol needs to appear later.

3.If, on the other hand, a symbol is a closing parenthesis, pop the stack.

4.As long as it is possible to pop the stack to match every closing symbol, the parentheses remain balanced.

5.If at any time there is no opening symbol on the stack to match a closing symbol, the string is not balanced properly. 6.At the end of the string, when all symbols have been processed, the stack should be empty. That leads to Balanced paranethesis.

Please look at the below image to understand clearly

runtime complexity of a Java assignment statement

O(1)

runtime complexity of a Single Loop

O(n)

runtime complexity of a Nested Loop

O(mn)

Runtime of the loop depends upon number of time loop must execute in order to finish a particular task

Time complexity for constants is always O(1)

i.e., time complexity for int x=250 is O(1)

time complexity to add a node at the end of singly linked list is  θ(n). In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).

time complexity to insert an element at the front of the linked list is O(1).  To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).

Stack:

A stack is a linear data structure in which elements can be inserted and deleted only from one side of the list, called the top. A stack follows the LIFO (Last In First Out) principle, i.e., the element inserted at the last is the first element to come out. The insertion of an element into stack is called push operation, and deletion of an element from the stack is called pop operation. In stack we always keep track of the last element present in the list with a pointer called top.

Queue:

A queue is a linear data structure in which elements can be inserted only from one side of the list called rear, and the elements can be deleted only from the other side called the front. The queue data structure follows the FIFO (First In First Out) principle, i.e. the element inserted at first in the list, is the first element to be removed from the list. The insertion of an element in a queue is called an enqueue operation and the deletion of an element is called a dequeue operation. In queue we always maintain two pointers, one pointing to the element which was inserted at the first and still present in the list with the front pointer and the second pointer pointing to the element inserted at the last with the rear pointer.

Linked List:

A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Linked List is a collection of Nodes. Each Node consists of two components i.e Data and next. data represents the value and next stores the address of the immediate Node.

Real Time Example of Stack is plates in a cupboard, a driveway that is only one car wide

Real Time Example of Queue is a queue of people at ticket-window, vehicles on toll-tax bridge

Recursion and Iteration

The Recursion and Iteration both repeatedly execute the set of instructions. Recursion is when a statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the controlling condition becomes false.

The primary difference between recursion and iteration is that recursion is a process, always applied to a function and iteration is applied to the set of instructions which we want to get repeatedly executed.

Binary Tree for arithmetic expression:

Algorithm:

Algorithm infix (tree)
/*Print the infix expression for an expression tree.
 Pre : tree is a pointer to an expression tree
 Post: the infix expression has been printed*/
 if (tree not empty)
    if (tree token is operator)
       print (open parenthesis)
    end if
    infix (tree left subtree)
    print (tree token)
    infix (tree right subtree)
    if (tree token is operator)
       print (close parenthesis)
    end if
 end if
end infix