Monthly Archives: November 2012

Program: Pascal’s Triangle

                                Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Method 1 ( O(n^3) time complexity )
Number of entries in every line is equal to line number. For example, the first line has “1″, the second line has “1 1″, the third line has “1 2 1″,.. and so on. Every entry in a line is value of a
 Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.
C(line, i)   = line! / ( (line-i)! * i! )
A simple method is to run two loops and calculate the value of Binomial Coefficient in inner loop.
// A simple O(n^3) program for Pascal’s Triangle
#include <stdio.h>
int binomialCoeff(int n, int k);
// Function to print first n lines of Pascal’s Triangle
void printPascal(int n)
{
  // Iterate through every line and print entries in it
  for (int line = 1; line < n; line++)
  {
    // Every line has number of integers equal to line number
    for (int i = 1; i <= line; i++)
      printf(“%d “, binomialCoeff(line, i));
    printf(“\n”);
  }
}
int binomialCoeff(int n, int k)
{
    int res = 1;
    if (k > n – k)
       k = n – k;
    for (int i = 0; i < k; ++i)
    {
        res *= (n – i);
        res /= (i + 1);
    }
    return res;
}
// Driver program to test above function
int main()
{
  int n = 7;
  printPascal(n);
  return 0;
}
Time complexity of this method is O(n^3). Following are optimized methods.

Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.

// A O(n^2) time and O(n^2) extra space method for Pascal’s Triangle
void printPascal(int n)
{
  int arr[n][n]; // An auxiliary array to store generated pscal triangle values
  // Iterate through every line and print integer(s) in it
  for (int line = 0; line < n; line++)
  {
    // Every line has number of integers equal to line number
    for (int i = 0; i <= line; i++)
    {
      // First and last values in every row are 1
      if (line == i || i == 0)
           arr[line][i] = 1;
      else // Other values are sum of values just above and left of above
           arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
      printf(“%d “, arr[line][i]);
    }
    printf(“\n”);
  }
}
This method can be optimized to use O(n) extra space as we need values only from previous row. So we can create an auxiliary array of size n and overwrite values. Following is another method uses only O(1) extra space.

Method 3 ( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that
 ith entry in a line number line is Binomial CoefficientC(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line-i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line – i) / i
So C(line, i) can be calculated from C(line, i-1) in O(1) time
// A O(n^2) time and O(1) extra space function for Pascal’s Triangle
void printPascal(int n)
{
  for (int line = 1; line <= n; line++)
  {
    int C = 1;  // used to represent C(line, i)
    for (int i = 1; i <= line; i++) 
    {
      printf(“%d “, C);  // The first value in a line is always 1
      C = C * (line – i) / i;  // C(line, i) = C(line, i-1) * (line – i) / i
    }
    printf(“\n”);
  }
}
So method 3 is the best method among all, but it may cause integer overflow for large values of n as it multiplies two integers to obtain values.

Program: Next higher number with same number of set bits


Given a number x, find next number with same number of 1 bits in it’s binary representation.
For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (100012).

Algorithm:
When we observe the binary sequence from 0 to 2n – 1 (n is # of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1′s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position. An example makes it more clear,
x = 156
10
x = 10011100
(2)
10011100
00011100 – right most string of 1’s in x
00000011 – right shifted pattern except left most bit ——> [A]
00010000 – isolated left most bit of right most 1’s pattern
00100000 – shiftleft-ed the isolated bit by one position ——> [B]
10000000 – left part of x, excluding right most 1’s pattern ——> [C]
10100000 – add B and C (OR operation) ——> [D]
10100011 – add A and D which is required number 163
(10)
After practicing with few examples, it easy to understand. Use the below given program for generating more sets.
Program Design:
We need to note few facts of binary numbers. The expression x & -x will isolate right most set bit in x (ensuring x will use 2′s complement form for negative numbers). If we add the result to x, right most string of 1′s in x will be reset, and the immediate ’0′ left to this pattern of 1′s will be set, which is part [B] of above explanation. For example if x = 156, x & -x will result in 00000100, adding this result to x yields 10100000 (see part D). We left with the right shifting part of pattern of 1′s (part A of above explanation).
There are different ways to achieve part A. Right shifting is essentially a division operation. What should be our divisor? Clearly, it should be multiple of 2 (avoids 0.5 error in right shifting), and it should shift the right most 1′s pattern to right extreme. The expression (x & -x) will serve the purpose of divisor. An EX-OR operation between the number X and expression which is used to reset right most bits, will isolate the rightmost 1′s pattern.
A Correction Factor:
Note that we are adding right most set bit to the bit pattern. The addition operation causes a shift in the bit positions. The weight of binary system is 2, one shift causes an increase by a factor of 2. Since the increased number (rightOnesPattern in the code) being used twice, the error propagates twice. The error needs to be corrected. A right shift by 2 positions will correct the result.
The popular name for this program is same number of one bits.
#include<iostream>
using namespace std;
typedef unsigned int uint_t;
// this function returns next higher number with same number of set bits as x.
uint_t snoob(uint_t x)
{
  uint_t rightOne;
  uint_t nextHigherOneBit;
  uint_t rightOnesPattern;
  uint_t next = 0;
  if(x)
  {
    // right most set bit
    rightOne = x & -(signed)x;
    // reset the pattern and set next higher bit
    // left part of x will be here
    nextHigherOneBit = x + rightOne;
    // nextHigherOneBit is now part [D] of the above explanation.
    // isolate the pattern
    rightOnesPattern = x ^ nextHigherOneBit;
    // right adjust pattern
    rightOnesPattern = (rightOnesPattern)/rightOne;
    // correction factor
    rightOnesPattern >>= 2;
    // rightOnesPattern is now part [A] of the above explanation.
    // integrate new pattern (Add [D] and [A])
    next = nextHigherOneBit | rightOnesPattern;
  }
  return next;
}
int main()
{
  int x = 156;
  cout<<“Next higher number with same number of set bits is “<<snoob(x);
  getchar();
  return 0;
}

Program: Lowest Common Ancestor in a Binary Search Tree

Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows:

 int FindLowestCommonAncestor(node* root, int value1, int value)
  I/P : 4 and 14
  O/P : 8
  (Here the common ancestors of 4 and 14, are {8,20}.
  Of {8,20}, the lowest one is 8).





Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it’s value is greater than both n1 and n2 then our LCA lies on left side of the node, if it’s value is smaller than both n1 and n2 then LCA lies on right side.
Implementation:
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int );
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
  /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid. For example 20, 22 in the given figure */ 
  if(root == NULL || root->data == n1 || root->data == n2)
    return -1;
   
  /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 12 and 14, recursion should
     terminate when we reach 8*/
  if((root->right != NULL) &&
    (root->right->data == n1 || root->right->data == n2))
    return root->data;
  if((root->left != NULL) &&
    (root->left->data == n1 || root->left->data == n2))
    return root->data;   
     
  if(root->data > n1 && root->data < n2)
    return root->data;
  if(root->data > n1 && root->data > n2)
    return leastCommanAncestor(root->left, n1, n2);
  if(root->data < n1 && root->data < n2)
    return leastCommanAncestor(root->right, n1, n2);
}   
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data  = data;
  node->left  = NULL;
  node->right = NULL;
  return(node);
}
/* Driver program to test mirror() */
int main()
{
  struct node *root  = newNode(2);
  root->left         = newNode(1);
  root->right        = newNode(4);
  root->right->left  = newNode(3);
  root->right->right = newNode(5);
/* Constructed binary search tree is
            2
           / \
         1   4
             / \
           3   5
*/
  printf("\n The Least Common Ancestor is \n");
  printf("%d", leastCommanAncestor(root, 3, 5));
  getchar();
  return 0;
}
Note that above function assumes that n1 is smaller than n2.
Time complexity: Time complexity is O(Logn) for a balanced BST and O(n) for a skewed BST.

Please Leave comment if you have doubts. Give ur solution thru comments.

Concat me through mail id: poratltechinfo@gmail.com

Programs: Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3
Output:  3->2->1->6->5->4->8->7->NULL.
Inputs:   1->2->3->4->5->6->7->80->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL.



Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be
 next and pointer to the previous node be prev. See this post for reversing a linked list.
2)
 head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return
 prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
    int data;
    struct node* next;
};
/* Reverses the linked list in groups of size k and returns the pointer to the new head node */
struct node *reverse (struct node *head, int k)
{
    struct node* current = head;
    struct node* next;
    struct node* prev = NULL;
    int count = 0;  
     
    /*reverse first k nodes of the linked list */
    while (current != NULL && count < k)
    {
       next  = current->next;
       current->next = prev;
       prev = current;
       current = next;
       count++;
    }
     
    /* next is now a pointer to (k+1)th node
       Recursively call for the list starting from current.
       And make rest of the list as next of first node */
    if(next !=  NULL)
    {  head->next = reverse(next, k); }
    /* prev is new head of the input list */
    return prev;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
    /* put in the data  */
    new_node->data  = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);   
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
/* Function to print linked list */
void printList(struct node *node)
{
    while(node != NULL)
    {
        printf(“%d  “, node->data);
        node = node->next;
    }
}   
/* Drier program to test above function*/
int main(void)
{
    /* Start with the empty list */
    struct node* head = NULL;
  
     /* Created Linked list is 1->2->3->4->5->6->7->8 */
     push(&head, 8);
     push(&head, 7);
     push(&head, 6);
     push(&head, 5);
     push(&head, 4);
     push(&head, 3);
     push(&head, 2);
     push(&head, 1);          
     printf(“\n Given linked list \n”);
     printList(head);
     head = reverse(head, 3);
     printf(“\n Reversed Linked list \n”);
     printList(head);
     getchar();
     return(0);
}
Please Leave comment if you have doubts. Give ur solution thru comments.

Concat me through mail id: poratltechinfo@gmail.com

Please Contribute and Share your experience with all by sending mail to ‘poratltechinfo@gmail.com’..Thank you.

Tech Tip: Create Bootable USB Pen Drive for Windows 7

In this post, I will show you how to load the Windows installation on to your USB flash drive and make it bootable just like the DVD.

There are Several Options:
1. Windows 7 USB-DVD Download Tool
2. Basic Option
3. Using PowerISO tool
1. Windows 7 USB-DVD Download Tool:

 Step1: Just Download this Tool using Link1 or Link2
 Step2: Install in your Desired PC,
 Step3: then follow some easy Steps
2. Basic Option:

Tools Required:
1. USB flash drive with a minimum capacity of 4 GB.

2. Windows 7 Setup DVD. 


Step 1 : Plug-in your USB flash drive.

Step 2 : Open the Command Prompt (or use PowerShell). If you are using Windows 7/Vista then open it with administrator rights*.
* Goto Start -> All Programs -> Accessories ->Windows PowerShell ->  Right-click on “Windows PowerShell” and select “Run as Administrator”.
Step 3: In the cmd, type

DISKPART
This will start window as below

Give the following command:
LIST DISK

This will show you a list of  available disks on your system. Disk 0 is usually the hard disk. In my case, Disk 1 is the USB drive (this can be a different one in your case). Now Give the command as shown below:

 SELECT DISK 1

above command, 1 is the USB drive number on my system. If you have a different number on your system, then you need to replace 1 with that number.

Step-4: Now issue the following list of commands one by one as shown below:

CLEAN
CREATE PARTITION PRIMARY
SELECT PARTITION 1
ACTIVE
FORMAT FS=NTFS QUICK
ASSIGN
EXIT

Close Power Shell and proceed to the next step.
Step 5: Insert the Windows 7/Vista installation disc and note down the “drive letter” of your DVD drive. In my case, it is “H:”.

Open the command prompt. If you are using Windows 7/Vista then open it with administrator rights*.
* Goto Start -> All Programs -> Accessories -> Right-click on “Command Prompt” and select “Run as Administrator”.

Now type the following list of commands as shown below:
H:
CD BOOT
BOOTSECT.EXE /NT60 G:(NOTE:
G: is your USB drive letter)

EXIT

Step-6: Copy the contents of your Windows 7/Vista installation disk into the USB flash drive.
Directly Copy-Paste All DVD file into Usb Stick.

Your USB stick is now ready to boot and install the OS for you.


3. Using PowerISO tool

Step1: Download the PowerIso Tool.
Step2: Make .iso file with WIN7 Os installation files.
Step3: Now, In powerISO Select Tools-> Create Bootable USB.
Step 4: Select the .iso file created.
Step5: After finishing the process, It’s done.
Don’t forget to enable the “USB Boot” option and change the “Boot priority to USB device from hard disk” in your BIOS settings.

Hardware: Panasonic TC-P55VT50

Now experience the new 3D technology in Home. Panasonic released a new TV with 3D Technology and lot more surprise bundle.

Here is the specifications:

DISPLAY
Screen Size Diagonal (inches): 55.1
Aspect Ratio: 16:9
Number of Pixels: 2,073,600 (1,920 x 1,080)
Panel: G15 Progressive Full-HD NeoPlasma
HDTV Display Capability (1080p, 1080i, 720p): Yes
Aspect Control: 4:3, Zoom, Full, Just, H-fill for TV/AV modes / 4:3, Full for PC mode

PICTURE
Shades of Gradation: 24,576 equivalent
Fast Swichig Phosphor: Yes
Filter: Infinite Black Ultra
Panel Drive: 2,500 Focused Field Drive
24p Playback (3:2)/24p Smooth Film: Yes/Yes
24p Cinematic Playback: 96 Hz/48 Hz
THX Mode: Yes (3D/2D)
ISFccc: Yes(Advanced Calibration)
Pro Setting: Yes
Smart VIERA Engine Pro
Smart VIERA Engine Pro (Dual core processor): Yes
Pure Image Creation: Yes
Vivid Color Creation: Yes
Facial Retouch: Yes
Web Smoother: Yes
1080p Pure Direct: Yes

Full HD 3D

3D Panel: Yes (Active)
3D 24p Cinema Smoother: Yes
2D-3D Conversion: Yes (with Face Detection)

AUDIO 
Number of Speakers: Front speaker (8 train speakers) x 2, Woofer (ø80 mm) x1
Audio Output: 18 W (4 + 4 + 10)
Surround Sound: AV Surround

JACKS
Integrated ATSC Tuner: Yes
HDMI Input: null / 4 (4 side)
Support Feature: Audio Return Channel (Input 2)
SD Card: yes (SDXC)
USB2.0: 3
Analog Audio Input ( for HDMI/DVI): Yes
Composite Video Input shared with Component: RCA x 1 (lower) (with Special Adapter cable (dedicated))
Audio Input (for Composite Video): RCA x 1 (lower) (with Special Adapter cable (dedicated))
Bluetooth: Yes (Keyboards/audio devices) (HID (Human Interface Device Profile) compliant keyboards are available. A2DP (Advanced Audio Distribution Profile) compliant audio devices are available.)
PC Input: D-sub 15-pin x 1 (lower) (with Special Adapter cable (dedicated))
Component Video Input (Y, PB, PR) shared with Composite: RCA x 1 (lower) (with Special Adapter cable (dedicated))
Audio Input (for Component Video): RCA x 1 (lower) (with Special Adapter cable (dedicated))
Ethernet: 1 (lower)
Digital Audio Output (Optical): 1 (lower)
FEATURES
VIERA Connect (IPTV): Yes
Web Browser: Yes
Skype while watching TV: Yes
Multitasking: Yes
Social Networking TV (Faceboook/Twitter): Yes
VIERA Remote App Support: Yes
VIERA Touch Pad Controller: Yes
Wireless LAN Adaptor: Yes (built-in)
DLNA: Yes
Media Player: null / yes (SD Card/USB) 
Support
Format: AVCHD 3D/Progressive, SD-VIDEO/MotionJPEG (Lumix)/MKV/MP4/MOV/M4v/FLV/3GPP/VRO/VOB/TS/PS, MP3/AAC/FLAC, JPEG/MPO
VIERA Link: Yes
VIERA Tools: Yes
Eco Mode: Yes
Game Mode: Yes
Pixel Orbiter (Anti-Image Retention): Yes
Trilingual Menu (English/Spanish/French): Yes
Built-In Closed Caption Decoder: Yes
Off – Timers: Yes
E-Help: Yes
GENERAL
Power Supply: AC 120 V, 60Hz
On Mode Average Power Consumption: 119 W
Receiving System: ATSC/QAM/NTSC
Dimensions with stand
Height [inches (mm)]: 32.3″ (819 mm)
Width [inches (mm)]: 50.7″ (1,286 mm)
Depth [inches (mm)]: 14.1″ (357 mm)
Dimensions W/O stand
Height [inches (mm)]: 30.4″ (771 mm)
Width [inches (mm)]: 50.7″ (1,286 mm)
Depth [inches (mm)]: Max.: 2.0″ (50 mm); General: 1.8″ (43.5 mm)
Weight with stand [lbs (kg)]: 79.4 lbs. (36.0 kg)
Weight W/O stand [lbs (kg)]: 69.5 lbs. (31.5 kg)
Carton Dimensions
Height [inches (mm)]: 34.7″ (880 mm)
Width [inches (mm)]: 59.7″ (1,516 mm)
Depth [inches (mm)]: 11.2″ (284 mm)
Gross Weight [lbs (kg)]: 94.8 lbs. (43 kg)
Operating Temperature: 32°F – 104°F (0°C – 40°C)
Safety Standard: US: UL60065/FCC Part15, CANADA: CSA C22.2/IC BETS-7
Optional Wall-mounting Bracket Model Numbers: TY-WK5P1RW
Glass & Metal Design: Yes (One Sheet of Glass)

Hardware: Android watch

Now android is in wrist. Have a look at the new arrival in market. Specification is available below.
Read it and know the technology.

Recently, I’m Watch (an Italian company) has created an Android Watch. It is very classy and compact with many specifications.

Here are the specs:

  1. i.MX233 processor (ARM926EJ-S)
  2. 64 MB RAM
  3. 4 GB Flash
  4. 1.54″ 240 by 240 pixel (220 ppi)
  5. Bluetooth 2.1 + EDR
  6. Standby 48 hours w/o Bluetooth
  7. Standby up to 30 hours w/ Bluetooth
  8. Talk time up to 2 hours
  9. 70 gr weight for Color version

Prize : 249 €