# Kalanand's July 2014 Log

## July 21st

### Simple hash table example

- Hash table: an array of 128 elements (key-value pairs).
Key is stored to distinguish between key-value pairs with the same hash.
- Hash function: remainder of division by 128.
- Collisions resolved using linear probing

struct Hash {
int key;
int value;
Hash(int k, int v) { key = k; value = v; }
int getKey() { return key; }
int getValue() { return value; }
};
//Hash Map class implementation
const int TABLE_SIZE = 128;
class HashMap {
private:
Hash **table;
public:
HashMap() {
table = new Hash*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; ++i) {
table[i] = NULL;
}
}
int get(int key) {
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key) {
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] == NULL) return -1;
return table[hash]->getValue();
}
void put(int key, int value) {
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key) {
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] != NULL) delete table[hash];
table[hash] = new Hash(key, value);
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; ++i) {
if (table[i] != NULL) delete table[i];
}
delete[] table;
}
};

## July 24th

### Number of distinct ways to climb stairs in 1 or 2 steps at a time is a Fibonacci sequence!!!

Let's say you are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Turns out the answer is simple but it takes a while to recognize the pattern.
Let N_{k} be the number of ways to climb k stairs taking only 1 or 2 steps.
We know that N_{1} = 1 and N_{2} = 2. Now, consider N_{k} for
k ≥ 3. The first step will be of size 1 or 2. In the first case there are N_{k−1}
ways to finish. In the second case there areN_{k−2}
ways to finish. Thus

N_{k} = N_{k−1} + N_{k−2}

This is Fibonacci sequence!

### Generalization

Now, let's say you can climb up 1, 2, or 3 stairs at a time.
Let's let N_{k} denote the number of ways to climb k stairs in this manner.
Notice that for k ≥ 4 there are 3 "moves" one can do for your first step:
you can climb 1, 2, or 3 stairs. If you climb 1 stair then there are N_{k−1}
ways to finish; if you climb 2 stairs there are N_{k−2}
ways to finish; and if you climb 3 stairs there are N_{k−3}
ways to finish. Thus

N_{k} = N_{k−1} + N_{k−2} + N_{k−3}

## Go to June's log

Last modified: Thu Jul 24 16:59:52 CDT 2014