# Fundamentals of Algorithms and Data Structures

For additional examples and discussion, read Chapter 3 in Competitive Programming 3 by Steven Halim

## Data Structures

I'm not going to spend much time talking about data structures because I assume that you're already familiar with most of them and how they work.

1. Do you need to keep an order between your elements? If yes, use a normal array or list.
2. Do you need key/value pair associations? If yes, use a dictionary.
3. Do you need fast access to the element with highest or lowest value? If yes, use a priority queue.
4. Otherwise, use a set.

Seriously, set is a super-awesome data structure. It has O(1) insert, delete, and search. In most cases when you would normally be using a list, you should consider whether or not you need to maintain order between your elements; if the answer to that question is "no", then you should consider switching to a set.

Note that you can use an iterate over both lists and sets in both Python and Java using either a for..in loop or your favorite functional construct.

## Algorithms

Last week, we discussed simple algorithms appropriate for technical interviews. This week, we will start looking at more advanced algorithms for more advanced problems.

### Binary Search

Binary Search is a special case of Divide and Conquer in which you recursively explore one half of a solution space but not the other half. You can use a binary search method whenever the problem has:

1. An upper and lower bound on the correct answer.
2. A reasonably efficient (linear-time) method to test if a given solution is correct, and also if it is less than or greater than the correct answer.

The key to binary search is to use trial answers to narrow the search space until we've homed in on the correct answer.

### Greedy

Greedy is a class of algorithms you can use when:

1. Exhibits optimal substructure: can be broken into smaller subproblems that can be solved independently.
2. Has a greedy property: locally optimal choices are also globally optimal.

In general, if a greedy method works, it's usually fast. Unfortunately, proving that a greedy method works is not always easy, and you have to test it on a wide variety of test cases.

### Dynamic Programming

You can use a dynamic programming method whenever the problem has:

1. Optimal substructure
2. Overlapping subproblems

We can use either top-down or bottom-up DP.

Top-down DP, also known as memoization, is easy to think about and program. It usually involves nothing more than slapping a hash map "cache" on top of an existing brute-force recursive function. More often than not, it will get you an acceptable solution in a programming competition.

Bottom-up DP, which is the more pure form of DP, means thinking about your problem in terms of a chain of dependencies rather than a recursion tree. It is sometimes more space efficient since we are able to discard old DP entries and we don't have as much recursion overhead.

Note that both approaches will typically have the same asymptotic time complexity for a given problem.

### D&C, Contraction

D&C and Contraction are two more classes of algorithms you learn in a class like CSE 241. Unfortunately, neither I nor Steven Halim find very many real-life cases when you use these classes of algorithms.

## Adding Memoization to a Recursive Function

Suppose you already have a recursive function, but your code is too slow. How do you add memoization?

You need to be able to define a key that uniquely identifies any particular input to the recursive function. In the coin change example (see below), this key can simply be the number of cents C at any particular state. A lot of times, your DP keys will be more complex, perhaps a pair of numbers or a bitmask.

For example, consider the Fibonacci recurrence.

``````def fib(n):
# Base Case
if n <= 2:
return 1

# Recursive Step
solution = fib(n-1) + fib(n-2)

# Return Result
return solution``````

In this case, your key can be simply n. You would add DP memoization to this function as follows.

``````def fib(n, cache=None):
# Make the cache data structure (hash table) if it doesn't exist yet
if cache is None: cache = {}

# Base Case
if n <= 2:
return 1

# Make the key that uniquely identifies the current state
key = n

# Recurse only if necessary
if key not in cache:
solution = fib(n-1, cache) + fib(n-2, cache)
cache[key] = solution

# Return Result
return cache[key]``````

In both cases, the "Base Case" section is the same. In addition, line 7 in the first example is the same as line 14 in the second example, except that we have to pass down the "cache" data structure.

This is a general formula that you can use to add DP memoization to an existing recursive function.

## Examples

### n-Queens

This is a classic problem. It is explained in detail in section 3.2.2 of Competitive Programming, and it is also problem 8.12 in Cracking the Coding Interview.

The question goes like this:

On a n-by-n chess board, in how many different ways can you arrange n queens such that no queen attacks any other queen?

We are going to solve this problem via the Brute Force and Fix strategy we learned last class. In Python, a brute force solution is simply:

``````def solve_brute(n):
res = 0
for positions in combinations(range(n*n), n):
if is_solution(positions, n):
res += 1
return res``````

See the code for is_solution down below.

This solution works and is correct, but as soon as n gets larger than 5 or 6, it times out. In particular, I get a runtime of 26.0144 seconds when n=6.

We can be a little bit smarter and recurse by filling the chess board row by row.

``````def solve_rows(n, positions=[], row=0):
# Base Case
if row == n:
if is_solution(positions, n): return 1
else: return 0

# Recursive step
res = 0
for i in range(n):  # for each cell in this row
pos = row * n + i  # compute the position index
positions.append(pos)  # add it to the solution candidate
res += solve_rows(n, positions, row+1) # recurse
positions.pop()  # reset the data structure

# Return Result
return res``````

In the code above, the "position index" just refers to a number to uniquely identify a cell on the chess board. For example, if n=8, then position indexes 0-7 would refer to the first row, 8-15 to the second row, and so on.

This gets me down to a runtime of 0.7066 seconds when n=6. However, we still have trouble solving the canonical 8x8 chess board: the above row-by-row solution takes 300.5697 when n=8.

How about if we pass along information about which columns have been occupied through the recursion tree?

``````def solve_rows_and_cols(n, positions=[], row=0, cols=set()):
# Base Case (same as before)
if row == n:
if is_solution(positions, n): return 1
else: return 0

# Recursive Step
res = 0
for i in range(n):  # for each cell in this row
pos = row * n + i  # compute the position index
col = pos % n  # compute the column index ('col = i' would work too)

# Test to see whether there is already a queen in this column.  If there
# is, "backtrack" or "prune" away this candidate solution.
if col in cols: continue

# Add the column and position to the data structures
positions.append(pos)

# Perform the recursion
res += solve_rows_and_cols(n, positions, row+1, cols)

# Reset the data structures
positions.pop()
cols.remove(col)

# Return Result
return res``````

I use a set data structure to keep track of the columns. A set in Python is backed by a hash table. It takes constant time to add, remove, or check for existence of a key in the set (and is super fast).

The above rows-and-columns solution gets us down to 0.0157 seconds on n=6 and 0.9957 seconds on n=8. However, we can still do better! Now that we have a framework set up to filter out duplicate columns, let's do the same thing but for diagonals. Note that there are two types of diagonals, sw-ne diagonals and nw-se diagonals, which I call "diag1" and "diag2".

``````def solve_best(n,
positions=[],
rows=set(),
cols=set(),
diags1=set(),
diags2=set(),
last=-1):
if len(positions) == n: return 1

res = 0
for pos in range(last+1, n*n):
row = pos // n
col = pos % n
d1 = row - col
d2 = row + col

if row in rows or col in cols or d1 in diags1 or d2 in diags2: continue

positions.append(pos)

res += solve_best(n, positions, rows, cols, diags1, diags2, pos)

positions.pop()
rows.remove(row)
cols.remove(col)
diags1.remove(d1)
diags2.remove(d2)

return res``````

It's a lot of lines of code, but most lines are short and there are really only a few things going on. This solution runs in 0.0123 seconds on n=6 and 0.6197 seconds on n=8, a modest improvement over the rows-and-columns-only solution.

n-Queens is a classic problem, and you are likely to see variations on it in programming competitions.

#### Code for is_solution

Here is my code for is_solution, which most of the above n-queens solutions depend on.

``````def is_unique(iter):
l = list(iter)
return len(l) == len(set(l))

def is_solution(positions, n):
rows_safe = is_unique(x//n for x in positions)
cols_safe = is_unique(x%n for x in positions)
diag1_safe = is_unique(x//n + x%n for x in positions)
diag2_safe = is_unique(x//n - x%n for x in positions)
return (rows_safe and cols_safe and diag1_safe and diag2_safe)``````

### Coin Change

This is another classic problem. It is explained in detail in section 3.5.2 of Competitive Programming (example 5), and it is also problem 8.11 in Cracking the Coding Interview.

The question goes like this:

At a convenience store, you buy a bag of chips and need C cents in change. The clerk has infinitely many coins in k different denominations, denoted S = {s1, s2, ..., sk}. What is the fewest number of coins the clerk can give you such that you receive exactly C cents?

There is an obvious greedy solution: pick the largest coin, reduce your balance, and continue until you reach 0.

``````# Greedy Solution.
#  S: reference to the original data structure
#  C: number of cents required
def solve_greedy(S, C):
res = 0
while C > 0:
# Always pick the largest coin that's less than C
C -= max(s for s in S if s <= C)
res += 1
return res``````

It turns out that this works in some cases, but not all cases! For example, if S={1,3,4} and C=6, the greedy solution will return 3, when in fact the correct solution is 2.

In fact, we need to use a Dynamic Programming solution. We first have to think about the problem as a recurrence, and then we need to add our cache data structure.

``````# Top-down DP solution.
#  S: reference to the original data structure (one per test case)
#  C: current state, i.e., number of cents (different on each call)
#  cache: reference to the cache data structure (one per test case)
def solve_top_down(S, C, cache=None):
# Create cache
if cache is None: cache = {}

# Base Case
if C == 0: return 0

# Recursive step
key = C
if key not in cache:
cache[key] = 1 + min(solve_top_down(S, C-s, cache) for s in S if s <= C)

# Return Value
return cache[key]``````

The bottom-up solution is a little bit more clever. Both solutions run in O(mn) time, where m is the length of S and n is the amount of change you need. One big downside of the top-down algorithm is that it crashes due to stack overflow as soon as C gets larger than a few hundred cents.

``````from collections import defaultdict

# Bottom-up DP solution.
#  S: reference to the original data structure
#  C: number of cents required
def solve_bottom_up(S, C):
# Create DP table
dp = defaultdict(lambda: float('inf'), {0: 0})

# Edge case
if C == 0: return 0

# Start bubbling up
for i in range(C):
# Find all dependencies
for s in S:
# If passing through state "i" is better than the best known solution
# for state "i+s", then update the entry in the DP table
dp[i+s] = min(dp[i+s], dp[i] + 1)

# Clean up memory: this element dp[i] is no longer required since its
# dependencies have been resolved.
del dp[i]

# Return Value
return dp[C]``````

Here is an example of how you could run my code on your own inputs.

``````S = (1,5,10,25)
C = 32
print("Greedy: %d" % solve_greedy(S,C))
print("Top-Down: %d" % solve_top_down(S,C))
print("Bottom-Up: %d" % solve_bottom_up(S,C))``````