Monthly Archives: December 2011

C Programming Puzzle #1

What does the following program print? (The answer might also be that is doesn’t print anything due to compilation or run-time error). #include <stdio.h> int main(){     if("Hello World" == "Hello World"){        printf("Yes ","No ");     }     printf(10+"Hello World"-4); return 0; } The answer to this puzzle along with puzzle #2 can be found here.

Solution to Project Euler 6

Problem 6 has the following description: The sum of the squares of the first ten natural numbers is, 12 + 22 + … + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + … + 10)2 = 552 = 3025 Hence the difference between the […]

Implementing Huffman Coding in C

Huffman Coding (link to Wikipedia) is a compression algorithm used for loss-less data compression. Here’s the basic idea: each ASCII character is usually represented with 8 bits, but if we had a text filed composed of only the lowercase a-z letters we could represent each character with only 5 bits (i.e., 2^5 = 32, which […]

Solution to Project Euler 5

Problem 5 was relatively easier than the ones we saw so far. Here’s the description: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? […]

Integer Partition Algorithm

The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are: 5 4+1 3+2 2+2+1 2+1+1+1 1+1+1+1+1 Notice that changing the order of the summands will not create a different partition. Now how do we find the number of different […]

Book Review: Algorithms in C

Written by Robert Sedgewick, a computer science professor at Princeton University, Algorithms in C (link to Amazon) is a collection of two books (though there are more to come) covering the fundamental topics on computer science. Right now it’s divided into five parts: Fundamentals Data Structures Sorting Searching Graphs I just went through the first […]

Solution to Project Euler 4

Here’s the description for Problem 4 on Project Euler: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99. Find the largest palindrome made from the product of two 3-digit numbers. As usual the brute force approach was my first guess, […]

Knapsack Problem Dynamic Programming Algorithm

The Knapsack problem is probably one of the most interesting and most popular in computer science, especially when we talk about dynamic programming. Here’s the description: Given a set of items, each with a weight and a value, determine which items you should pick to maximize the value while keeping the overall weight smaller than […]

Solution to Project Euler 3

Problem 3 on Project Euler is another easy one. Here’s the description: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? A simple brute force approach, testing all factors of the number to see if they are prime and storing the largest […]