A Gentle Introduction To Ternary Search

Like linear search and binary search, ternary search is a searching technique that is used to determine the position of a specific value in an array. In binary search, the sorted array is divided into two parts while in ternary search, it is divided into 3 parts and then you determine in which part the element exists.

A ternary search is an example of a divide and conquer algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before you begin the search. In this search, after each iteration it neglects ⅓

part of the array and repeats the same operations on the remaining ⅔.

Use of ternary search

This concept is used in unimodal functions to determine the maximum or minimum value of that function. Unimodal functions are functions that, have a single highest value. A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining third.

binary search and ternary search comparisons in worst case?
From the first look, it seems the ternary search does less number of comparisons as it makes Log₃n recursive calls, but binary search makes Log₂n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.

   T(n) = T(n/2) + 2,  T(1) = 1

The following is recursive formula for counting comparisons in worst case of Ternary Search.

   T(n) = T(n/3) + 4, T(1) = 1

In binary search, there are 2Log₂n + 1 comparisons in worst case. In ternary search, there are 4Log₃n + 1 comparisons in worst case.

Time Complexity for Binary search = 2clog2n + O(1)
Time Complexity for Ternary search = 4clog3n + O(1)

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log₃n and Log₂n . The value of 2Log₃n can be written as (2 / Log₂3) * Log₂n . Since the value of (2 / Log₂3) is more than one, Ternary Search does more comparisons than Binary Search in worst case.

Implementation

int ternary_search(int l,int r, int x)
{
    if(r>=l)
    {
        int mid1 = l + (r-l)/3;
        int mid2 = r -  (r-l)/3;
        if(ar[mid1] == x)
            return mid1;
        if(ar[mid2] == x)
            return mid2;
        if(x<ar[mid1])
            return ternary_search(l,mid1-1,x);
        else if(x>ar[mid2])
            return ternary_search(mid2+1,r,x);
        else
            return ternary_search(mid1+1,mid2-1,x);

    }
    return -1;
}

 

Hot Topics in Computer Science

Some latest hot topics in Computer Science:

• Data Warehousing
• Internet of Things(IoT)
• Big Data
• Cloud Computing
• Semantic Web
• MANET
• Machine Learning
• Artificial Intelligence
• Data Mining
• Image Processing
• Bioinformatics
• Quantum Computing

Data Warehousing

Data Warehousing is the process of analyzing data for business purposes. Data warehouse store integrated data from multiple sources at a single place which can later be retrieved for making reports. The data warehouse in simple terms is a type of database different and kept isolated from organization’s run-time database. The data in the warehouse is historical data which is helpful in understanding business goals and make decisions for future prospects. It is a relatively new concept and have high growth in future. Data Warehouse provides Online Analytical Processing(OLAP) tools for the systematic and effective study of data in a multidimensional view. Data Warehouse finds its application in the following areas:

• Financial Sector
• Banking Sector
• Retail Services
• Consumer goods
• Manufacturing

Internet of Things(IoT)

Internet of Things(IoT) is a concept of interconnection of various devices, a vehicle to the internet. IOT make use of actuators and sensors for transferring data to and from the devices. This technology is developed for better efficiency and accuracy apart from minimizing human interaction with the devices. The example for this is the traffic lights which changes its colors depending upon the traffic. Following are the application areas of Internet of Things(IoT):

• Home Automation
• Healthcare
• Agriculture
• Transportation
• Manufacturing
• Environment

Big Data

Big Data is a term to denote the large volume of data which is complex to handle. The data may be structured or unstructured. Structured data is an organized data while unstructured data is an unorganized data. The definition of big data is termed in terms of three Vs. These vs are:

• Volume: Volume defines large volume of data from different sources
• Velocity: It refers to the speed with which the data is generated
• Variety: It refers to the varied amount of data both structured and unstructured.

 

Application areas:

• Government
• Healthcare
• Education
• Finance
• Manufacturing
• Media
• Sports

Cloud Computing

 

Cloud Computing is a comparatively new technology. It is an internet-based service that creates a shared pool of resources for consumers. There are three service models of cloud computing namely:

• Software as a Service(SaaS)
• Platform as a Service(PaaS)
• Infrastructure as a Service(IaaS)

Characteristics of cloud computing are:

• On-demand self-service
• Broad network access
• Shared pool of resources
• Scalability
• Measured service

Semantic Web

Semantic Web is also referred to as Web 3.0 and is the next big thing in the field of communication. It is standardized by World Wide Web Consortium(W3C) to promote common data formats and exchange protocols over the web. It is machine-readable information based and is built on XML technology. It is an extension to Web 2.0. In the semantic web, the information is well defined to enable better cooperation between the computers and the people. In the semantic web, the data is interlinked for better understanding. It is different from traditional data sharing technologies.

MANET

MANET stands for mobile ad hoc network. It is an infrastructure-less network with mobile devices connected wirelessly and is self-configuring. It can change locations independently and can link to other devices through a wireless connection. Following are the various types of MANETS:

• Vehicular ad hoc network(VANET)
• Smartphone ad-hoc network(SPANET)
• Internet-based mobile ad hoc network(iMANET)

various simulation tools to study the functionality and working of MANET like OPNET, NETSIM, NS3 etc.

In MANET there is no need of central hub to receive and send messages. Instead, the nodes directly send packets to each other.

MANET finds its applications in the following areas:

• Environment sensors
• Healthcare
• Vehicular ad hoc communication
• Road Safety
• Home

Machine Learning

It is also a relatively new concept in the field of computer science and is a technique of guiding computers to act in a certain way without programming. It makes use of certain complex algorithms to receive an input and predict an output for the same. There are three types of learning;

• Supervised learning
• Unsupervised learning
• Reinforcement learning

Machine Learning is closely related to statistics.

Data Mining

Data Mining is the process of identifying and establishing a relationship between large datasets for finding a solution to a problem through analysis of data. There are various tools and techniques in Data Mining which gives enterprises and organizations the ability to predict futuristic trends. Data Mining finds its application in various areas of research, statistics, genetics, and marketing. Following are the main techniques used in the process of Data Mining:

• Decision Trees
• Genetic Algorithm
• Induction method
• Artificial Neural Network
• Association
• Clustering

Advantages of Data Mining

• Data Mining helps marketing and retail enterprises to study customer behavior.
• Organizations into banking and finance business can get information about customer’s historical data and financial activities.
• Data Mining help manufacturing units to detect faults in operational parameters.
• Data Mining also helps various governmental agencies to track record of financial activities to curb on criminal activities.

Disadvantages of Data Mining

• Privacy Issues
• Security Issues
• Information extracted from data mining can be misused

Artificial Intelligence

Artificial Intelligence is the intelligence shown by machines and it deals with the study and creation of intelligent systems that can think and act like human beings. In Artificial Intelligence, intelligent agents are studied that can perceive its environment and take actions according to its surrounding environment.

Goals of Artificial Intelligence

Following are the main goals of Artificial Intelligence:

• Creation of expert systems
• Implementation of human intelligence in machines
• Problem-solving through reasoning

Application of Artificial Intelligence

Following are the main applications of Artificial Intelligence:

• Expert Systems
• Natural Language Processing
• Artificial Neural Networks
• Robotics
• Fuzzy Logic Systems

Strong AI – It is a type of artificial intelligence system with human thinking capabilities and can find a solution to an unfamiliar task.

Weak AI – It is a type of artificial intelligence system specifically designed for a particular task. Apple’s Siri is an example of Weak AI.

Turing Test is used to check whether a system is intelligent or not. Machine Learning is a part of Artificial Intelligence. Following are the types of agents in Artificial Intelligence systems:

• Model-Based Reflex Agents
• Goal-Based Agents
• Utility-Based Agents
• Simple Reflex Agents

Natural Language Processing – It is a method to communicate with the intelligent systems using human language. It is required to make intelligent systems work according to your instructions. There are two processes under Natural Language Processing – Natural Language Understanding, Natural Language Generation.

Natural Language Understanding involves creating useful representations from the natural language. Natural Language Generation involves steps like Lexical Analysis, Syntactic Analysis, Semantic Analysis, Integration and Pragmatic Analysis to generate meaningful information.

Image Processing

Image Processing is another field in Computer Science and a popular topic for a thesis in Computer Science. There are two types of image processing – Analog and Digital Image Processing. Digital Image Processing is the process of performing operations on digital images using computer-based algorithms to alter its features for enhancement or for other effects. Through Image Processing, essential information can be extracted from digital images. It is an important area of research in computer science. The techniques involved in image processing include transformation, classification, pattern recognition, filtering, image restoration and various other processes and techniques.

Main purpose of Image Processing

Following are the main purposes of image processing:

• Visualization
• Image Restoration
• Image Retrieval
• Pattern Measurement
• Image Recognition

Applications of Image Processing

Following are the main applications of Image Processing:

• UV Imaging, Gamma Ray Imaging and CT scan in medical field
• Transmission and encoding
• Robot Vision
• Color Processing
• Pattern Recognition
• Video Processing

Bioinformatics

Bioinformatics is a field that uses various computational methods and software tools to analyze the biological data. In simple words, bioinformatics is the field that uses computer programming for biological studies. This field is a combination of computer science, biology, statistics, and mathematics. It uses image and signal processing techniques to extract useful information from a large amount of data. Following are the main applications of bioinformatics:

• It helps in observing mutations in the field of genetics
• It plays an important role in text mining and organization of biological data
• It helps to study the various aspects of genes like protein expression and regulation
• Genetic data can be compared using bioinformatics which will help in understanding molecular biology
• Simulation and modeling of DNA, RNA, and proteins can be done using bioinformatics tools

Quantum Computing

Quantum Computing is a computing technique in which computers known as quantum computers use the laws of quantum mechanics for processing information. Quantum Computers are different from digital electronic computers in the sense that these computers use quantum bits known as qubits for processing. A lot of experiments are being conducted to build a powerful quantum computer. Once developed, these computers will be able to solve complex computational problems which cannot be solved by classical computers.

Quantum Computers work on quantum algorithms like Simon’s algorithm to solve problems. Quantum Computing finds its application in the following areas:

• Medicines
• Logistics
• Finance
• Artificial Intelligence

Algorithm paradigm | Introduction to Divide and conquer algorithm

Divide and conquer algorithm

Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. A typical Divide and Conquer algorithm solves a problem using following three steps.

1. Divide: Break the problem into sub-problems of same type.
2. Conquer: Recursively solve these sub-problems.
3. Combine: Combine the solution sub-problems.

 

These are methods of designing algorithms that (informally) proceed as follows:

Given an instance of the problem to be solved, split this into several smaller sub-instances (of the same problem), independently solve each of the sub-instances and then combine the sub-instance solutions so as to yield a solution for the original instance.

With the divide-and-conquer method the size of the problem instance is reduced by a factor (e.g. half the input size), while with the decrease-and-conquer method the size is reduced by a constant.

Example of divide-and-conquer algorithms:

• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)
• Cooley–Tukey Fast Fourier Transform (FFT) algorithm
• Karatsuba algorithm for fast multiplication

Examples of decrease-and-conquer algorithms:

1.  Insertion sort
2.  Topological sorting
3. Binary Tree traversals: inorder, preorder and postorder (recursion)
4.  Computing the length of the longest path in a binary tree (recursion)
5.  Computing Fibonacci numbers (recursion)
6.  Reversing a queue (recursion)
7.  Warshall’s algorithm (recursion)

 

 Advantages of Divide and Conquer

• The most recognizable benefit of the divide and conquer paradigm is that it allows us to solve difficult problem, such as the Tower of Hanoi, which is a mathematical game or puzzle. Being given a difficult problem can often be discouraging if there is no idea how to go about solving it. However, with the divide and conquer method, it reduces the degree of difficulty since it divides the problem into sub problems that are easily solvable, and usually runs faster than other algorithms would.
• It also uses memory caches effectively. When the sub problems become simple enough, they can be solved within a cache, without having to access the slower main memory.

 Disadvantages of Divide and Conquer

• One of the most common issues with this sort of algorithm is the fact that the recursion is slow, which in some cases outweighs any advantages of this divide and conquer process.
• Sometimes it can become more complicated than a basic iterative approach, especially in cases with a large n. In other words, if someone wanted to add a large amount of numbers together, if they just create a simple loop to add them together, it would turn out to be a much simpler approach than it would be to divide the numbers up into two groups, add these groups recursively, and then add the sums of the two groups together.

Example Merge sort:

Merge Sort is a Divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following algorithm for details.

mergeSort(arr[], left,  right)
If right > left
     1. Find the middle point to divide the array into two halves:  
             middle  = (left+right)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, left, middle)
     3. Call mergeSort for second half:
             Call mergeSort(arr, middle+1, right)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, left, middle, right)

 

Java implementation of merge sort is given below:

/* Java program for implement Merge Sort */
class MergeSort {

// Merges two subarrays of arr[].
// First subarray is arr[left to middle]
// Second subarray is arr[middle+1 to right]
void merge(int arr[], int left, int middle, int right) {
// Find sizes of two subarrays to be merged
int n1 = middle - left + 1;
int n2 = right - middle;

/* Create temp arrays */
int LEFT[] = new int[n1];
int RIGHT[] = new int[n2];

/*Copy data to temp arrays*/
for (int i = 0; i < n1; ++i) {
LEFT[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
RIGHT[j] = arr[middle + 1 + j];
}

/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;

// Initial index of merged subarry array
int k = left;
while (i < n1 && j < n2) {
if (LEFT[i] <= RIGHT[j]) {
arr[k] = LEFT[i];
i++;
} else {
arr[k] = RIGHT[j];
j++;
}
k++;
}

/* Copy remaining elements of LEFT[] if any */
while (i < n1) {
arr[k] = LEFT[i];
i++;
k++;
}

/* Copy remaining elements of RIGHT[] if any */
while (j < n2) {
arr[k] = RIGHT[j];
j++;
k++;
}
}

// Main function that sorts arr[l..r] using
// merge()
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int middle = (left + right) / 2;

// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);

// Merge the sorted halves
merge(arr, left, middle, right);
}
}

/* A utility function to print array of size n */
void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

// Driver method
public static void main(String args[]) {
int arr[] = {12, 19, 13, 51, 6, 7, 68};
MergeSort ob = new MergeSort();
System.out.println("Given Array");
ob.printArray(arr);

ob.mergeSort(arr, 0, arr.length - 1);

System.out.println("\nSorted array");
ob.printArray(arr);
}
}
/* This code is contributed by Sani Kamal */

 

output:

run:
Given Array
12 19 13 51 6 7 68

Sorted array
6 7 12 13 19 51 68
BUILD SUCCESSFUL (total time: 1 second)

Time Complexity:

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: No in a typical implementation

Stable: Yes

Applications of Merge Sort

1. Merge sort is useful for sorting linked lists in O(nLogn) time
2. Inversion count problem
3. Used in External Sorting

 

 

 

Algorithm paradigms (Introduction)

An algorithmic paradigm, algorithm design paradigm, algorithmic technique, or algorithmic strategy is a generic method or approach which underlies the design of a class of algorithms. In simple “High level approach to solving a class of problems”.

Steps in development of Algorithms

a) Problem definition
b) Development of a model
c) Specification of Algorithm
d) Designing an Algorithm
e) Checking the correctness of Algorithm
f) Analysis of Algorithm
g) Implementation of Algorithm
h) Program testing
i) Documentation Preparation

 

Common design paradigms

  i. Divide and conquer
ii. Dynamic programming
iii. Greedy algorithm
iv. Back Tracking
v. Brute Force

vi. Branch and Bound

Divide and conquer algorithm:

Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Dynamic Programming:

One disadvantage of using Divide-and-Conquer is that the process of recursively solving separate sub-instances can result in the same computations being performed repeatedly since identical sub-instances may arise.

The idea behind dynamic programming is to avoid this pathology by obviating the requirement to calculate the same quantity twice.

The method usually accomplishes this by maintaining a table of sub-instance results.

Dynamic Programming is a Bottom-Up Technique in which the smallest sub-instances are explicitly solved first and the results of these used to construct solutions to progressively larger sub-instances.

In contrast, Divide-and-Conquer is a Top-Down Technique which logically progresses from the initial instance down to the smallest sub-instance via intermediate sub-instances.

Greedy Algorithms:

it is “take what you can get now” strategy algorithm.

The solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far. At each step the choice must be locally optimal – this is the central point of this technique.

Examples:
Minimal spanning tree
Shortest distance in graphs
Greedy algorithm for the Knapsack problem
The coin exchange problem
Huffman trees for optimal encoding

Greedy techniques are mainly used to solve optimization problems. They do not always give the best solution.

Brute Force:

Brute force is a straightforward approach to solve a problem based on the problem’s statement and definitions of the concepts involved. It is considered as one of the easiest approach to apply and is useful for solving small – size instances of a problem.

Some examples of brute force algorithms are:
Computing an (a > 0, n a nonnegative integer) by multiplying a*a*…*a
Computing n!
Selection sort
Bubble sort
Sequential search
Exhaustive search: Traveling Salesman Problem, Knapsack problem.

Branch-and-bound:

Branch and bound is used when we can evaluate each node using the cost and utility functions. At each step we choose the best node to proceed further. Branch-and bound algorithms are implemented using a priority queue. The state-space tree is built in a breadth-first manner.

Example: the 8-puzzle problem. The cost function is the number of moves. The utility function evaluates how close is a given state of the puzzle to the goal state, e.g. counting how many tiles are not in place.