Archive

Archive for the ‘Algorithms’ Category

Apache Velocity Template


If you are looking for Code generation engine Velocity Templates from Apache is your answer.

The template concept in this helps you to generate source code – java, c, c++, .Net, .txt list can go on…

Source code generated through Apache Velocity Template. Build and Deployment of this code using Apache ANT should give you awesome power 🙂

 

Find whether LinkedList is cyclic

December 16, 2010 Leave a comment

I was browsing through and came across this algorithm some where, which checks whether linked list is cyclic or not. This is to brush up my concepts on datastructures 🙂

Start with 2 pointers at the first node of the linked list

Loop infinitely
  if fastPointer reach Null
     return 'No Cycle'
  if fastPointer moves on to slowPointer
     return 'Cycle'
  move slowPointer by one Node
  move fastPointer by two Nodes
endLoop

How many books can you store in 1 GB hard drive?

December 6, 2010 30 comments

As explained in my previous post Few rules of thumb

Let’s apply Rule #7 to this problem. As the rule says, “A character is represented by 8 bits” i.e. each character takes about 8 bits. Please note that this problem can be solved only by making few assumptions and your solution depends on the kind of assumptions you make.

Let’s solve the problem now:

  • we know 1 byte = 8 bits (Ref. table at the end of this post)
    • 1 GB (giga byte) = 1073741824 bytes (≈ 109 bytes) [read it as, 10 power 9]
    • 1 GB = 8 * 109 bits
  • Now assume on an average every word is comprised of 5 characters
  • Assume every page has about 10 lines and each line has about 20 words => 200 words per page
  • Number of characters in each page => 5*200 = 1000 characters per page
  • Assume every book has about 300 pages => 1000*300 = 300000 characters per book
  • Now that every book has about 300,000 characters. The amount of memory taken by each book is
    • 300,000 * 8 = 2400000 bits (≈24*105 bits of space)
    • The above principle states that each book takes about 24*105 bits of space
  • Now, how many bookscan be stored in 1 GB hard drive?
    • (8 * 109 )/ (24*105) ≈ 3333.33 books (It’s corrected now. Thanks to the comments)

Answer to the question is… In 1 GB hard drive you can store about 3334 books with the kind of assumptions we made!

We used following conversions to solve the above problem:

  • 1 Byte = 8 Bit
  • 1 Kilobyte = 1024 Bytes
  • 1 Megabyte = 1048576 Bytes
  • 1 Gigabyte = 1073741824 Bytes

Few rules of thumb

December 6, 2010 Leave a comment

Hey this list is cool…

Following are some of rules of thumb that one may want to remember for solving complex problems or while estimating time and space complexities (in computer terms) of certain scenarios

  1. Light travels one foot in a nanosecond (one billionth of a second).
  2. Approximately  π(≈ 3.15) hundredths of a second is a nanoyear (one billionth of a year).
  3. It takes between 1 and 10 nanoseconds (ns) to store a value in Java. Basic math operations take a similar length of time.
  4. An array assignment is approximately twice as slow as a regular assignment.
  5. A Vector assignment is approximately 50 times slower than a regular assignment.
  6. Modern computers execute 1 billion instructions per second.
  7. A character is represented by 8 bits (approximately 10).
  8. An Ethernet network can transmit at 100 million bits per second (expected throughput is nearer 10 million bits).
  9. Fewer than 100 words made up 50 percent of Shakespeare’s writing; they have an average length of π. A core of 3000 words makes up 90 percent of his vocabulary; they have an average of 5.5 letters.

I got this list from Data Structures for Principled Programmer. With the help of Rule # 7 let’s try solving a problem in my next post… 🙂

Categories: Algorithms, General

Optimize your program to run faster

December 6, 2010 1 comment

We all knew that the fewer the instructions in a program, the faster the program executes! When any program is executed, the kind of data structures they utilize and the kind of algorithm utilized decides the fate of fastness and memory space used by the program. An efficient programmer is the one who keeps these two things in mind while programming.

It happened to me many times, when ever I go to my older code I keep getting new ideas and happen to remove lot of obsolete statements or optimize the program instructions to achieve the same end result. This optimization helped me many a times to improve the overall performance of the program. On the other hand, it gets really difficult after a limit of extent to improve an individual program. This limit is some times called as Information Theoretic Limit.

According to it, given the approach of the algorithm and the design of a data structure, no improvement can be made to the program to make it run faster!

What ‘am trying to convey here is that Optimization of the code is the most important factor to make programs run quickly.

Note: comments are never considered an instruction by the compiler, hence removing it or retaining it is not going to make programs faster!