Loop vs. Recursion Recursion version: next: next element in loop-> loop end: carry + reset = return Loop version: next = cur + 1 Combination vs. Permutation vs. Phone number Problem Structure Combination: position doesn't matter + no reuse … Continue reading
Nature Combination Cnk: only output at length k Cn0+Cn1+...+Cnk+...+Cnn=2n recursion (all subsets): T(n) = 2T(n-1)+c loop (narrow scope) + recursion (on each narrow scope): T(n) = T(n-1) + T(n-2) +...+T(1)+c Permutation Pnn=n!: T(n)=nT(n-1) + c: each recursion level==each position Pnk: … Continue reading
According to this article Assertions should be used as a debugging feature only. You may use them for sanity-checks that test for conditions that should always be TRUE and that indicate some programming errors if not or to check for … Continue reading
Mysterious C String Cast In our code under RHEL6, we need to query filesystem disk space, basically the same thing as df command does. There is a system call statvfs() on Linux returning all filesystem info given a path name. … Continue reading
Class A has an interface method func(). The implementation class B: public A is in a shared library. func() in the old version does not have argument. The new version changes the interface to add some argument func(a). The program … Continue reading
CONTINUOUS UPDATES Hash C++ before C++11, there is no native hash container in STL. GNU C++ has a non-standard hash implementation called hash_set C++11 adds unordered_set Use Signature: template < class Key, // unordered_set::key_type/value_type class Hash = hash<Key>, // unordered_set::hasher … Continue reading
The basic strategy: organize and store minimums of ranges for queries. How much to save in preprocessing determines query time. Trivial: time: <O(n3), O(1)>, space: O(n2). In preprocessing, trivial search miminums of all ranges. DP: time: <O(n2, O(1)>, space: O(n2). … Continue reading
In C++, nested class is a class defined inside another class. The class can be declared in public, protected or private section of its nesting class, which determines its accessibility to the outside world. A public nested class is used … Continue reading
Problem Count the number of 2’s between 0 and n Idea The number n can be broken down into a couple of ranges. The number of 2’s of numbers in each range is independent of each other. For example, 3345 … Continue reading
How Knapsack Problem is Derived ... For each kind of item, the weight equals the value: . The problem then becomes how to find the exact subset that sums to W. Decision vs. Optimization Original knapsack problems only have optimization … Continue reading