Huffman Coding

                  Huffman Coding is an entropy encoding algorithm used for lossless data compression.Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code,that expresses the most common source symbols using shorter strings of bits than are used for less common source symbols.Huffman coding is equivalent to simple binary block encoding.

Compression

          

             The technique works by creating a binary tree of nodes. These can be stored in a regular array, the size of which depends on the number of symbols.

A node can be either a leaf node or an internal node. Initially, all nodes are leaf nodes, which contain the symbol itself, the weight  of the symbol and optionally, a link to a parent node which makes it easy to read the code (in reverse) starting from a leaf node. Internal nodes contain symbol weight, links to two child nodes and the optional link to a parent node. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child.

The simplest construction algorithm uses a priority queue where the node with lowest probability is given highest priority:

1. Create a leaf node for each symbol and add it to the priority queue.
2. While there is more than one node in the queue:
   1. Remove the two nodes of highest priority (lowest probability) from the queue
   2. Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
   3. Add the new node to the queue.
3. The remaining node is the root node and the tree is complete.

                 If the symbols are sorted by probability, there is a linear-time (O(n)) method to create a Huffman tree using two queues, the first one containing the initial weights (along with pointers to the associated leaves), and combined weights (along with pointers to the trees) being put in the back of the second queue. This assures that the lowest weight is always kept at the front of one of the two queues:

1. Start with as many leaves as there are symbols.
2. Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).
3. While there is more than one node in the queues:
   1. Dequeue the two nodes with the lowest weight by examining the fronts of both queues.
   2. Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
   3. Enqueue the new node into the rear of the second queue.
4. The remaining node is the root node; the tree has now been generated. 

Decompression

               
                The process of decompression is simply a matter of translating the stream of prefix codes to individual byte values, usually by traversing the Huffman tree node by node as each bit is read from the input stream.Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be reconstructed and thus reused every time, at the expense of at least some measure of compression efficiency.

huffman coding using python code can be download from here.

                                                                                                                                                                                                                                                           

lazy evaluation and the Sieve of Eratosthenes in Scala

         Lazy evaluation can be described as an expression that has a value, but that is not evaluated until it's actually needed. Some functional languages are described as Pure Lazy  to reflect the fact that all evaluation is performed on demand. Haskell is on such language. Scala has both aspects of strict evaluation and lazy evaluation, as such it couldn't be referred to as 'pure' in either sense.

          By means of the simplest example to illustrate Lazy evaluation, consider the following interaction with the Scala :

scala> lazy val a = b + 1; lazy val b = 1;
a: Int = <lazy>
b: Int = <lazy>
scala> a
res9: Int = 2
scala> b
res10: Int = 1

        This illustrates lazy evaluation, without defining the 'vals' as lazy the statement lazy val a = b + 1; lazy val b = 1; as val a = b + 1; val b = 1; couldn't be evaluated because b would be undefined when evaluating a!.

        The examples are based on the Sieve of Eratosthenes. Eratosthenes was an ancient Greek Mathematician from 276 BC – c. 195 BC. The Sieve of Eratosthenes is a ancient algorithm for finding prime numbers from 2 .. n. Stated simply, this algorithm can be expressed as :

• Create a list of all the numbers from 2 .. n.
• Starting at p = 2
• Strike out all multiples of p up until n from the list
• Let p now be the first (lowest) number that has not been struck-off the list
• Repeat the last two steps until p^2 > n
• All remaining numbers not struck from the list are prime

        The following Scala code shows  the way to implement the Sieve using Scala Lazy streams.

 

object Primes1 {
    def primes : Stream[Int] = {
        var is = Stream from 2
        def sieve(numbers: Stream[Int]): Stream[Int] = {
           Stream.cons(
           numbers.head,
           sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
 }
 sieve(is)
}
def main(args : Array[String]) = {
    primes take 100 foreach println
}
}
object Primes2 {
    def primes = {
       def sieve(is: Stream[Int]): Stream[Int] = {
           val h = is.head
           Stream.cons(h, sieve(is filter (_ % h > 0)))
 }
 sieve(Stream.from(2))
}
def main(args: Array[String]) {
    println(primes take 100 toList)
}
}

Scala - Pattern Matching

                Pattern matching is the most widely used feature of Scala.Scala provides great support for pattern matching for processing the messages. A pattern match includes a sequence of alternatives, each starting with the keyword case. Each alternative includes a pattern and one or more expressions, which will be evaluated if the pattern matches.An arrow symbol => separates the pattern from the expressions.

object Test {

       def main(args: Array[String]) {

              println(matchTest(3))

                 }

       def matchTest(x: Int): String = x match {

             case 1 => "one"

             case 2 => "two"

             case _ => "many"

             }

      }

             The block with the case statements defines a function which maps integers to strings. The match keyword provides a convenient way of applying a function (like the pattern matching function above) to an object. Following is an example which matches a value against patterns of different types:

object Test {

        def main(args: Array[String]) {

                println(matchTest("two"))

                println(matchTest("test"))

                println(matchTest(1))

               }

        def matchTest(x: Any): Any = x match {

                case 1 => "one"

                case "two" => 2

                case y: Int => "scala.Int"

                case _ => "many"

               }

       }

                   The first case matches if x refers to the integer value 1. The second case matches if x is equal to the string"two". The third case consists of a typed pattern; it matches against any integer and binds the selector value x to the variable y of type integer. Following is another form of writing same match...case expressions with the help of braces {...}:

object Test {

        def main(args: Array[String]) {

                println(matchTest("two"))

                println(matchTest("test"))

                println(matchTest(1))

                  }

       def matchTest(x: Any){

              x match {

              case 1 => "one"

              case "two" => 2

              case y: Int => "scala.Int"

              case _ => "many"

                    }

              }

       }

Memory management in Android

                 Android devices are usually battery-powered and it is designed to manage memory (RAM) to keep power consumption at a minimum.When an Android application is no longer in use, the system will automatically suspend it in memory - while the application is still technically "open," suspended applications consume no resources (e.g. battery power or processing power) and sit idly in the background until needed again.

                    This has the dual benefit of increasing the general responsiveness of the device, since applications don't need to be closed and reopened from scratch each time, but also ensuring background applications don't waste power needlessly.

                  
                   Android manages the applications stored in memory automatically: when memory is low, the system will begin killing applications and processes that have been inactive for a while, in reverse order since they were last used.. This process is designed to be invisible to the user, such that users do not need to manage memory or the killing of applications themselves.

             Confusion over Android memory management has resulted in third-party task killers becoming popular on the Google play store, where users mistakenly believe that they are required to manage applications and RAM themselves, similar to on a desktop operating system such as Windows.Third-party Android task killers are generally regarded as doing more harm than good.

Emergency Medical Support System in Android

                      Emergency Medical Support System is a system to manage emergency health problems and critical conditions of patients.This medical application in Android phones is a very useful and life saving utility.This system stores the medical conditions of the user and the contacts of the doctors and hospitals he had. The system provides single touch access to contact the persons and organisations,It provides Medical data and contacts for first responders and hospital staff to use in case of an emergency.The online website is used for store the database.The GPS service is used for locate the place and based on this location the list of nearest hospitals is retrieve from the online data base.EMSS provides the facilities given below

• A list of people to call during emergency
• Insurance information store and retrieve immediately 
• Doctor's name,number,etc are store and call during emergency
• Medical conditions store and retrieve immediately
• Any special instructions for first responder
• Details of nearby hospitals can be accessed by GPS
• Call to the nearby hospitals 
• Ambulance calling 
• Sms service

                 Any special instructions or other information you wish to provide can be given.The use of gps service enhances the scope of this system.The system is implemented in java language along with tools like eclipse and android sdk.

Scala - Exception Handling

       Scala's exceptions works like exceptions in many other languages like Java. Instead of returning a value in the normal way, a method can terminate by throwing an exception. However, Scala doesn't actually have checked exceptions.

       To handle exceptions use a try{...}catch{...} block like in Java except that the catch block uses matching to identify and handle the exceptions.

Throwing exceptions:

 

       Throwing an exception looks the same as in Java.create an exception object and then throw it with the throw keyword:

             throw new IllegalArgumentException

Catching exceptions:

 

     Scala allows to try/catch any exception in a single block and then perform pattern matching against it using case blocks as shown below:

import java.io.FileReader

import java.io.FileNotFoundException

import java.io.IOException

object Test {

def main(args: Array[String]) {

try {

val f = new FileReader("input.txt")

} catch {

case ex: FileNotFoundException =>>{

println("Missing file exception")

}

case ex: IOException => {

println("IO Exception")

}

}

}

}

The behavior of this try-catch expression is the same as in other languages with exceptions. The body is executed, and if it throws an exception, each catch clause is tried in turn

Scala - Traits

                A trait encapsulates method and field definitions, which can then be reused by mixing them into classes.Unlike class inheritance, in which each class must inherit from just one superclass, a class can mix in any number of traits.

               Traits are used to define object types by specifying the signature of the supported methods. Scala also allows traits to be partially implemented but traits may not have constructor parameters.

A trait definition looks just like a class definition except that it uses the keyword trait as follows:

trait Equal {

        def isEqual(x: Any): Boolean

        def isNotEqual(x: Any): Boolean = !isEqual(x) }

              This trait consists of two methods isEqual and isNotEqual.Here we have not given any implementation for isEqual where as another method has its implementation. Child classes extending a trait can give implementation for the un-implemented methods. So a trait is very similar to what we have abstract classes in Java. Below is a complete example to show the concept of traits:

trait Equal {

         def isEqual(x: Any): Boolean

         def isNotEqual(x: Any): Boolean = !isEqual(x) }

class Point(xc: Int, yc: Int) extends Equal {

          var x: Int = xc

          var y: Int = yc

          def isEqual(obj: Any) =

                obj.isInstanceOf[Point] &&

                obj.asInstanceOf[Point].x == x }

object Test {

        def main(args: Array[String]) {

                val p1 = new Point(2, 3)

                val p2 = new Point(2, 4)

                val p3 = new Point(3, 3)

                println(p1.isNotEqual(p2))

                println(p1.isNotEqual(p3))

                println(p1.isNotEqual(2))

                     }

            }

When to use traits?

• If the behavior will not be reused, then make it a concrete class. It is not reusable behavior after all.
• If it might be reused in multiple, unrelated classes, make it a trait. Only traits can be mixed into different parts of the class hierarchy.
• If you want to inherit from it in Java code, use an abstract class.
• If you plan to distribute it in compiled form, and you expect outside groups to write classes inheriting from it, you might lean towards using an abstract class.
• If efficiency is very important, lean towards using a class.