It just an assuption you make for the recursive description of the height of a binary tree. You can consider a tree composed by just a node either with 0 height or with 1 height. If you really want to think about it somehow you can think that it’s 0 if you consider the height … Read more
There exist algorithms more efficient than O(N^2) to multiply two numbers (see Karatsuba, Pollard, Schönhage–Strassen, etc.) The two problems “multiply two arbitrary N-bit numbers” and “Square an arbitrary N-bit number” have the same complexity. We have 4*x*y = (x+y)^2 – (x-y)^2 So if squaring N-bit integers takes O(f(N)) time, then the product of two arbitrary … Read more
K (Wikipedia), 15 characters: p:{x{+’:x,0}\1} Example output: p 10 (1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 … Read more
First solutions for shifting (shift is the shift distance, must not be negative, a is the operand to be shifted and contains also the result when done). The power table is used by all three shift operations. // table used for shift operations powtab = { 1, 2, 4, 8, 16, 32, 64, 128, 256, … Read more
Use the symmetric difference operator for sets (aka the XOR operator): >>> set([1,2,3]) ^ set([3,4,5]) set([1, 2, 4, 5])
The big O notation, and its relatives, the big Theta, the big Omega, the small o and the small omega are ways of saying something about how a function behaves at a limit point (for example, when approaching infinity, but also when approaching 0, etc.) without saying much else about the function. They are commonly … Read more
Much as I love Haskell, here are the reasons I would prefer SML for a class in discrete math and data structures (and most other beginners’ classes): Time and space costs of Haskell programs can be very hard to predict, even for experts. SML offers much more limited ways to blow the machine. Syntax for function … Read more
This is the function that I use for this calculation: public static int binlog( int bits ) // returns 0 for bits=0 { int log = 0; if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; } if( bits >= 256 ) { bits >>>= 8; log += … Read more