From the monthly archives: February 2012

Java Programming Cheat Sheet 1–OO Concepts

By On February 23, 2012 · Leave a Comment

I first learned Java more than 5 years ago. But I switch between different programming languages and sometimes it’s easy to get confused. Recently I decided to refresh my Java knowledge, and this cheat sheet is a note based on my revision. It covers OO (Object Oriented) concepts, Java Syntax, and Basic I/O (Input/Output).

This [...]

Continue Reading →

A Bug Occurred at malloc

By On February 21, 2012 · Leave a Comment

0. Context

I’m developing a program that allocates memory dynamically in a loop. For every iteration of the loop, the code allocates memory using malloc and then operates on the allocated memory. The program crashes at second iteration.

1. Locate the Bug

I added a few printf statements, and found that the program crashes [...]

Continue Reading →

Video Converter Android > 100,000 Downloads

By On February 19, 2012 · 1 Comment

Video Converter Android has crossed 100,000 downloads on Feb 20, 2012. It has been in Top 100 list of Android Video&Media category for over a month.

Recently I’ve been busy with my work and study, so I didn’t have time for improving the app. It’s functioning well on most Android devices, but there’re still [...]

Continue Reading →

Binary Search and A Sample Implementation for C Standard Library bsearch Function

By On February 15, 2012 · 4 Comments

Binary search is an algorithm that finds the position of a search target in a sorted array. It has an worst case run time of logN (for 1 million items, 20 probes can do), which makes it pretty efficient in searching. This post briefly describes binary search and provides two implementations with the same interface [...]

Continue Reading →

Million Integer Problems — Part 2. Sorting a Million Integers

By On February 14, 2012 · 1 Comment

This is the second post for million integer problems. The first post is about generating million integers. You can find it here. This post deals with sorting of million integers.

It can be proven that the best that a comparison-based sorting can do has average run time of nlogn. However, given specific inputs, [...]

Continue Reading →

Million Integer Problems — Part 1. Generate 1 million integers

By On February 14, 2012 · Leave a Comment

This is a post for a set of problems that deals with millions of integers. Part 1 deals with how to generate millions of integers.

This is normally used as a program to generate inputs for testing subsequent problems. We’ll look at two problems with a slight difference.

1. Allow user to input [...]

Continue Reading →

Knuth-Morris-Pratt Algorithm (KMP)

By On February 13, 2012 · Leave a Comment

I’ve learned Knuth-Morris-Pratt Algorithm (KMP) several times. Several weeks after I learned it, if I am asked to solve the string/pattern matching problem, I only know there’s a KMP algorithm that does it efficiently at the time complexity of O(n+m). How to do it? I need to read it again. So I know I’ll need [...]

Continue Reading →

KMP (Knuth-Morris-Pratt) Algorithm Pre-computation

By On February 13, 2012 · Leave a Comment

A More General Problem

The pre-computation of KMP finds the longest suffix of a sub-pattern P[0..j] (where j is [0, m-1], m is the length of the pattern) that is also the prefix of this sub-pattern.

A more general problem is to find the longest suffix of a pattern X[0..lx-1], which is also the [...]

Continue Reading →

Simple Profiling of MD5

By On February 9, 2012 · Leave a Comment

MD5 (Message-Digest) is an algorithm commonly used as cryptographic hash function. It takes an arbitrary length of data and produces a 128-bit (16 bytes) hash value. MD5 is not recommended for secure applications any more because attack messages can be constructed to produce collision. However, without intentional attack, MD5 is extremely unlikely to produce a [...]

Continue Reading →
Set your Twitter account name in your settings to use the TwitterBar Section.