Engineering Code

Introduction to .Net Framework

noreply@blogger.com (Amit Wadhwa) — Mon, 30 Nov 2009 02:37:00 +0000

In his latest blog post about five rules for writing good code, Yan Pritzker states Rule 5 as Really learn the language and the framework. He says “No need to be a walking encyclopedia, but remember to occasionally open up that encyclopedia and read through it so that you know at least what’s out there.” So, I decided to revisit some .NET fundamentals and jot down my notes here.

The following is a short introduction to .Net framework and its components.

The .Net architecture consists of the Common Language Runtime (CLR), .Net Framework Class library, and language support components.

The Common Language Runtime (a.k.a. CLR) simplifies provides a robust and secure execution environment for .NET applications. It is also referred to as a managed environment, in which common services, such as garbage collection and security, are automatically provided.

A short description of some of the components is below:

Component	Description
Class Loader	Manages metadata, loading and layout of classes
MSIL to Native Compiler	JIT compiler for converting MSIL to Native code
Code Manager	Manages code execution
Garbage collection	--
Security Engine	Provides security based on user identity and code origin
Debugger	--
Type Checker	--
Exception Manager	Provides structured Exception handling, integrates with Windows Structured Error Handling (SEH)
Thread Support	--
COM marshaler	--
.NET Class Library support	Integrates code with the runtime that supports the .NET Framework class library

The .NET Framework class library exposes features of the runtime and provides other high-level services.

ADO.NET, the next generation of ADO technology provides improved support for disconnected programming. It also provides rich XML support in the System.Xml namespace.

ASP.NET is a programming framework built on the common language runtime that can be used on a server to build powerful Web applications

References:

1. http://skwpspace.com/2009/09/29/five-rules-for-writing-good-code/

2. http://msdn.microsoft.com/en-us/netframework/default.aspx

3. http://msdn.microsoft.com/en-us/library/aa139615.aspx

Why every other playoff system sucks

noreply@blogger.com (Amit Wadhwa) — Wed, 30 Sep 2009 04:55:00 +0000

Many times we’ve seen a underdog team defeating a top-ranked team in the 1st round of a major tournament. Most people rejoice (except the fans of the losing team) since everybody loves a fairy tale victory, The organizer’s are happy since it creates a lot of buzz and everybody’s happy that the sports is still not dead since anything can happen.

Let’s take a deeper look. Team A wins 63 games out of 80 games in the regular season plays Team B which won around 40 games. Team A loses the match and bows out of the tournament. Everybody is surprised for a moment, Team B probably loses in the next round since they again play a better team and are already happy with the results they have in hand [there was a reason it only won 40 games out of 80].

The above is a common format used across many competitions in the world (NBA, Cricket Tournaments, NCAA Tournament, Champions league). But, I think such upsets does more harm to the game than benefits it. Since the team who was definitely one of the better teams in the tournament is out due to having a bad day or couple of major players being out/suspended for the game.

Some organizers e.g. the NBA, try to avoid the above scenario by either keeping N (=3,5,7) no. of matches or sometimes giving the top ranked team a home advantage or sometimes both. Playing multiple matches definitely lowers the odds of the better team losing, however, this usually leads to some boring matches in the initial part of the tournament.

Here comes the format used by the Australian Football league, which looks like this:

Clearly, this system has numerous advantages than the knockout system usually followed. To quote Wikipedia “Under this finals system, the final eight teams are broken up into four groups of two. Each group of two earns one extra benefit over the teams beneath it. These benefits are home ground finals and the double-chance, whereby a first-week loss will not eliminate the team from the finals.”

I think atleast some tournaments should explore this format like the NCAA basketball tournament and the Cricket world cup which have the worst structure since there is only a single match between the teams and there’s no clear home-court advantage.

References:

http://en.wikipedia.org/wiki/AFL_finals_system

The Decorator Pattern

noreply@blogger.com (Amit Wadhwa) — Sat, 12 Sep 2009 22:24:00 +0000

Decorator pattern is a kind of structural design pattern which provides a way to attach new state and behavior to an object dynamically. The original object is left untouched which makes the pattern useful for changing systems. Decorators both inherit the original class and contain an instant of it.
The Decorator pattern is generally used when a object is needed with some extra functionality than an existing class but the existing class is not available for subclassing or one doesn't want to subclass for some reason (e.g. to avoid class explosion).
The following example illustrates the pattern:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DPPractice
{
    class DecoratorPattern
    {
        interface IWindow
        {
            string getDescription();
            void draw();
        }
        public class SimpleWindow : IWindow
        {
            public void draw()
            {
                //draw Simple Window
            }

            public string getDescription()
            {
                return "simple window";
            }

        }
        class VerticalScrollBarDecorator : IWindow
        {

            private IWindow decoratedWindow;

            public VerticalScrollBarDecorator(IWindow decoratedWindow)
            {
                this.decoratedWindow = decoratedWindow;
            }


            public void draw()
            {
                drawVerticalScrollBar();
                decoratedWindow.draw();
            }

            private void drawVerticalScrollBar()
            {
                // draw the vertical scrollbar
            }

            public String getDescription()
            {
                return decoratedWindow.getDescription() + ", including vertical scrollbars";
            }
        }

        static void Main(String[] args)
        {
            // create a decorated Window with horizontal and vertical scrollbars
            IWindow window = new VerticalScrollBarDecorator(new SimpleWindow());

            // print the Window's description
            Console.WriteLine(window.getDescription());
        }


    }
}

As can be seen from the example the Decorator pattern is heavily utilized in displaying windows etc. adding and excluding scroll bars easily while rendering.

Other uses of the Decorator Pattern:

1. Decorators are used in I/O API's of C#.
System.IO.Stream is decorated by
System.IO.BufferedStream
System.IO.FileStream Etc.

2. As illustrated by the example the Decorator pattern is heavily utilized in rendering windows/display objects

References:
http://en.wikipedia.org/wiki/Decorator_pattern
Design Patterns: Elements of Reusable Object-Oriented Software
C# 3.0 Design Patterns

Time Management

noreply@blogger.com (Amit Wadhwa) — Tue, 08 Sep 2009 03:29:00 +0000

This weekend I took some time out to watch the Time Management talk by Randy Pausch.Randy Pausch was an Computer Science professor at CMU. He died of cancer in July, 2008. He was a great speaker and some of his lectures has become very famous in the last few years. The most famous one being “The Last Lecture: Really Achieving Your Childhood Dreams" which is one of the most inspiring talks I have ever heard.

The talk on Time management, however, is a more pragmatic talk and talks about techniques to manage time better. Again, the underlying principle in Randy’s talk is to maximize life and fun.

Here is the talk followed with my notes. The slides are available here.

1. Pragmatic Talk
    a. Time is only commodity that matters
2. Agenda:
    a. Set goals
    b. Avoid wasting time
    c. Deal w/ boss
    d. How to delegate to others
    e. Tools
    f. Stress and Procrastination
3. Slides on website, Red stars are important
4. Americans bad at dealing with time
    a. Waste time
    b. Time and money are equitable
    c. How much is your time worth/hr
    d. Costs company twice your salary
    e. 50000/yr --> 100k cost to org
    f. Decisions: Outsource vs. DIY
    g. Manage time as money
        i. Money is not well managed
        ii. Though better
    h. Money can be earned later, Time doesn’t comes back
    i. Boss == Academic Advisor/Parents
5. One good thief [11]
    a. Talk is composed mainly from nuggets from the 2 books
        i. Time Management for Teachers
        ii. Career Track Seminar: Taking control of Your Work Day
    b. Time Famine:
        i. Problem is systematic
        ii. Long term solution required
    c. This is Life Advice
6. Overall goal is Fun
        a. Maximize time is a means so that we maximize fun
    7. Typical Office worker wastes 2 hours/day[13]
        a. Messy desk etc.
    8. Manage time well to be successful
        a. Meta skills
        b. If you want to run with ppl faster than you, optimize the skills you have
    9. Planning [16]
        a. Great if you can cross stuff from your to-do list
        b. More important to do the right things adequately than Doing (wrong) things right
        c. 80/20 rule: Very small things on ur list is gonna matter most
        d. Experience comes with time and no shortcuts.
        e. When things don’t go well, you're learning a lot and it'll be better soon.
    10. Inspiration
        a. If you can dream it, you can do it.
        b. If you refuse to dream it, you won't do it.
        c. Disneyland: 366 days
            i. Used everyone of them
    11. Planning
        a. Daily/Weekly/Semester
        b. You can always change the plan
    12. To do lists
        a. Break stuff into small steps
        b. Boss: Grow your people
        c. Eat that frog. Start with the big one first
        d. *Covey's four quadrants
            i. Go to Quad 2 after Q1 rather than Q3
        e. *Paperwork
            i. No clutter
            ii. Touch each piece of paper/email only once
                1) Inbox is not to-do list
        f. Filing system
            i. All paper goes there in alpha order
            ii. Everything should have a place
    13. Desk [ime - 28:06]
        a. Atleast 2 monitors
            i. Left:
                1) To do list
            ii. Mid:
                1) Inbox
            iii. Right:
                1) Calendar
        b. *Speaker Phone
            i. Great for waiting
            ii. Timer: Great for making people guilty on other side
            iii. Telephone Techniques
                1) Group your calls
                2) Keep calls short
                3) Use a headset
        c. *Thank you cards
                1) Very important
                2) Tangible way to tell someone how much you appreciated things
        d. Recycle Bin:
            i. Can dig stuff out
            ii. Post-its/notepad
            iii. Find a system for yourself
        e. Others
            i. Address Stamper
            ii. Kleenex
    14. Scheduling
        a. You don’t find time for important things, you make it
                1) By not wasting time on other things
                2) Learn to say no
                    a) “I’ll do it if nobody else steps forward”
                    b) “I’ll be your deep fall back," but you have to keep searching.
        b. Find your Most productive times
        c. Find your dead times
        d. *Interruptions
            i. 6-9 minutes, 4-5 minute recovery
            ii. reduce frequency and length of interruptions
            iii. No Email "ding"
        e. Cut things short
            i. Stand up, stroll to the door, complement, thank, shake hands
        f. Time journal
            i. Record your time
            ii. Update not at EOD
        g. Make up fake meeting b/w near by meetings
            i. Go to lib.
    15. Work-life balance
            i. Work fewer hours/get more done
    16. Focus on things that are important
            i. Smoking women concerned about noise of jackhammers on her unborn child
            ii. Effective vs. Efficient
    17. Procrastination
        a.   Quotes
            i. If I wait long enough it will go away
            ii. Parkinson's mail
        b. Make fake deadlines
        c. Get into a comfort zone
            i. Identify why you aren’t enthusiastic
            ii. Don't be afraid to ask people
    18. Delegation
        a. Authority with responsibility
            i. Empower ppl to get it done
            ii. Always do the ugliest/dirtiest job yourself
        b. Can't be vague
            i. Specific thing
            ii. Specific time
            iii. Specific reward/penalty for them
        c. Challenge people
            i. Delegate until people complain
            ii. Email: Get it in writing
            iii. Give objectives not procedures
            iv. Relative importance of tasks
        d. Never too early to delegate
        e. Reinforce behavior you want repeated
    19. Meetings
        a. No black-berries
        b. Agenda
        c. 1 minute minutes: an efficient way to keep track of decisions made in a meeting: who is responsible for what by when?
    20. Technology
        a. Computer's are faster but they take longer
        b. End to end
        c. It must make your life better
        d. New way of doing things
    21. Email Tips
        a. Save all of it/Searchable
        b. If you want something done, only one recipient.
        c. If you really want something done, CC their boss.
        d. Follow up after 48 hours
    22. Communication with Boss
        a. Write things down
        b. When's next meeting
        c. What's the goal
        d. Who to ask for help
        e. They want Results!
    23. General Advice
        a. No vacation if you're connected to work
        b. Kill TV
        c. Convert Money to Time esp if you have children
        d. Eat, sleep and exercise
        e. Never break a promise, but re-negotiate them if need be
        f. If you haven’t got time to do it right, you don’t have time to do it wrong
        g. Recognize that most things are pass/fail.
        h. Feedback loops: ask in confidence
    24. Reading
        a. One minute Manager
        b. 7 Habits
    25. Do it now
        a. Get a day-timer/PDA
        b. TODO list in priority order/Covey 4 quads
        c. Time Journal/Count hours of TV
        d. Revisit the talk in 30 days and ask "What have I changed?"
    26. "Time is the only thing you have and one day you may find that you have less than you imagined".

Since the formatting above is not great, Here are the notes in a one note format:

http://cid-c10db90c8a3e3ef0.skydrive.live.com/self.aspx/.Public/Time%20Management.one

References:

http://en.wikipedia.org/wiki/Randy_Pausch
http://www.cs.virginia.edu/~robins/Randy/RandyPauschTimeManagement2007.pdf
http://www.cs.virginia.edu/~robins/Randy/

Josephus Problem

noreply@blogger.com (Amit Wadhwa) — Thu, 27 Aug 2009 00:26:00 +0000

The Josephus problem is a problem often discussed and seen in CS literature. I got introduced to the problem when I initially started programming and knowing nothing about linked lists and/or recursion had a really hard time solving it.

The problem is stated as:
There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The easiest and most logical way to solve the problem is to simply simulate it using a circular link list.

N is no. of people, M as the count.

struct node {  
	int item; 
	node* next; 
};


int simple_simulation(int N, int M)
{ 
  int i;
  node *t=new node();
  node *x=t;
  t->item = 1; t->next = t;

  //Construct the list 
  for (i = 2; i <= N; i++)
  {
    x = (x->next = new node ());
    x->item = i; 
    x->next = t;
  }

  //Find the survivor
  while (x != x->next)
  {
    for (i = 1; i < M; i++) 
      x = x->next;
    x->next = x->next->next; N--;
  }
  return x->item;
}

A better way to solve the problem is through recursion. Its easy to find who is killed first, (Hint: it’s the Mth guy from the start) after that we are left with N-1 total people and the count starts from the new guy who was at M+1th position earlier. Going on like this gives us a simple recursive function:

int formula (int N, int M) 
{ 
if (N == 1)
	return 0; 
return (formula (N-1, M) + M) % N; 
}

References:

http://en.wikipedia.org/wiki/Josephus_problem

Climb the Pyramid

noreply@blogger.com (Amit Wadhwa) — Wed, 12 Aug 2009 19:34:00 +0000

Cal Newport describes the pyramid strategy to evaluate one’s progress.

http://calnewport.com/blog/2009/06/03/the-pyramid-method-a-simple-strategy-for-becoming-exceptionally-good/

From the blog:

[quote]

I call this general technique the Pyramid Method. I claim that it’s a powerful approach for anyone looking to transform an interest or natural talent into an expertise that cannot be ignored. Regardless of the pursuit in question, if you want to take it someplace serious, follow Chris’s example. This means:

Pick a single relevant venue to join at the entry level and work to increase your standing.
Make sure the venue offers clear metrics on your progress; use these metrics to guide your efforts to get better.
Forget all the other bullshit advice and mini-strategies people offer for getting ahead in your pursuit. If you can’t master this one venue, then you don’t yet deserve the world’s respect.
Put your head down, and get it done.

[/quote]

The strategy can work for many skills music, sports and coding. But choosing the proper venue is critical. IMO, apart from the above properties mentioned by Chris, The venue should have some other properties. I would talk about them from a coder’s perspective.

1. Have a low entry barrier: So that you can start early from a entry-level. So, when you only know the syntax and basic constructs of a high level language (C++, Java, C#)

2. A high competition/quality: So, you don’t “win” the venue too soon. So, you are actively engaged when you can solve non-trivial problems in your arena also. This also ensures that good coders will keep coming to your venue rather than taking off someplace else.

3. Can cater to more than 1 skill: I find this important to be a successful programmer you have to do more than code! This can involve making system architecture, understanding existing codebases, soft skills like communication.

One of the venues I know is Topcoder.com as it offers all what Chris has outlined in his article and what I have outlined here in this post.

Now, I just have to go and follow the all important Step 4 from Chris’s post.

Largest Element in the Stack

noreply@blogger.com (Amit Wadhwa) — Mon, 18 May 2009 09:18:00 +0000

Problem: Given a stack you have to insert a stream of numbers in it and you have to keep track of the highest element at any point in the stack

In general, the solution will require traversing through the entire stack hence taking O(n) time. However, given the option of using another data-structure this can be done using minimal extra memory using another "Stack" !.

The basic idea is when pushing an element in the original, check if the the "highest_elem_stack" is empty or if its top element is less than or equal to the element being pushed, if yes push this element on both stacks.

While popping check if the popped element is equal to the top element of the "highest_elem_stack". If yes pop both stacks.

The highest element in the original stack would always be equal to the top element in the "highest_elem_stack"

3 sum problem

noreply@blogger.com (Amit Wadhwa) — Tue, 09 Dec 2008 18:36:00 +0000

The problem is defined as given a array find a set of elements such that c=a+b.

Approach
1. Sort the array
2. for each element c=arr[i] in the array
3. left=0; right=i;
4. while left<right
5. check if c==arr[left]+arr[right]
6. then add c to output
7. else if c<arr[left]+arr[right] right--
8. else left++
9. end
10.end


#include <iostream>

using namespace std;

int compare (const void * a, const void * b);
void sum3(int arr[], int n);
void main(){
 int arr[]={2,3,5,1,4,9};
 
 qsort(arr,6,sizeof(int),compare);

 sum3(arr,6);

}
void sum3(int arr[], int n){
 int l,r;
 int count=0; 
 int index[6];
 int curr=0;
 for(int i=n-1;i>=0;i--)
 { 
  l=0; r=i;
  while(l<r){
   curr=arr[l] +arr[r];  
   if(arr[i] == curr){
    index[count++]=i; 
    cout<<arr[i]<<" ";
    break;
   }
   else if(arr[i] < curr)
    r--;
   else l++;
  }
 }
}
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Complexity of the above procedure is O(n^2). Apparently a better solution for the problem doesn't exist. Also, a number of problems can be reduced to the 3 sum problem and are called 3sum hard.

Implement a queue using 2 stacks

noreply@blogger.com (Amit Wadhwa) — Tue, 09 Dec 2008 10:59:00 +0000

Use 2 stacks, S and T

1. Enqueue
S.push()

2. Dequeue
if T.count==0
while (S.count>0) t.push(s.pop());

T.pop();

The operations take O(1) amortized time.

Reference
C SC 545 Exam Fall 08

Kth smallest in merge of 2 sorted arrays

noreply@blogger.com (Amit Wadhwa) — Tue, 09 Dec 2008 10:33:00 +0000

Idea:
The solution goes like this

A[1...m] B[1...n]

1. Compare A(k/2) and B(k/2)
if A(k/2) < B(k/2)

So the kth smallest can't be in A[1..k/2] and B[k/2+1 .. n]. A[1...k/2] < Kth smallest < B[k/2+1 ... n]

So we discard these elements. And now search for the k/2th smallest number in the 2 remaining arrays

if the reverse is true we do the same operation but with B and A swapped

2. if m<k

we discard B[1...k-m-1]

and look for (m+1)th (= k-(k-m-1)) smallest element in remaining arrays

const trick

noreply@blogger.com (Amit Wadhwa) — Tue, 09 Dec 2008 10:11:00 +0000

1. const int* x=5;

Declares a pointer to a constant.
So now a assignment *x=10; will fail

2. int* const x=5;
Declares a constant pointer to a variable.
so *x=10 will PASS while x=10 will fail.

3. const int * == int const *
The above 2 mean the same thing

4. const int const *x=5;

Using 3. statement 4 Declares a pointer to a constant. (same as 1)

New vs. Malloc

noreply@blogger.com (Amit Wadhwa) — Wed, 03 Dec 2008 23:47:00 +0000

New calls the "operator new(...)" method to allocate memory (like what malloc does), but memory allocation is followed by a call to the appropriate constructor. Also new is type-safe, yet malloc is not.

Static function in C

noreply@blogger.com (Amit Wadhwa) — Wed, 03 Dec 2008 23:39:00 +0000

A static function is a function with the static qualifier applied:

static void foo ( void )
{
/* Blah blah */
}
What it does is restrict visibility of the function to the translation unit in which it's declared. Functions are implicitly declared as extern by default, which means they're visible across translation units.

Reference
http://www.daniweb.com/forums/thread82504.html

Maximum Sum Sub array

noreply@blogger.com (Amit Wadhwa) — Tue, 02 Dec 2008 03:28:00 +0000

This is a interesting problem which can be solved in a variety of ways. This problem has a chunk of a chapter devoted in the Programming Pearls book by Jon Bentley.

Method 1. Brute Force O(n^2)

This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.


private static int sumbruteforce(int [] arr){
  int sum=0;
  int max=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<arr.length;i++){
   sum=0;
   for(int j=i;j<arr.length;j++){
    sum+=arr[j];
    if(sum>max){
     max=sum;
     maxi=i;
     maxj=j;
    }
   }  
  }
  System.out.println(maxi+" "+maxj);
  return max;
 }

2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.

Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.


private static int sumDivConquer(int [] arr, int l, int h){
  if(l>h)
   return 0;
  if(l==h)
   return arr[l];

  
  int m=(int) Math.floor((double)((l+h)/2));
  int max=0;
  
  max=sumDivConquer(arr, l, m);
  max=Math.max(max,sumDivConquer(arr, m+1, h));
  
  
  int L=0;
  int R=0;
  int S=0;
  for(int i=m;i>=l;i--){
   S+=arr[i];
   L=S>L? S:L;
  }
  R=S=0;
  for(int i=m+1;i<=h;i++){
   S+=arr[i];
   R=S>R? S:R;
  }
  max=Math.max(max, L+R);
  
  return max;     
 }

3. Dynamic programming O(n)

An optimized DP solution takes O(n).

The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.

The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;

for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}

Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.


private static int sumDP(int [] arr){
 int table[]=new int[arr.length];
 table[0]=arr[0];
 for(int i=1;i<arr.length;i++){
  table[i]=Math.max(arr[i], arr[i]+table[i-1]);
 }
 int max=Integer.MIN_VALUE;
 for(int i=0;i<arr.length;i++){
  if(table[i]>max)
   max=table[i];
 }
 return max;
}

A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.

The code is derived from here


private static int sumKadane(int arr[]){
    int max=Integer.MIN_VALUE;
    int a,b; a=b=0;
    int curr = 0;
    int aa = 1;
    for (int bb= 1;bb<arr.length;bb++){
        curr = curr + arr[bb];
        if (curr > max) {
            max=curr;
            a=aa;
            b=bb;             
        }
        
        if (curr < 0) {
            curr = 0;
            aa = bb + 1;
        }
    }
    System.out.println(a+" "+b);
    return max;
}

Counting Number of set bits in a number

noreply@blogger.com (Amit Wadhwa) — Mon, 01 Dec 2008 12:12:00 +0000

1. Method 1

Complexity= O(n)


int numOfOnes(int n){
  int count=0;
  while(n!=0){
   if((n & 1) == 1)
    count++;
   n=n>>>1;
  }
  return count;   
 }

Method 2:
The method works as follows:

The operation:
n=n&(n-1)
resets the last set bit of n.

So the number of time the above operation can be done before n is equal to 0 are the number of set bits in n originally.

Complexity= O(m) where m is the number of set bits in n.


int numOfOnes2(int n){
 int count=0;
 while(n!=0){
  n=n&(n-1);   
  count++;
 }
 return count;
}

Also note that if count above is 1, then number n is a power of 2.

Generating Combinations

noreply@blogger.com (Amit Wadhwa) — Mon, 01 Dec 2008 09:29:00 +0000

The algorithm for this is very similar to the algorithm for generating permutations.

Algorithm:
1. Remove Item i from elements and put in output array
2. Display Output
3. Generate combinations for rest of the array


public void combine(String str){
  int l=str.length();  
  StringBuilder out=new StringBuilder();
  char []in=str.toCharArray();
  doCombine(in,out,l,0);
 }
 private void doCombine(char[] in, StringBuilder out, int n, int start){
  for(int i=start;i<n;i++){   
   out.append(in[i]);
   System.out.println(out);
   if(i<n)
    doCombine(in, out, n, i+1);
   
   out.setLength(out.length()-1);
  }
 }

Generating Permutations

noreply@blogger.com (Amit Wadhwa) — Mon, 01 Dec 2008 08:17:00 +0000

This has been a problem I always had difficulty with. The only resort I had till now was to memorize the solution and spit it out when needed. But now, with a algorithms class behind me and a little bit more insight into the problem, I can atlast cook up the logic here.

SO, the Question is:
Given n items (numbers, chars) generate/print all possible permutation of them

Algorithm:
1. Take a item i and put it in the perm array
2. Generate Permutation for rest of the n-1 elements (Print perm array when n==0)
3. Put back Item i in elements


public class Permute {
 public void permute(String str){
  int l=str.length();
  boolean [] used=new boolean[l];
  StringBuilder out=new StringBuilder();
  char []in=str.toCharArray();
  doPermute(in,out,used, l, 0);
 }

 private void doPermute(char[] in, StringBuilder out, boolean[] used, int n,
   int level) {
  if (level==n){
   System.out.println(out.toString());
   return;
  }
  
  for(int i=0;i<n;i++){
   if(used[i]) continue;
   out.append(in[i]);
   used[i]=true;
   doPermute(in, out, used, n, level+1);
   used[i]=false;
   out.setLength(out.length()-1);
  }
  
 }
}

References:

1. Programming Interviews Exposed
2. http://www.paulgriffiths.net/program/c/perm.php

Shuffling

noreply@blogger.com (Amit Wadhwa) — Sun, 16 Nov 2008 11:13:00 +0000

Shuffling is a very interesting programming problem, Almost everybody can come up with a good algorithm using a simple rand() function, but it gets a little tricky when one has to perform a in place shuffle (i.e. w/o using any extra memory).

Knuth's Algorithm described in the Art of Computer programming, Vol 2 (which is based on Fisher Yates algorithm) is regarded as one the best known algorithm for the problem.

The description on wikipedia is a little clearer and goes like this:
1. Let A1 := 1, A2 := 2 and so on up to AN := N, and let n := N.
2. Pick a random number k between 1 and n inclusive.
3. If k ≠ n, swap the values of Ak and An.
4. Decrease n by one.
5. Repeat from step 2 until n is less than 2.


  public static void shuffle (int[] array) 
    {        
        Random rng = new Random();   // i.e., java.util.Random.
       
       // The number of items left to shuffle (loop invariant).
        int n = array.length;                
        
        while (n > 1) 
        {
            int k = rng.nextInt(n);  // 0 <= k < n.
            n--;      // n is now the last pertinent index;
            // swap array[n] with array[k] (does nothing if k == n).
            int temp = array[n];                 
            array[n] = array[k];
            array[k] = temp;
        }
    }

Alternately, instead of going n to 1 we can do a forward pass like here:


int N = array.length; 
for (int i = 0; i < N; i++) 
{ 
   int r = i + (int) (Math.random() * (N-i)); 
   int t = array[r]; 
   array[r] = array[i]; 
   array[i] = t; 
}

An alternative method is we can assign each element of the set to be shuffled a random number and the set is then sorted according to these numbers. This may be faster in practice, despite having worse asymptotic time complexity (O(n log n) vs. O(n)).

Like the Fisher-Yates shuffle, this method will also produce unbiased results if correctly implemented, and may be more tolerant of certain kinds of bias in the random numbers. However, care must be taken to ensure that the assigned random numbers are never duplicated, since sorting algorithms in general won't order elements randomly in case of a tie.

Wikipedia also defines a interesting algorithm very similar to the Knuth's algorithm called the Sattolo algorithm for generating uniformly distributed cyclic permutations. The only difference between the 2 algorithms is that in Sattolo's algorithm in step 2, the random number k is chosen from the range between 1 and n−1 (rather than between 1 and n) inclusive.

To turn the Java example above into an example of Sattolo's algorithm, simply replace rng.nextInt(n) with rng.nextInt(n-1) in the code. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.

Reference:
1. TAOCP Vol 2 Section 3.4.5 by Donald Knuth
2. http://en.wikipedia.org/wiki/Knuth_shuffle

Finding a loop in a singly linked list

noreply@blogger.com (Amit Wadhwa) — Fri, 14 Nov 2008 07:59:00 +0000

There are three "decent" solutions for it

1. Pass through the list, use a hashtable to store the addresses of the visited nodes, if 2 nodes hash to same key, there's a loop.


function boolean hasLoop(Node startNode){
  HashSet nodesSeen = new HashSet();
  Node currentNode = startNode;
  do {
    if (nodesSeen.contains(currentNode)) return true;
    nodesSeen.add(currentNode);
  } while (currentNode = currentNode.next());
  return false;
}

2. Floyd's Cycle-Finding Algorithm

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.


function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Alternately, in C


p=q=head;
do{
p=p->next->next;
q=q->next;
}while p!=q or p!=null;
if p==q
loop exists
else
no loop

To find the smallest index where the cycle starts:


// To find the smallest index where the cycle starts
// P is set from last algorithm
int index=0;
q=0;
while p!=q{
     p=p->next;
     q=q->next;
     index ++;
}
return index;

To find cycle length


// P & Q  is set from last algorithm
int len=0;
while p!=q{
     p=p->next;     
     len ++;
}
return len;

See reasoning for len, index functions at wiki

3. Brent' Algorithm


power=len=1;
q=head;
p=head->next;

while p!=q {
 if (power==len){
  p=q;
  power*=2 , len=0;
 }
 p=p->next; len++;
 if(p==NULL) return (no cycle);
}
return (cycle), len;

For finding Index


i=index=0;
p=q=head;
while(i++<len)
 p=p->next;

while p!=q {
  q=q->next;
  p=p->next;
  index++;
}
return index;

Reference:
http://ostermiller.org/find_loop_singly_linked_list.html
wiki

Delete a node in single linked list

noreply@blogger.com (Amit Wadhwa) — Thu, 13 Nov 2008 23:51:00 +0000

The solution to this is to copy the data from the next node into this node and delete the next node!. Ofcourse this wont work if the node to be deleted is the last node. Mark it as dummy in that case. If you have a Circular linked list, then this might be all the more interesting.

Two problems for the day

noreply@blogger.com (Amit Wadhwa) — Tue, 11 Nov 2008 22:16:00 +0000

Robotic Arm movement: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37

Binary Search: http://codekata.pragprog.com/2007/01/kata_two_karate.html

To be updated...

Optimizing Loops

noreply@blogger.com (Amit Wadhwa) — Mon, 10 Nov 2008 11:30:00 +0000

A few ways to optimize loops

Iterating through loops has the following structure in many cases:


for(int k=0; k<someVar.length(); k++)

Check it out, you execute the k=0 command, then you execute the comparison as well as the length method as many times as you have n variables to loop through. Finally you increment k n+1 times. This all leads to a lot of executions. To make it go faster:


int length = someVar.length();
for(int k=0; k<length; k++)

Taking the method call to length() out will increase the loop's speed slightly. However, you're still calling length from the variable table n times. So try it this way instead:


int length = someVar.length();
for(int k=length; k>0; --k)

This will iterate backwards. What that means, is that now you won't be pulling up 2 variables in the comparison. You'll only compare one variable to 0. Although, it isn't necessarily that much more beneficial to call length outside of the loop statement now since your call to length is only executed once.

Virtual Destructors

noreply@blogger.com (Amit Wadhwa) — Mon, 03 Nov 2008 20:50:00 +0000

If an object (with a non-virtual destructor) is destroyed explicitly by applying the delete operator to a base-class pointer to the object, the base-class destructor function (matching the pointer type) is called on the object.

There is a simple solution to this problem: declare a virtual base-class destructor. This makes all derived-class destructors virtual even though they don't have the same name as the base-class destructor. Now, if the object in the hierarchy is destroyed explicitly by applying the delete operator to a base-class pointer to a derived-class object, the destructor for the appropriate class is called.

Virtual constructor: Constructors cannot be virtual. Declaring a constructor as a virtual function is a syntax error.

To be completed .. (Example)

References
WikiAnswers

Amortized Analysis

noreply@blogger.com (Amit Wadhwa) — Thu, 23 Oct 2008 08:07:00 +0000

Amortized analysis refers to finding the average running time per operation over a worst-case sequence of operations.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, so the amortized time per operation is O(n) / n = O(1).

The approach is going to be to somehow assign an artificial cost to each operation in the sequence. This artificial cost is called the _amortized cost_ of an operation. The key property required of amortized cost is that the total real cost of the sequence should be bounded by the total of the amortized costs of all the operations.

There are several techniques used in amortized analysis:

* Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average cost to be T(n) / n.

* Accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.

* Potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.

References:
http://en.wikipedia.org/wiki/Amortized
http://www.eli.sdsu.edu/courses/fall96/cs660/notes/amortizedAnalysis/amortizedAnalysis.html
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s03/www/amortized-analysis.txt

GCD of 2 numbers

noreply@blogger.com (Amit Wadhwa) — Mon, 15 Sep 2008 01:14:00 +0000

The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:

gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not defined.
If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u−v)/2, v). If both are odd and u <v, then gcd(u, v) = gcd((v-u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.
Repeat steps 3–4 until u = v, or (one more step) until u = 0. In either case, the result is 2^kv, where k is the number of common factors of 2 found in step 2.

Since this definition is tail-recursive, a loop can be used to replace the recursion.


unsigned int gcd(unsigned int u, unsigned int v)
{
int shift;

/* GCD(0,x) := x */
if (u == 0 || v == 0)
  return u | v;

/* Let shift := lg K, where K is the greatest power of 2
   dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
    u >>= 1;
    v >>= 1;
}

while ((u & 1) == 0)
  u >>= 1;

/* From here on, u is always odd. */
do {
    while ((v & 1) == 0)  /* Loop X */
      v >>= 1;

    /* Now u and v are both odd, so diff(u, v) is even.
       Let u = min(u, v), v = diff(u, v)/2. */
    if (u <= v) {
             v -= u;        
    } else {                      
             int diff = u - v;
             u = v; 
             v = diff;      
    } 
    v >>= 1;
    } while (v != 0);
    return u;
}