## Posts

### GREEDY ALGORITHMS

Greedy Algorithms A greedy algorithm builds up a solution by choosing the option that looks the best at every step.Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?Whenever picking which coin to use, you'd take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That's a greedy algorithm, because you're always greedily choosing the coin that covers the biggest portion of the remaining amount.Some other places where a greedy algorithm gets you the best solution:Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.Careful: sometimes a greedy algorithm doesn't give you an optimal solution:When filling a duffel bag with cakes of different weights and values

### MUTABLE VS IMMUTABLE

Mutable vs Immutable Objects A mutable object can be changed after it's created, and an immutable object can't.In Java, everything (except for strings) is mutable by default: publicclassIntegerPair{int x;int y;IntegerPair(int x,int y){this.x = x;this.y = y;}} IntegerPair p =newIntegerPair(5,10);// p.x = 5, p.y = 10 p.x =50;// p.x = 50, p.y = 10Java There's no way to make existing objects immutable. Even if an object is declared final, its fields can still be changed: publicclassIntegerPair{int x;int y;IntegerPair

### INTEGER OVERFLOW

Integer Overflow When you create an integer variable, your computer allocates a fixed number of bits for storing it. Most modern computers use 32 or 64 bits. But some numbers are so big they don't fit even in 64 bits, like sextillion (a billion trillion), which is 70 digits in binary.Sometimes we might have a number that does fit in 32 or 64 bits, but if we add to it (or multiply it by something, or do another operation) the result might not fit in the original 32 or 64 bits. This is called an integer overflow.For example, let's say we have just 2 bits to store integers with. So we can only hold the unsigned (non-negative) integers 0-3 in binary: 00 (0) 01 (1) 10 (2) 11 (3) What happens if we have 3 (11) and we try to add 1 (01)? The answer is 4 (100) but that requires 3 bits and we only have 2.What happens next depends on the language:Some languages, like Python or Ruby, will notice that the result won't fit and automatically allocate space for a larger number.In other langu…