Hadoop Learner's Guide 1: Steps to install Hadoop on Windows with Cygwin

1. Create a folder "c:\training"

2. Download JDK version 1.7 for OS 32-bit/64-bit for JAVA
    a) URL:  http://www.oracle.com/technetwork/java/javase/downloads/index.html
    b) Download jdk-7u25-windows-x64.exe in folder "training"
    c) Create a folder "java" in folder "training"

3. Install Java
    a)  Click jdk-***.exe to install java
    b)  Give installation directory as C:\training\java

4. Download and Install Cygwin for OS 32-bit/64-bit
    a) URL: http://www.cygwin.com
    b) Click setup-x86_*.exe to download and install Cygwin
    c) Create a folder "cygwin64" in folder "training" ->   "C:\training\cygwin64\"
    d)  Follow instructions in Section "7.3 Installing Cygwin"at "http://docs.oracle.com/cd/E24628_01/install.121/e22624/preinstall_req_cygwin_ssh.htm" to install Cygwin.

       Run the setup executable, then click Next to proceed.
       

       On the Choose Installation Type screen, select Install from Internet, then click Next.

       

      On the Choose Installation Directory screen, enter C:\training\cygwin64\ as the Root Directory, then click Next.
       

      On the Select Local Package Directory screen, select a directory on your local machine C:\training\package\ where you want to store the downloaded installation files, then click Next.

     
      
     On the Select Connection Type screen, select appropriate settings to connect to the internet, then click Next.

     

     On the Choose Download Site(s) screen, select any site from the available list, then click Next.
          

    Add following packages for installation: openssh, openssl, unzip, zip
 
    On the select packages screen, ensure that you select the following packages, then click Next:
     From the Archive category, select unzip and zip as follows:



   From the Net category, select openssh and openssl as follows:



   After selecting the packages and clicking Next, the Resolving Dependencies screen is displayed. Click Next to proceed.

  On the Installation Status and Create Icons screen, do not make any changes. Click Finish to complete the installation process.

  
 
5. Setup and Start SSHD daemon
    a) Follow steps 1-3 for Section "7.4 Configuring SSH after installing Cygwin" of "http://docs.oracle.com/cd/E24628_01/install.121/e22624/preinstall_req_cygwin_ssh.htm".
    b) Navigate to the ~\training\cygwin64\ directory, right-click the cygwin.bat file and select Run as administrator.

          c) For question, if privilege separation should be used, answer  no.

*** Query: Should privilege separation be used? <yes/no>: No

    d) For question, if sshd should be installed as a service, answer yes.

*** Query: Do you want to install sshd as a service?
*** Query: <Say "no" if it is already installed as a service> <yes/no>: yes

    e)
 *** Query: Enter the value of CYGWIN for the deamon: [] bin mode ntsec
   f)*** Query: Do you want to use a different name? no
   g) *** Query: Create new privileged user account 'cyg_server'? (yes/no) yes

*** Query: Please enter the password: 

*** Query: Renter:

If the configuration is successful, you will see the following message:

Host configuration finished. Have fun!

   h)  To start Cygwin SSHD

Perform these steps:

1. Right-click on My Computer, and select Manage.
2. In the Computer Management dialog box that appears, go to Services and Applications, and select CYGWIN sshd.
3. Click CYGWIN sshd, then click the Start button.

  h) If the SSH daemon does not start up, view the c:\cygwin\var\log\sshd.log file for information on why the start up failed.

  i)  To test ssh

      > ssh localhost

         Password:

6. Setup passphraseless ssh so that password is not required

If you cannot ssh to localhost without a passphrase, execute the following commands:
$ ssh-keygen -t dsa -P '' -f ~/.ssh/id_dsa 
$ cat ~/.ssh/id_dsa.pub >> ~/.ssh/authorized_keys

Test:

>ssh localhost

No password required this time

6. Download and Install Hadoop 1.2.1 for Single Node

  a) URL: http://apache.mesi.com.ar/hadoop/common/hadoop-1.2.1/hadoop-1.2.1.tar.gz
      Download it in C:\training\
      Other urls : http://apache.mesi.com.ar/hadoop/common/
  b) Unzip the hadoop-1.2.1.tar.gz in C:\training
  c) Edit following configuration files
      c.1) Add following to c:\training\hadoop-1.2.1\conf\core-site.xml  
             <configuration>

       <property>
         <name>fs.default.name</name>
         <value>hdfs://localhost:9000</value>
       </property>
      </configuration>

    c.2) Add following to c:\training\hadoop-1.2.1\conf\hdfs-site.xml
           <configuration>

       <property>
         <name>dfs.replication</name>
         <value>1</value>
       </property>
     </configuration>

   c.3)  Add following to c:\training\hadoop-1.2.1\conf\mapred-site.xml
          <configuration>

       <property>
         <name>mapred.job.tracker</name>
         <value>localhost:9001</value>
       </property>
     </configuration>

7. Setup JAVA_HOME

    a) Set JAVA_HOME in Windows
         Create a new variable JAVA_HOME as follows:  Right-click on My Computer and go to Properties. In the System Properties window, click Advanced. In this tab, click Environment Variables. Then Add a User Variable JAVA_HOME.

Variable Name: JAVA_HOME
Variable Value: C:\training\java\jdk_1.7.0_21

  b) Set JAVA_HOME in Cygwin
       b.1) On Cygwin command line, type
              export  JAVA_HOME=/cygdrive/c/training/java/jdk_1.7.0_21 ( Linux style path name)
              or
              export JAVA_HOME=c:\\training\\java\jdk_1.7.0_21 (Notice the use of two \\ to give path)
       b.2) Add the export command in ~/.bashrc

  c) Set JAVA_HOME in hadoop scripts

            Edit C:\training\hadoop-1.2.1\conf\hadoop-env.sh to set JAVA_HOME

      JAVA_HOME=/cygdrive/c/training/java/jdk_1.7.0_21
      or
      JAVA_HOME=$JAVA_HOME  ( As it was exported in shell )


8. Start Hadoop

Format a new distributed-filesystem:
$ /cygdrive/c/training/hadoop-1.2.1/bin/hadoop namenode -format

Start the hadoop daemons:
$ /cygdrive/c/training/hadoop-1.2.1/bin/start-all.sh

The hadoop daemon log output is written to the ${HADOOP_LOG_DIR} directory (defaults to ${HADOOP_HOME}/logs).

Browse the web interface for the NameNode and the JobTracker; by default they are available at:

• NameNode - http://localhost:50070/
• JobTracker - http://localhost:50030/

Stop the hadoop daemons:

$ /cygdrive/c/training/hadoop-1.2.1/bin/stop-all.sh

Programming Interview Questions - 14

Q1. Given a calendar of events, design an algorithm to find all the overlapping events.


Q2. Given a sorted array of numbers containing duplicates, find the last occurrence of a given number.


Q3. Write a function which outputs itself.

Hint: Quine computing


Q4. Given two numbers x and y having equal number of digits, rearrange x such that x is greater than y and difference d = (x-y) is the least among all the x's possible by its rearrangement.
Example: x = 1234
               y = 2410
Rearranged x is 2413


Q5.  We have given a matrix A[m][n] where each cell is either 0 or 1. Adjacent cells ( top, bottom, left, and right ) having similar value (1 or 0) are considered connected. An island is a set of connected cells. Design an algorithm to count the numbers of the dis-connected islands.

Programming Interview Questions - 13

Q1.  Given an unsorted array of -ve's, +ve's, and zeros, design an algorithm to arrange the numbers such that all the -ve's are in the left, zeroes are in the middle, and all the +ve's are in the right of the array.

Hint1: Dutch national flag problem
Hint2: Quick sort with 0 as pivot such that all -ve's are left of first zero and all the duplicate zeroes and +ve's are right of the first zero.  Duplicate zeroes and +ve's may be in nay order. So, we again apply quicksort on right sub-array with 1 as pivot.


Q2.  Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.


Q3.  Count the number of 1's in a number's representation.

Hint:    while(num > 0) { count++ ;  num = num & (num-1);}


Q4.  Given an array of N numbers, find a set of k numbers whose sum is maximum.
Hint: Find top-k greatest numbers. Construct a max heap in O(n) time and  retrieve top-k in O(k log n).


Q5. Given two arrays A and B of  N and M elements each, write an algorithm to find min(|A[i]-B[j]|).

Hint: Sort each of the arrays in the ascending order. Use an algorithm similar to merge sort to find adjacent pairs of A and B in the combined sorted array. In place of creating a new sorted array, in the merge process itself, find the pairs and take the difference. Find the pair with the smallest difference.


Q6.  Given a string of characters, find the longest substring made up of only three distinct characters.

E.g. Given string s =  abcdaaabbcccefbccc
Here the longest substring having 3 distinct characters is "aaabbccc".

Hint:  Use the principle of Knuth-Morris-Prat algorithm. Remember the position of three characters.


Q7.  Given an array of  integers, design an algorithm to put all the zeros in the beginning of the array.

Hint: 1. Use the principle of quick-sort.
        2. Scan from both ends of the array using a left index  ( i from 0 to n-1, i++)  and a right index ( j from n-1 to 0, j-- ). Exchange a non-zero element on the left with a zero element on the right.  Repeat this until the i < j.


Q8. Given  N  two-dimensional co-ordinates (X_i, Y_i ), find the line passing through the most co-ordinates.

Hint: Hough Transform


Q9.  Given an array of +ve integers and the option to change any integer to it negative value as per required, design an algorithm to find the minimum sum  S >= 0 and all the changes required.


Q10.  Given a sorted list of non-overlapping intervals A= {(4-8),(10-12), (17-23), (25-31)}, design following functions
(a) Given a new interval (a-b), insert it into A such that the list is still sorted and the intervals are non-overlapping.  We can merge all the intervals that overlap with the new interval.
e.g.: Insert (9,24) into A.
       Result list A = {(4-8),(9-24),(25-31)}

Important Java Questions

1. Differentiate between procedural programming and object oriented programming.
2. What are interfaces?
3. Describe some advantages of interfaces.
4. What are abstract classes?
5. What are the differences between an interface and an abstract class?
6. What is method overriding and method overloading?
7. What is polymorphism?
8. What is difference between aggregation and composition association?
9. What are immutable objects? How to make an object immutable?
10. What is deadlock and livelock?
11. How to achieve synchronization in a multi-thread java programming? Method level synchronization and Block level synchronization. Static method synchronization.
12. How to implement a thread?
13. Difference between a thread and a process.
14. Describe a scenario where a deadlock happens.
15. How to handle exceptions in Java?
16. What is a Singleton and how to implement it?
17. Difference between Hashmap and Hashtable?
18. Difference between Vector  and LinkedList?
19. Regular Expressions in Java?
20. Difference between inheritence and composition ?
21. Difference between comparator and comparable interfaces?
21. Design patterns in oops programming?
22. What are re-entrant locks?
23. Difference between implicit and explicit locking?
24. What are marker interfaces?
25. What is the difference between a concurrent hashmap and concurrency achieved using synchronized keyword?
26.What is the difference between an enumerator and an iterator? Which is fail-safe and which one is fail-fast?
27. What is difference between a volatile variable and a ThreadLocal variable?
28. can an interface declare a private method?
29. can a constructor throw an exception?
30. A method declaration in an interface has throws exception. is it necessary for implementing class to throw an exception?
31. What are generics?
32. How to determine the datatype of a generic type?
33. What is a race condition in a software?
34. What is a phantom reference?

Software Engineering Interview Questions - 12

Q1. Given N points in a 2-Dimensional space, find a point (x, y) which minimizes the sum to all the given points.

Hint: Its an important problem studied in operations research as facility location problem.  The problem has a variety of form. The above problem is Ferment Weber Problem.

a) For L1 norm (also see Lp space, Normed Vector Space from linear algebra), its the median that minimizes the sum. See the derivative of an absolute function for an insight.

b) For L2 or Euclidean distance  ( see Euclidean Space for more details), there is no closed form solution as discussed in Ferment Weber Problem.

Note: See the difference from centroid as used in k-means clustering or centre of mass.


Q2.  Design an algorithm to count the number of binary strings of size n that can be formed with the constraint that a 0  has a 1 in its immediate left.

Example:  101010 -> Right
                001010 ->Wrong

Hint: F(n) = F(n-1) + F(n-2)
        Let's suppose that the rightmost bit is 0. Then the 2nd rightmost bit has to be 1. This gives F(n-2) binary strings. If the rightmost bit is 1. Then, we get F(n-1) binary strings.




Q3.  Given a matrix  MxN of numbers, find the sub-matrix with the largest sum.

Hint: 2-Dimensional Kadane Algorithm

Flow of execution:

Input Matrix

      C1   C2   C3  C4  C5  C6
R1
R2
R3
R4
R5

Compute Sum1


                                  C1   C2   C3  C4  C5  C6
R1
R1+R2
R1+R2+R3
R1+R2+R3+R4
R1+R2+R3+R4+R5

Perform 1-D Kadane for each row from row R1 to R5.

Compute Sum2.

                              C1   C2   C3  C4  C5  C6
--
R2
R2+R3
R2+R3+R4
R2+R3+R4+R5

Perform 1-D Kadane for each row from R2 to R5.

...... Continue
Complexity O(N^3)

Q4. Given a matrix MxN with 0's and 1's where 0 means a lake and 1 means land, design an algorithm to find the shortest path from [0, 0] to [1, 1].

Hint: Use flood fill algorithm which is similar to a Breadth First Search on a graph.



Q5. Given a sorted array of numbers where each number is repeated multiple times, design an algorithm to find the first occurrence of a given number.

Hint: Binary search


Q6. Given an array of numbers where every number except one is repeated, efficiently find the number.

Hint: Use XOR


Q7.  Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.

Hint:  Use XOR with Divide and Conquer. An XOR of all the numbers is only the XOR of the two non-repeating numbers. Take a set bit of the result.  Le it be the kth bit. This bit is set because the corresponding bits in the non-repeating numbers are opposite. Now divide all the numbers into two groups, one having the kth bit as 0 and the other having kth bit as 1. Take XOR of each of the groups. The resultants are the non-repeating numbers.

X & ~(X-1) gives the least significant set bit. (X-1) has the property to shift the least significant set bit to left.

The idea can be recursively used to find k non-repeating numbers.


Q8.  Given an array of numbers where all the numbers are repeated odd number of times except one which is repeated even number of times, design an algorithm to find the number which is repeated even number of times. 


Q9.  Given an array of numbers where some numbers occur only ones, some are repeated twice and only one number occur thrice, design an algorithm to find the number that occur thrice.


Q10. Given an array of numbers where all number occur three times except one which occur only once, design an algorithm to find the number that occur only once.

Interesting Problems on Trees - 3

Q1. Given a Preorder traversal of a Binary Search Tree, reconstruct the tree.

Hint: First node is root. Scan the traversal till we get a value greater than the root.  Then, the left part forms the left subtree whereas right part forms the right subtree.

Q2. Given a Preorder traversal of a Binary Search Tree, design an algorithm to verify if each non-leaf node has only one children.

Hint:  a) If a node has only one children then all its children are greater ( for right subtree) or lesser ( for a left subtree ) than it.  IN preorder traversal all the children of a node comes after the node. So, we just need to check if all the nodes are greater or lesser. To do it efficiently, we can use the property that the largest node is the rightmost node whereas the smallest node is the leftmost node.

b) Construct a BST from Preorder traversal. First node is root. Scan the traversal till we get a value greater than the root.  Then, the left part forms the left subtree whereas right part forms the right subtree.


Q3. Two nodes in a binary search tree are swapped, design an algorithm to correct the tree.

Hint: Perform an inorder traversal. At each step verify if we are getting a sorted sequence by inorder traversal. This can be obtained by comparing a number with its successor and predecessor. If the node does not satisfy the constraint,  then remember the node. Finally, fix the two nodes which have been swapped.


Q4.  Given a Binary Search Tree and two numbers x and y, find the shortest path ( minimum number of hops) between the numbers.

Hint: Perform a simultaneous search for the  numbers in the BST. The first node where the search splits is the least common ancestor the numbers.  Taking this as reference node, find the depth of each of the nodes from this reference node. Sum of the depths is the length of the shortest path.


Q5.  Given two binary search tree, merge these in-place to get a new binary search tree.

Java source code:
Main class: MergeTwoBST.java 
Other classes: BinaryTree.java , Node.java , NodeInt.java , NodeStr.java 
Input File: UnorderedNumberSequence

Software Engineering Interview Questions - 11

Q1. Give an algorithm to serialize a binary tree into stream, and then reconstruct the binary tree from the stream.

Hint:  a) If binary tree is in array, we can serialize ans deserialize in a straight forward manner. 

         b) Preorder and Inorder traversal.

         c) Serialize using pattern {parent} {left subtree} {right subtree} recursively.

Q2.  Print all the M size combinations of a N size set in a sequence such that each set of the sequence can be obtained from its preceding set by removing one element and adding a new element. 

Q3. Find all the duplicates in a given Binary Search Tree without using any extra space. 

Hint: Use an inorder traversal and match the current node with the last node to check if they are duplicates.

Q4. Given a list of numbers A= {5, 10, 15, 20, 21, 23} and associated probability of occurrence P={ 0.1, 0.3, 0.05. 0.13, 0.02,  0.4} such that sum(P[i]) = 1, construct a Binary Search Tree that minimizes the expected access time of the nodes  given a message having the numbers in A. The cost of access of a node at depth d (the number of comparisons required to access the node at depth d ) is d+1.  Let n be a node at depth d in the BST with probability of occurrence p, then the minimization function is sum(p(n)*(d+1) over all n)

Hint: Use dynamic programming.


Q5. Given two tumblers of capacity 5 (m) liters and 3 (n) liters where m-n=k, design a technique to measure 4 (x) liters.
Note: This is famous as puzzle. Here, we want an actual algorithm to do it.


Q6.Write an algorithm to solve Tower of Hanoi .


Q7.  Given a N x N matrix of numbers, design an  efficient algorithm to perform a 90 degree rotation of the  matrix.

Hint:  Assume matrix A to be made up of layers similar to an Onion. Perform a  layer by layer rotation starting from the outermost layer to the innermost layer. To perform a rotation at a given layer, start from any corner and move the corner elements in clockwise directions by n-1 steps. We start from A[0][0]. We
move as follows:
A[0][0] -> A[n-1][0] -> A[n-1][n-1] -> A[0][n-1] -> A[0][0]
Then move, A[0][1] -> A[n-2][0] -> A[n-1][n-2] -> A[1][n-1] -> A[0][1] and so on.


Q8.  Given a linked list where each node also has a pointer to some arbitrary node in the list, design an algorithm to clone the linked list.


Hint:  Let A be a linked list. Insert a new node in front of the every node of A and copy value from the previous node to create a new linked list B.  Now to copy the arbitrary pointers use following logic

B(Current).Next.Arbitray_Pointer = B(Current).Arbitrary_Pointer.Next

Finally restore the original linked list as follows:

Original_Head = Original_Current = B(Head)
Clone_Head= Original_Current.Next
-- Begin For loop
Clone_Current = Original_Current.Next
Original_Current .Next = Clone_Current .Next
Original_Current  = Original_Current .Next
--End loop


Q9.  Given a histogram, find the maximum area rectangle within the histogram.

Hint: For each bar, the largest rectangle obtained by the bar would be:
 The  height of the bar (h) *
 The maximum left extension without decreasing the bar height  (l) *
 The maximum right extension without decreasing the height of the bar (r) .

To efficiently obtain l and h use following idea of stack.
Initialize a stack with top of the stack, TOS= 0
Compute l as ( i - TOS)

For bar i = 1, l = i - TOS = 1 - 0 = 1
Push bar 1 is the stack, TOS = 1
For bar i = 2,  pop out bars til we find a bar of height smaller than second bar, and recompute TOS
l = i - TOS
...

Similarly compute r.

All this will have a time complexity of O(n)


Q10.  Given an array of integers, design an algorithm to find:
          a) the largest sub-array whose elements can be arranged into a continuous sequence.
          b) the longest continuous sequence.


Hint (b) Sort and then do a linear scan. For fixed interval,  a bitset can be used.

Starting Oracle Database Enterprise Manager

1. Switch user to root
    su root
     or
    sudo su

2. Set ORACLE_SID
    ORACLE_SID = ORCL
    export ORACLE_SID

3. Set ORACLE_HOSTNAME
    ORACLE_HOSTNAME= localhost
    export ORACLE_HOSTNAME

4. emctl start dbconsole

    emctl is available in bin folder in Oracle  installation folder
    oracle/product/11.2.0/dbhome_1/bin

5. Access oracle enterprise manager using the URL: https://localhost:1158/em

Software Engineering Interview Questions - 10

Q1. Find the square root of  a number x.

   Hint: Use Newton Raphson method or Bisection Method / Binary Search Method.

           Let  y^2=x  =>  y^2 - x = 0

           Let f(y) = y^2 -x

           y_n = y_(n-1) - f(y)/f ' (y)

Q2.  Given an array of numbers, find the first number that is unique in the array.

Hint:  Use a LinkedHashMap

Different implementations of Map in java are :  Hashtable (obsolete), HashMap (Supports null key and null value ),  LinkedHashMap,  TreeMap (Red-Black tree Navigable Key Sorted Map),  EnumMap ( Uses Enum keys and sorted on natural order of Enum keys),  ConcurrentSkipListMap (SkipList based implementation ), ConcurrentHashMap (Supports concurrency), IdentityHashMap (Uses reference-equality rather than Object-equality for comparing keys), and  WeakHashMap.


Q3.  There is a file which has n numbers in the nth line. For example,
         7
         2 9
         8 3 1
         2 7 9 1
       Now, starting from the top and moving down using the adjacent numbers in the below row, find the maximum sum of such a path. For example, adjacent numbers for 2nd number 9 in the row 2 are 8, 3, and 1 in row 3.

Hint: Use dynamic programming. Start from nth row and traverse back. Let the input file is stored in a half matrix/ 2-D array A. For an element at A[i][j],
A[i][j] = max(sum(A[i][j]+A[i+1][j]), sum(A[i][j]+A[i+1][j-1]),sum(A[i][j]+A[i+1][j+1]))
Pick the max sum for i = 0, i.e., 0th row.


Q4. Given n points on a circle, find the different number of ways of drawing non-intersecting chords between the n points.

Hint: Motzkin number


Q5. Given an unsorted array A where ith element A[i] is within k position from its position j in the sorted array, i.e., |j-i|=k, design an algorithm to efficiently sort the array.

Hint: Sort using a heap of size 2k. Create a minimum heap using the first 2K elements A[0 - (2k-1)]. Remove the head of the heap which is the smallest element and place at A[0]. Reorganize the heap. Insert A[2k] element in the heap. Remove the head and place at A[1]. Continue till we reach the end of the array.     This gives sorted array till A[n-k]. Finally, a heap sort is used on the remainder of the heap to get the last (2k-1) elements in sorted order.  Time complexity: O(N logk).


Q6. Given a palindrome date 2001/10/02, find the next date which is palindrome.

Hint: 20011002 is palindrome. increment 2001 till we get last 2 digits which gives a possible month when the digits are flipped. That is the next date.

Q7. Given an unsorted array of numbers, find the longest sub-array whose elements form a continuous sequence.
Example: A = {12, 1, 19, 16, 15, 18, 17, 2, 5}
Answer: {19, 16, 15, 18, 17}




Q8.  Given a stream of characters, design an algorithm to find a given string in it.

Hint: Knuth-Morris-Pratt Algorithm


Q9. Given a sorted array of numbers having multiple duplicates, find the first occurrence of a given number.


Hint: Perform a binary search.  Once we find the element at ith position, we check if A[i-1] < 0 or i=0. If not, we continue search in the left sub-array.

Q10.  Given an array of numbers and a set of operators ( +, -, *, /), find the smallest number that can not be formed by the numbers and operators. Order of the numbers in the array needs to be maintained while forming an expression with the operators.

Software Engineering Interview Questions - 9

Q1. Compress a given string using Huffman Encoding.


Q2. Given two integers a and b, find their
       a) greatest common divisor (gcd)
       b) least common multiple (lcm)

Hint: a) Use euclidean division algorithm
                  gcd(a, 0) = a
                  gcd(a,b) = gcd (b, a mod b)

        b) Use relation lcm(a, b) = (|a*b|)/gcd(a, b)


Q3. Design an algorithm to efficiently compute binomial coefficient C(n , k).

Hint: Use recurrence formula
       C(n, k)= C(n-1, k-1) + C(n-1, k)
       C(0, k )=  0 for all integers k>0
       C(n, 0) = 1 for all integers n>=0

       Similarly, there is pascal's rule and pascal's triangle


Q4.  Design an algorithm to evaluate a fully parenthesized  infix expression/Polish Notation.
Example: (((2 * 5) - (1 * 2)) / (11 - 9))

Hint: Use a single stack data structure with operator precedence.


Q5.  Design an algorithm to evaluate a partially parenthesized infix expression.
Example:  (2 * 5 - 1 * 2) / (11 - 9)

Hint:  Use a character stack that stores the operators, a number stack for operands, and follow precedence rule.


Q6.  Design an algorithm to evaluate a prefix expression.

Example: / -  * 2 5 * 1 2 - 11 9

Hint: Read the whole expression in a stack and perform operation from last to first.


Q7.  Design an algorithm to evaluate a postfix expression/Reverse Polish Notation.
     

Q8. Design an algorithm to convert a fully parenthesized infix expression into prefix expression.


Q9. Design an algorithm to convert a fully parenthesized infix expression into postfix expression.
Hint: a) Use a character stack to store operators. Print the operands. Pop operands when we get a closing bracket.
b) Shunting-Yard  Algorithm


Q10. Given a graph G={V, E} where V is the set of vertices and E is the set of edges with unit weight and two vertices S and T, design an algorithm to find the smallest path between the nodes.

Hint: Perform a bidirectional Breadth First Search from both S and T.