Binary Tree Construction and Traversals

Tree Construction

1.  Given a sorted linked list, construct a Binary Search Tree.

2.  Given a doubly linked list, construct a Binary Search Tree and vice-a-versa.

3. Construct a  Binary Search Tree  given a preorder and an inorder traversal of the tree.

  Example:
    

   Inorder:  B D A E F C
   Preorder:  A B D C E F

   Java source code:  Main class -> TreeConstructionInorderPreorder.java
                                Other classes -> BinaryTree.java, Node.java  
   Input File: TreeTraInput.txt

Traversals

Types of Binary Tree

    1. Normal Binary Tree

    2. Binary Search Tree

    3. Threaded Binary Tree

Type of Traversals ( Wiki )

    Depth-First

         1.  Preorder

         2.  Inorder

         3.  Postorder

  

    Breadth First 

        4. Level order  

        5. Zig-Zag 

    

Methodology

    1. Recursive 

    2. Iterative using Stack
    3. Inorder tree traversal without recursion and  use of stack ( Hint : Morris Traversal, Morris Traversal 2)
    

Nearest Neighbor Search Using Data Projections and Hashing

1. Introduction

Random data projection with hash-based index structures has come to be the state-of-the-art method for both an efficient near neighbor search and a scalable cluster analysis for very high-dimensional data.  Data of very high dimensions pose serious computational challenge because of curse-of-dimensionality [Slide]. Random projections are also commonly used for dimension reduction.  An instance of random projection, Locality sensitive hashing, has widely attracted the attention of research community and is an active area of further research. This article gives resources for detailed reading on projection method.

2. Near Neighbor Search  

    a)  Types of queries

       1. Nearest neighbor queries

       2. Top-k nearest neighbors queries

       3. Range queries

       4. r-Near neighbor queries or ball-queries

       5. Approximate nearest neighbor queries (ANN )

       6. All nearest-neighbor queries  or Group queries or multi-object queries
       7. Reverse nearest neighbor queries
       8. List of other queries
       

   b) Hashing functions for different distance metrics

      1. Stable distributions for L1 Norm and L2 Norm (Euclidean distance)       

      2. Bit sampling for Hamming distance

      3. Min-Hash for Jaccard Similarity Coefficient

      4. Random Hyperplane for Cosine Similarity 

      5. Earth Mover's Distance

      6.

   c) References 

   
      2012

              1. SIMP: Accurate and Efficient Near Neighbor Search in High Dimensional Spaces ( Note: Method shown to yield very efficient search result on more than 100 million 128-dimensional vectors.  This is one of the largest dataset used for measuring the performance of a high-dimensional search algorithm). 

     
      2011
      2010
             1. Kernelized Locality-Sensitive Hashing for Scalable Image Search
             2. An Algorithm and Hardware Design for Very Fast Similarity Search in High Dimensional Space

      2009

            1. LSB Tree: Efficient and Accurate Nearest Neighbor and Closest Pair Search in High Dimensional Space

      2008

              1.  A Posteriori Multi-Probe Locality Sensitive Hashing 

              2.  Modeling LSH for Performance Tuning
              3.  Lecture Notes

      2007

               1. Multi-probe LSH: efficient indexing for high-dimensional similarity search ( Caveat : )

      2006

           1. Lower bounds on Locality Sensitive Hashing

           2.   Entropy based Nearest Neighbor Search in High Dimensions

           3.   Near-Optimal Hashing Algorithms for Near Neighbor Problem in High Dimensions

           4.   Nearest Neighbor Methods in Learning and Vision: Theory and Practice

      2005

           1. LSH Forest: Self-Tuning Indexes for Similarity Search

          

      2004
 
            1. Locality-sensitive hashing scheme based on p-stable distributions

     2003
     2002
            1. Similarity Estimation Techniques from Rounding Algorithms

     2001
            1. Random projection in dimensionality reduction: Applications to image and text data
            2. Database-friendly Random Projections
            3. Database-friendly random projections: Johnson-Lindenstrauss with binary coins

     2000
            1. Experiments with Random Projections

     1999
           1.  Similarity Search in High Dimensions via Hashing
           2.  A Small Approximately Min-Wise Independent Family of Hash Functions

     1998
           1.  Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality
           2.  Min-Wise Independent Permutations

     1997
            1. Two algorithms for nearest-neighbor search in high dimensions

     1984
            1.  W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space

  

  d) Implementations

          1.  Implementation of p-Stable LSH
          2.  LSHKit
          3.  SIMP
          4.  LSB

3. Image Search using Random Projections and LSH 

1. Random projection in dimensionality reduction: Applications to image and text data
2. Efficient Near-duplicate detection and sub-image retrieval
3. Near Duplicate Image Detection: min-Hash and tf-idf Weighting
4. Geometric min-Hashing: Finding a (Thick) Needle in a Haystack
5. Caltech Work

4. Scalable Cluster Analysis using Min-Hash

1.  Scalable technique for clustering the web
2.  Random Projection for High Dimensional Data Clustering: A Cluster Ensemble Approach
3.  Dimensionality Reduction by Random Mapping: Fast Similarity Computation for Clustering

Linked List Problems

1. Find the nth element from the end of a singly linked list.

    Approach 1:  Traverse the list  and find the length L of the list. Traverse the list second time and find (L-(n-1))th element from the head/start of the linked list.   Total traversal cost (L-n+1).

   Approach 2: Take two pointers A and B. Initialize both pointers to the head of the list. First move B to point to the nth node in the list. Next, move both pointers A and B together. Terminate the process when B points to the last node. At termination. A points to the nth node from the end of the linked list.  

2. What are  important types of linked lists.
  Singly Linked List,  Doubly Linked List, XOR-Linked List, and Circular Linked List.

3. Given a   circular linked list (singly-connected) and a pointer (head) to a node in the list , insert a node just before the head without fully traversing the list.

   Hint:  Insert a node after the head, switch values of head node and new node, move the head  to next

4. Give an algorithm to find if a linked list is circular or not.

5.  Give an algorithm to find  if a  linked list has a cycle/loop.
     Floyd's Cycle Detection Algorithm
     Some other solutions

6.  How to construct an efficient doubly-connected linked list.

     Hint: XOR-Linked List

7.  Given a forked linked list, find the point of fork.

                              G---H---I
                                           |
      A---B---C---D---E---F---J---K---L--M
                             
     In the above forked linked list, we see that J is the forking point.

8. Code to simulate Josephus problem.

    Hint: Use circular linked list.

Interesting String Problems

 1.  Longest common substring problem 

    Variant 1:      Longest common substring in two given strings. Let "aabcdefgh"  and  "ccbcdefff"  be two strings. Then the longest common substring is "bcdef".

    Variant  2: Longest repeating substring in a given string.  Let  "aabcdefghccbcdefff " be a string. Then, the longest repeating substring is again "bcdef".


2.   Longest palindromic substring

Given a string, the problem is to find the longest substring which is also a palindrome. Let "bananas" be a string, then the substring "anana" is the longest substring that is palindrome.

3.   String search / matching problem

Given a string S1 of size n and a string S2 of size m, where m < n, find the first or all the occurrences of string S2 in S1.  There are many algorithms to solve this problem in linear time. The most famous being Kunth-Morris-Pratt algorithm.

4. Strings  Anagram

Given two strings S1 and S2, find whether they are Anagram.

A string S1 is an Anagram of String S2 if S1 is formed by rearranging the letters of S2.

5. Reverse a string in place, e.g., "I LIKE IPHONE" -> "ENOHPI EKIL I".

6. Reverse characters of each word of string, e.g.,  "I LIKE IPHONE" -> "I EKIL ENOHPI".

7. Reverse a string such that the position of the words are reversed but the characters of the words are not reversed, e.g., "I LIKE IPHONE" -> "IPHONE LIKE I".

8. Find all the palindromes in a given string

Defintions, Data Structures, and Algorithms used for solving above problems

1.  Defining Substring, Subsequence, Prefix, and Suffix
2.  Defining Palindrome
3.  Difference between Substring and Subsequence
4.  Generalized Suffix Tree
5.  Dynamic Programming (DP)
      5.1   DP Practice Problems
      5.2   Tutorial on DP
      5.3   MIT Lecture Video

In-Place Interleaving of Two Strings

Question

 Given a string, e.g., str=substr1substr2, interleave the substrings substr1 and substr2 in-place. 
 This can be extended to three strings or more. For three strings str = substr1substr2substr3, interleave the sub strings to generate a unified string.

 Example

For two strings:
Given str = A1 A2 A3 B1 B2 B3, interleave  substr1= A1 A2 A3 and substr2= B1 B2 B3 in-place to obtain A1 B1 A2 B2 A3 B3.

For three strings:
A1 A2 A3 b1 B2 B3 C1 C2 C3, interleave substr1 = A1 A2 A3, substr2 = B1 B2 B3, and substr3 = C1 C2 C3, interleave to get A1 B1 C1 A2 B2 C2 A3 B3 C3

Solution Idea

 

 

 

Java Code

public class SeqInterleave {

    /**

     * @param args

     */

   

    public static void main(String[] args) {

        

        /*

         * Input

         */

        String[] strIn = {"A1","A2","A3","A4","A5", "A6", "A7","B1", "B2", "B3", "B4", "B5", "B6", "B7"};

        

        

        /*

         * We assume that the elements in the array are valid

         * The size of the array is even

         * The size of each type is half of the total array length

         */

        SeqInterleave seqObj = new SeqInterleave();

        seqObj.interleave(strIn);

        seqObj.printOutput(strIn);

    }

   

   

    public void interleave(String[] strIn)

    {

        int stringHalfLen = strIn.length/2;

        

        //start swapping from A7
       // Loop 1

        for(int i = stringHalfLen-1, j = 0; i > 0 ; i--, j++)

        {

            int exStartPoint = i;

            int exEndPoint = stringHalfLen+j;

          
           // Loop2

            for(int k = exStartPoint ; k <= exEndPoint; k=k+2)

            {

                String temp = strIn[k];

                strIn[k] = strIn[k+1];

                strIn[k+1]= temp;

            }

            printOutput(strIn);

            System.out.println();

        }

        

    }

   

    public void printOutput(String[] strIn)

    {

        for(int i = 0; i < strIn.length ; i++)

            System.out.print(strIn[i]+" ");

    }

}

Input

A1 A2 A3 A4 A5 A6 A7 B1 B2 B3 B4 B5 B6 B7

 

Execution Output Sequence

A1 A2 A3 A4 A5 A6 B1 A7 B2 B3 B4 B5 B6 B7
A1 A2 A3 A4 A5 B1 A6 B2 A7 B3 B4 B5 B6 B7
A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 B5 B6 B7
A1 A2 A3 B1 A4 B2 A5 B3 A6 B4 A7 B5 B6 B7
A1 A2 B1 A3 B2 A4 B3 A5 B4 A6 B5 A7 B6 B7
A1 B1 A2 B2 A3 B3 A4 B4 A5 B5 A6 B6 A7 B7 

 

Complexity

For an array of length n, it has  O( n^2) time complexity.

Loop1 has  ((n/2)-1) iterations.

In each iteration i, we perform i swappings. In each swap, two elements of the array are used.

 

is a Binary Tree also a Binary Search Tree?

Question

Write an algorithm to verify if a Binary Tree (BT) is a Binary Search Tree (BST).

Definitions

 

 BT: A binary tree  in computer science is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right".

BST: A binary search tree (BST) (aka ordered or sorted binary tree) in computer science is a node-based binary tree data structure having following properties:^[1]

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

Solutions

 

1. An in-order traversal of the binary tree should  yield a sorted list of node keys.

2. Write a function (iterative/recursive) to verify the three basic properties of a BST
 as described above.

References

 

1. CSLibrary Stanford
    This discusses many interesting functions on binary trees and binary search trees: Lookup(), Insert(), Delete(), NoOfNodes(), MaxDepth(), MinValue(), PathSum(), Mirror(), doubleTree(), sameTree(), countTrees()


2. UCB Video Lecture on Binary Search Trees





3. UCB Video Lecture Series on Data Structures

Video Lectures on Statistical Hypothesis Testing

1. Basics of Hypothesis testing

2. Hypothesis Test 

List fo Videos on NoSQL Database MongoDB

1. Installation and Introduction to MongoDB



2. O'Reilly Webcast: Introduction to MongoDB

 

3.Introduction to MongoDB




4. Inside MongoDB







5. Will Shulman (MongoLab) Talk on MongoDB : It's Not Just About Big Data






6.  MongoDB Schema Design





7.  O'Reilly Webcast: A MongoDB Optimization Primer for Indexing






8. O' Reilly Webcast : Scaling With MongoDB





9.  O' Reilly Webcast : Sharding



10.   MangoDB Internals

11.  MongoDB and Python

12.  Introduction to Using MongoDB and Spring Data on Cloud Foundary





13.  Building Mobile Backend  with MongoDB






14. MongoDB Backups using Replica Sets

15. Scaling With MongoDB

Introduction to Predictive Analytics

Everyone is highly curios to have a glimpse at the future. A peek into the future not only provides excitement in general but also helps to in proper planning and laying out import strategies. At the minimal, future predictions give us an opportunity to be prepared for the bad times and minimize the losses.  For example,  a tool that helps a human resource manager to predict the employees who are at the risk of seeking voluntary termination from the organization is immensely helpful. This helps the manager in taking proper actions to retain high performing employees and minimize losses by reducing operating costs of the organization.

Development of methodologies and tools to predict future are of utmost importance.  Predictive analytics is one such field of study at the junction of statistics, data mining, and machine learning that aims to provide future insights into various domains.


What is predictive analytics?

It is a process of analyzing historical and current facts to get an insight into future risks,  events, and trends.  Its goal is to generate actionable items for an end user to address future needs.  It finds its use in all the field of sciences, marketing, healthcare, insurance, telecommunications, and other domains.


Difference from the state-of-the-art Business Intelligence practices

The state-of-the-art Business intelligence methods generate static reports from the historical data. For example, given a repository of sales transactions, a BI software generates different kinds of reports, in the form of documents, visual charts or spreadsheets, based on  demographics, time,  product categories and other criteria. This helps an end user to analyze the historical data and discover the factors that led to the observed sales data.  In BI,  onus lies with the end user to discover future trends and events from the reports. On the contrary, predictive analytics automatically generates the future trends and events by analyzing the historical data.

References
1. Wikipedia Article
2. Dean Abbott Blog
3. Forbes Article
4. Predictive analytics with data mining

Products
1. Oracle Data Mining and Predictive Analytics
2. IBM's SPSS
3. SAS
4. We Predict
5. Revolutionanalytics 

Xpath (XML Path Language)

XPath, defined by the World Wide Web Consortium (W3C) ,  is a query language for finding elements, attributes, and other information from an XML document.  It is an integral part of XSLT ((Extensible Stylesheet Language Transformation).  XPath uses a tree representation of an XML document.  It uses XPath expressions to traverse the tree structure of the XML and select elements and attributes by a variety of criteria.

An XML Document

<?xml version="1.0" encoding="ISO-8859-1"?>

<School> 
   <Students>  
        <Student id="1"> 
                   <Name>John</Name> 
                   <Age>20</Age> 
        </Student> 
        <Student id="2"> 
                    <Name>Shaya</Name> 
                    <Age>20</Age> 
        </Student> 
    </Students> 
    <Teachers> 
           <Teacher id="1"> 
                 <Name>Tim</Name> 
                 <Age>40</Age> 
                 <Gender>M</Gender>
           </Teacher>
    </Teachers> 
</School>

Element: All the names within  <  /> symbol all called elements, e.g., School is an element. 
Attribute: These are properties of an element, e.g., id is an attribute of Student element.
Each element has a set of children elements or a data enclosed within it.

XPath Summary

1. Absolute path to select elements
We need to specify the complete path from the root till the element we are interested in select the node. For example, XPath expression   /School/Students/Student or School/Students/Student  selects all the Student elements.  A path starting from '/' is always an absolute path.

2. Relative path to select elements
This is used to select an element relative to the current element. For example, we can use Teachers/Teacher to select all the Teacher elements relative to Teachers element.

3. Selecting elements without specifying the full absolute or relative path.
'//' is used to perform this task. For example, we can use XPath expression '//' to select all the elements in the XML document.  We can use Students//Name to find all the Name elements in Students element. Here we do not need to specify the full path.

4. Selecting parent elements of a given element.
We can select the parent element by using  '..' . For example Students/.. will select its parent School.

5. Selecting all the descendent elements of a given element
We can select all the elements of a given element using wildcard * . For example, School/* selects all the descendent elements (Students, Student, Name, Gender, Teachers, Teacher etc.) of School. 

6. Selecting elements with predicates
XPath provides predicates, specified using square brackets [ ], for more flexible element selection. Predicates are used after the parent element.  For example,
School/Students/Student[1]  selects first Student element of Students
School/Students/Student[last()-1]  selects second last Student element of Students
School/Students/Student[position()< 2]  selects first Student element of Students

7. Selecting attributes
We can select an attribute using an XPath expression that specifies a path to the element and the attribute. For example,  School/Students/Student/@id will select id attribute of Student element and //@id will select all the id attributes. 

We can use wildcard to select all the attributes. For example, //Student[@*] will select all the Student elements which has an attribute.

8.  Concatenating multiple XPath expression
We can use bar symbol '|' to concatenate multiple XPath expressions. For example, /School/Students | /School/Teachers select both Students and Teachers  elements.

9. Xpath provides axes, functions, and operators to perform more complex selections.

References:

W3 Documentation
Wikipedia Article
W3Schools Tutorial