Number Of Possible Triangles In An Array

We have "n" sticks with us. The length of each stick is known to us. We need to find the number the triangles that can possibly be made from these sticks. The condition for making a triangle is that the sum of any two sides of the triangle should be greater than the third side. i.e. if a, b, c form a triangle, then :
1) a+b>c
2) b+c>a
3) a+c>b

INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".

OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.

BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have ⁿC₃ = ϴ(n³) comparisons. Following is the brute force approach:

Algorithm bruteForce(int[n] a)

1. For (i = 0 upto n-3)
2.      For(j = i+1 upto n-2)
3.           For(k = j+1 upto n-1)
4.                  if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5.                        count++

A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then  (a, b, c) can form a triangle.

This manipulation is illustrated as follows : 
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.

The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.

Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n³. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.

Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).

Implementation Of Quick Sort

We have observed that although the logic behind quick sort is quite simple and straight-forward, people do find it a bit difficult to implement. So we have implemented this very useful and efficient (O(n*log₂n)) sort in java. It has been tested for all cases, yet if you find any flaws in it, please leave a comment.

The logic behind this quick sort implementation is picked up from CLRS 3rd edition. 
 

Longest Palindrome In The String

INPUT :
A string of length n.

OUTPUT :
A palindromic string which is the longest sub-string of the inputted string. Thus the output string can have a maximum length of 'n'

THE BRUTE FORCE METHOD :
Since we are looking for a sub-string, the brute force method would suggest finding every possible sub-string in the string and checking if its a palindrome. The algorithm to find every sub-string accepts the inputted string 's' and its length 'n' as parameters. We assume the existence of a pseudo function isPalindrome which accepts a string as parameter and returns true if the string is a palindrome and false otherwise. We also assume subString(String, startIndex, endIndex) to be a function that returns the substring of s beginning from startIndex (including) and ending at endIndex (excluding). This is quite similar to the Java.lang.String.substring(int beginIndex, int endIndex). The algorithm uses 3 variables : maxlen to find out the maximum length of the palindrome, templen to compare with maxlen, start and end as the begin and end indices of the palindrome respectively.

Algorithm findSubString (String s)

1. maxlen = 0 ,  templen = 0, start = 0, end = 0
2. for (int i = 0 up to n-1) 
3.      for (int j = i down to 0)
4.            for (int k = i+1 up to n)
5.                          templen = k-j+1
6.                          if ( isPalindrome(subString(s, j, k+1)) && templen > maxlen) 
7.                               maxlen = templen
8.                               start = j
9.                               end = k+1 // k+1 is because subString excludes the endIndex
10.                          end if
11.               end for
12.         end for
13. end for
14. return subString(s, start, end)

However, as we see, this approach uses 3 traversals in 3 nested for loops, taking O(n³) time. It should be noted that the time-efficiency of the function isPalindrome() is not taken into consideration as it is, anyways, less than O(n³) (shall be proved in a few moments).

THE isPalindrome() FUNCTION :
The most efficient method of determining whether a string is palindrome or no is to start with its central character and to go one character each to the left and right simultaneously checking whether the string is a palindrome. For example, for "abcba", we start at "c", which is the central character and then go one character to the left getting "b" and one character to the right getting "b" again. Thus "bcb" is a palindrome. We go on doing this till the string stops being a palindrome. This is essentially the algorithm behind isPalindrome(). Let us say that we divide every palindromic string of length, say p, into 2 kinds : when p is even and when p is odd. 

1.  when p is odd, as in "abcba", we fix 1 mid-point (here "c"), then compare every character at an "x" distance from it to the left to every character at the same distance from it to the right.
2. when p is even, like "abccba", we fix no mid-point, and begin comparing from "c" and "c" (they occupy the center positions in the string; 6/2 = 3 therefore 3rd and 4th positions are central) and then continue as above.

Thus we see, that any string can be checked for palindrome in O(n) times (1 traversal).

A BETTER APPROACH :
Note that we need to find a palindromic sub-string. Such a sub-string may begin or end at any index in the string, and not necessarily at the beginning and the end of the string. For example, for "banana", the longest palindromic sub-string is "anana" which doesn't start at the beginning of the string. So to speak, we do not know the start or the end of the sub-string and thus we cannot find the mid-point. Hence, we need to consider every character as the mid-point and begin checking for the palindromes. This will take 1 traversal of the string. A java code implementing this approach is as follows :

Do leave any comments if you find a better approach or if you have any doubts regarding the given approach. 

Courtesy : http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/