Tag

Divide and conquer

Browsing

Binary search is a method to find the particular item in the sorted array. In each step, the algorithm divides the array equally and match the middle item. If the key match, return the index. If the key is less then middle, search left subarray. Else search right subarray.

Fibonacci number is a number that start with one or zero and next number is equal to the sum of previous two numbers. Ex F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 Sample Input and Output The first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two. Example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … source Code package com.dsacode.Algorithm.divideconquer; public class Fibonacci { public static…

A Binary tree is a tree with two nodes left node, right node and root node . The root node is a top most node in the tree. Write a program to print all the paths in binary tree using Pre-order traversal. source Code package com.dsacode.Algorithm.divideconquer; class TreeNodePrintAll { public TreeNodePrintAll left; public TreeNodePrintAll right; int data; public TreeNodePrintAll(int data) { this.left = null; this.right = null; this.data = data; } @Override public String toString() { return data + ” “; } } public class PrintAllPath { TreeNodePrintAll root; void printTree(TreeNodePrintAll node) { if (node == null) return; printTree(node.left); System.out.print(node…

Quicksort is an efficient comparison sort algorithm compare than other sorting algorithm. It can operate in place on an array, requiring small additional amounts of memory to perform sorting. Quicksort can be faster than merge sort and heap sort. Quicksort is one of the divide and conquer strategy algorithm. It requires careful selection of pivot element. Even if the array nearly sorted or sorted the quicksort takes the same complexity. If the array nearly sorted, we can choose insertion sort for better complexity. Write a program to implement the quick sort. source Code package com.dsacode.Algorithm.sorting; import java.util.Arrays; public class Quicksort…