Use Backtracking to print all Subsets
Jan 22nd
I’m “studying” this algorithmic technique: Backtracking. This is an algorithmic approach to problem solution that I trust every good Computer Scientist already uses; but taking a good theo-practical look at it is something better.
A Backtracking Tree
I believe you can find enough informations about it online (the 2 links I provided are more than enough), so I’ll go straight to the problem.
Problem definition
Given an integer n, and the set S = { 1 ... n }, calculate (print) all the possible subsets of S. For example, for n = 1, all the possible subsets are { 1 } and { } (empty set). For n = 2, all the possible subsets are: { 1 2 } { 1 } { 2 } { }. In general, for the set made of the first n Integers, the number of possible subsets is 2n.
Approaching the problem
A way to describe a possible subset is an array of n elements, one for every integers; every element in the array will have value TRUE if the correspondent integers is part of the subset, FALSE otherwise.
Why the Backtracking then? Because the backtracking technique is designed to generate every possible “candidate solution” once. If we design the algorithm smartly, we can get the backtracking logic to work for us and generate all the possible subsets.
Are you are asking yourself: “isn’t this a bit of a stretching of the backtracking approach?”. I believe it is: the code could be made way smaller, even though it would have the same complexity. We are going to execute the backtracking, designing the algorithm so it will never stop until it tried every possible solution. No “intermediate stopping condition” then.
Money change problem: Greedy vs. Dyn.Pro.
Jan 17th
This is a classical problem of Computer Science: it’s used to study both Greedy and Dynamic Programming algorithmic techniques.
I hate having my pocket full of copper!!! -_-
Definition
Given:
- A set of
nDenominationsD[0...n-1]in ascending order, representing a Monetary Coin System - An money amount
A, as input
calculate a solution:
S[0...n-1], with0 <= S[i] <= (A/S[i])and0 < i < n-1
where:
A = Sum[i=0 -> n-1] { D[i] * S[i] }Min{ Sum[i=0 -> n-1] { S[i] } }
In other words
Find the smallest amount of coins to make the given amount. More >
Calculate abs(int) without branching
Jan 13th
For this you need someone to teach it to you: if you made it yourself, then you are a very good Comp-Sci, and you should send your CV to Google ASAP. 
Without branching O_o?
Yes, without using any “if ( a < 0 )...". To do that, you need to refresh how Two's Complement works, then come back.
What we really need to focus on is that, given a signed int A, the negative of that number is: B = ~A + 1. BUT, we are trying to calculate the Absolute Value, not the negative. So, something like:
RESULT =
(INPUT, if positive, or NEGATE_INPUT, if negative)
+
(0, if positive, or 1, if negative)
Does it makes sense to you? To me it didn’t for the first 10 minutes. More >
Swap the value of two integers without temporary storage
Jan 13th
Someone says this is an old lame trick. I think it’s simple and clever use of XOR.
How/Why does it work?
It’s built around the properties of the XOR ^ operator, who has the following properties:
A ^ B = B ^ A(commutative)A ^ 0 = AA ^ 1 = ~AA ^ A = 0
So, you can see how it get’s applied here:
#include <stdio .h>
int main(void)
{
unsigned int a, b;
// ... populate somehow "a" and "b"...
printf("a = %d - b = %d\n", a, b);
a ^= b; // store in "a" the value of "a XOR b"
b ^= a; // store in "b" the value of "a XOR b XOR b" = "a XOR 0" = "a"
a ^= b; // store in "a" the velue of "a XOR b XOR a" = "b XOR 0" = "b"
printf("a = %d - b = %d\n", a, b);
}
Neat.
Pascal’s Triangle generator
Jan 11th
What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need).
Pascal’s Triangle first 6 rows
The thing I wrote here is a generator of the n-th row of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a Triangular Matrix, and building every row based on the one above, solution is built in place.
String search in O(n + m)
Jan 8th
Searching a string inside another string is a very easy task. Given a string A and a string B, start a loop over A from left to right and, for every letter, start an internal loop to see if there is a match with the letters of B.
A ball of string
Pseudo code would look something like this:
function NaiveSearch(string s[1..n], string sub[1..m])
for i from 1 to n-m+1
for j from 1 to m
if s[i+j-1] ≠ sub[j]
jump to next iteration of outer loop
return i
return not found
Time Complexity? O(n * m), where n is the size of A and m is the size of B.
Wonna do better? Follow me. More >
Twitter
Facebook
Google
Anobii
GitHub
LinkedIn