Archive

Archive for the ‘Uncategorized’ Category

2015 in review


The WordPress.com stats helper monkeys prepared a 2015 annual report for this blog.

Here's an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 30,000 times in 2015. If it were a concert at Sydney Opera House, it would take about 11 sold-out performances for that many people to see it.

Click here to see the complete report.

Categories: Uncategorized

Project euler: Problem 15


You can find the project euler exact problem here. This problem is particularly interesting because it takes a very long time without any optimization. I started with a simple recursion but obviously not efficient, to my surprise the program did not even finish more than 10 minutes :P. The optimized version using dynamic programming hardly takes any time. Here is the code.

#include<stdio.h>

unsigned long long depth(int len)
{
   unsigned long long dep[len + 1][len + 1];
    dep[0][0] = 0;
    for (int i = 1; i <= len; i++) {
        dep[0][i] = 1;
        dep[i][0] = 1;
    }
    for (int i = 1; i <= len; i++) {
        for(int j = 1; j <= len ; j++) {
            dep[i][j] = dep[i - 1][j] + dep[i][j -1];
        }
    }
    return dep[len][len];
}

int main(void)
{
    int len = 20;
    printf("%llu\n", depth(len));
}

Answer: 137846528820

Time it takes to finish the above challenge.

real 0m0.076s
user 0m0.000s
sys 0m0.078s

Categories: Uncategorized

Quick differences between different types of ROMs


ROM (Read Only Memory)

  • As the name suggests, Once programmed cannot be reprogrammed.
  •  If the data needs to be updated throw away the programmed chip and start over with a new chip.
  • Pros:
  • less costly when produced in huge volumes
  • Robust, power efficient.
  • Cons:
  • slower

PROM (Programmable Read Only Memory)

  • This also can be programmed only once.
  • This is field programmable (ie., can be programmed anywhere).
  • Economical even when produced in small quantities.

EPROM (Electronically Programmable Read Only Memory)

  • Electronically Programmable.
  • Inexpensive per chip.
  • EPROM eraser is not selective, it erases entire chip.
  • To erase it is to be placed under the UV laser for several minutes.
  • Caution: EPROM kept under the UV laser more than required time might over erase the chip making it un-usable.

EEPROM (Electrically erasable programmable read-only memory)

  • The changes for EPROM cannot be made incrementally. For any change it erases whole chip and re-writes.
  • EEPROM can erase the targeted cells through re-writing only required cells. This way it removes this biggest drawback of EPROM.
  • EEPROM can be changed 1 Byte at a time but it is very slow.
  • Flash memory overcomes the the above limitation of slowness.
  • Flash memory erases in terms of blocks of size 512 Bytes thus improving the overall performance.

References:

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

http://computer.howstuffworks.com/rom5.htm

http://www.mycomputerscience.net/2010/06/read-only-memory1.html#

Flash and EEPROM programming from Mcirochip

Codechef: Find the largest AND operation result between any two elements of a given array


At first the problem looks very simple and can be solved easily in O(N^2).

#include <iostream>
using namespace std;
 
int main() {
 
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
		
	}
	long max = 0;
	for(int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++)
		if (max < (data[i] & data[j]) )
			max = (data[i] & data[j]);
	}
	cout<<max;
	return 0;
} 

But when it comes to huge data sets the solution for finding the maximum between every pair of elements is too much time consuming. A different approach is needed to find it quickly. Here we are reducing the complexity of the algorithm from O(N^2) to merely O(sizeof(long) * 8 * N). This is a good improvement for this algorithm.


#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
	}
	long res = 0;
	int count = 0;
	for(int i = sizeof(long) * 8; i >= 0; i--) {
		count = 0;
		for (int j = 0; j < n; j++) {
			if ((data[j] & (res | (1 << i))) == (res | (1 << i))) {
				count++;
			}
			if (count >= 2) {
				res |= (1 << i);	
				break;
			}
		}
	}
	cout<<res;
	return 0;
}

The above same code can be found here. http://ideone.com/W1LlV0

Here documents in bash


In my day to day work oftentimes I work with C, Bash scripting and Cross compiling for ARM and other interesting stuff. I feel programming is an art so as bash scripting. There are many things we come across after seeing the scripts written by highly experienced bash programmers. One of such concept was a here document.

In simple terms,

here documents can be treated as multiple line input provided to a command in a shell script.

Let us discuss here documents with simple examples:

Example 1:

wc -l << COUNT_LINES
Vasanth Raja
Chittampally
!!
COUNT_LINES

In the above example the start and end of the here document are specified with “COUNT_LINES“. Input to “wc -l” command is the three lines in between the COUNT_LINES. As expected the output to this is “3“.

Example 2:

Oftentimes I see the here documents used in conjunction with cat. This is because when we want to print set of lines to the terminal, this comes in handy. For example

cat << USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Few important points are

1. In here documents we can substitute command outputs.

In the above example $0 and `dirname $0` are replaced with the command outputs.

2. All the text in the here document will be printed exactly to the standard output. That means leading tabs, spaces are preserved exactly.

Suppose if you wish to remove the leading tabs from the here document, the same can be achieved in the following manner

cat << – USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Just use a ‘-‘ symbol just after the symbol “<<“.

In a nutshell, here documents comes very hand when you want to give multiple line input to a command. Moreover, here documents are simple to use and easy to understand.

Good articles in life hacker

2013 in review


The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 46,000 times in 2013. If it were a concert at Sydney Opera House, it would take about 17 sold-out performances for that many people to see it.

Click here to see the complete report.

Categories: Uncategorized