If w prefers m' over her husband, m, m' does not prefer w over his own wife, w'.

If m prefers w' over his wife, w, w' does not prefer m over her own husband, m'.

Initialize each person to be free

If f = O(g) and g = O(h) then f = O(h).

Also works with Ω and Θ.

If f = O(h) and g = O(h) then f + g = O(h).

Also works with Ω and Θ.

Use it like a stack. As soon as a man is engaged, take him out of list. Constant time since we always deal with the person in the front. If a man's wife leaves him, he is put at the top of the list, which also takes constant time.

O(k)

Next[m] keeps track of which woman man m should propose to next

Initially Next[m] = 1 for all m

ManPref is a 2D matrix of the preference lists for the men.

ManPref[m, Next[m]] returns the woman m should propose to next

Once m proposes to the woman, Next[m] is incremented regardless of what the woman's response is.

O(k)

Current is an array of length n.

Current[w] is the woman's current partner

Thus, checking if a woman is engaged will be fast

O(k)

At the beginning, create an nxn array named Ranking

Ranking[m,w] would return how highly ranked m is on w's preference list

O(k)

Because smallest element is at the root, finding the min is easy.

Symmetric Matrix

Matrix[i,j]=1 implies that there is an edge between node i and j

Θ(n^2) space

Constant time access

Identifying all edges is Θ(n^2). This kind of confused me. I thought it would only take n(n+1)/2 time because a lot of the data is repeated. Wouldn't it be O(n^2) and Θ(something else)? The big theta/tight bound concept confuses me. The book says I have to “inflate” the running time, and n(n+1)/2 does inflate to n^2, but it seems like this makes the point of the tight bound (I assume that the point of identifying the tight bound is to find a more precise measurement of efficiency) if it “inflates” the running time? Is it used to find a precise measurement of efficiency if the upper bound is really huge (let's say O(n^5)) and the lower bound is really small (let's say Ω(n))? If that is the case, what possible values could we have for the tight bound? This is confusing.

Not really a list. It's an array of lists. SO IT'S ALSMOST A MATRIX.

Array[i] is the ith node. It's a list of all the edges that node i is connected to.

There are two representations of each edge because each edge appears in two separate lists

m = number of edges

n = number of nodes

Space is 2m+n.

Identifying all edges is Θ(m + n). This tight bound makes sense because it is actually less than the amount of time it would actually take. It's also better than best case.

Let G be a graph

We don't really need a proof for this. It's very intuitive. A node needs at least one edge to join a graph. Everything else follows from this.

Pick a node

Shove everything that's immediately connected to it into the next level down

Do the same to those nodes. You now have a hierarchy. This is a rooted tree.

O(n^3).

If we look for a tighter bound, we can find it.

Bipartite means cannot have odd length cycle (because this means one edge will connect two nodes form the same side)

Local Optimizations

Informal explanation: At each iteration, add biggest coin possible that doesn't take us over our goal amount

Only works with American coins (reasons why is obvious, just pick arbitrary numbers for coin sizes and you will eventually find a system of coins that won't work)

Greedy stays ahead: Show that the greedy algorithm performs at least as well as any other arbitrary algorithm

Exchange argument: Transform any solution into a greedy solution

Structural argument: Figure out some structural bound that all solutions must meet

These last two were not talked about yet, but they will be later

We want to find a way to schedule the maximum number of jobs where job j starts at s_j and ends at f_j

How do we order the jobs?

Algorithm is on page 118

The best way to do it is by the finishing time.

Algorithm should be pretty obvious and intuitive.

We have a bunch of overlapping intervals, and we want to assign them in such a way that we have a minimum number of conflicts

Algorithm on page 124

Note that the greedy algorithm never assigns two incompatible intervals to the same label

Proof on page 124-125

Start with an optimal schedule

Slowly change it over time (while maintaining optimality) until it is identical to the greedy proof

(Pretty similar to greedy stays a head, same basic idea)

Pair of jobs, i and j, such that the deadline of j is before the deadline of i, but i is scheduled first

Proof of this is on page 129

Pretty obvious

Proof is in the slides

This follows from the previous claim

Consider an optimal schedule that has the minimum number of inversions

(We can safely assume we have no idle time in this schedule)

If there are no inversions, this is the same as the schedule produced by our algorithm (same proof technique as last time)

DONE!

Keep track of explored nodes S

Keep track of distances to each node (initially infinity)

On page 138

Page 139

Let S be the set of all explored nodes

Add another node v (we are no dealing with k+1 nodes) that is connected by edge (u,v)

We have the shortest distance to u

Any other path from root to v will be no shorter than that from root to u to v

So, this works by induction

Tree with n-1 nodes that connects all the nodes

This means no cycles

Let S be any subset of nodes. If the edge with the minimum cost has exactly one edge in S, the MST contains that edge.

Consider a cycle. The MST does not contain the largest edge in that cycle.

Implementation explained on 149-150

Fancy data structure

Keeps track of edges added

Maintains disjoint sets

Details are on page 157

This Union-Data Structure is pretty magical.

It essentially make the whole algorithm easy.

We got a bunch of points

There is a numeric value that specifies the similarity of the nodes

How do we divide them into k non-empty groups where the ones in the same group/cluster are more “similar” to each other than to any member of another group/cluster?

We want to cluster them in such a way that there is maximum spacing between the clusters.

How do we do that? Read that last line again. MAX DIST.

Just get rid of the longest edges. BOOM.

We only need to delete k-1 edges to get k groups

Didn't talk about efficiency of the algorithm much in the book, but I guess that's because it's not particularly difficult to figure it out.

How do we know that this algorithm works, i.e. produces a k-clustering of maximum spacing?

Just like CS112

We need 5 bits to encode whole aphabet.

We can do it in a better way.

We can have shorter encodings for more frequent letters.

This will work as long as prefixes don't overlap.

Goal is to minimize ABL (Average # of bits per letter)

Calculate ABL with ABL = sum ( frequency * #bits)

It would actually be pretter interesting if they explained how they got this formula. It wouldn't help me learn at all, but it would have been cool

How to minimize it? Brute force? If that was the answer we wouldn't be studying this.

Use binary tree to represent encoding. encoding is the path you take to get to the letter (all letters are on leaves)

0 left 1 right

There's a proof in the book about how the tree has to be full. I thought this was pretty intuitive. I don't know if this is because I've seen this before or if it actually is just pretty intuitive.

Proof is on page 168

We know it makes a lot of sense to have the most frequent letters near the top of the tree and to have letter with similar frequencies to have similar bit lengths.

This is how we are going to put them in the tree.

More frequent → higher up in teh tree → fewer bits

Similar frequency → sibilings or similar # bits

Algorithm on Page 172.

Proof on page 174-175 for optimality

# of subproblems

size of subproblems

number of levels

cost of combining

Find the four things above

Calculate the number of problems per level

My way of calculating this may be very wrong.

But, I think that winging it works just as well.

It really depends on how you define array[i]>array[j].

Merge And Count and Sort And Count algorithms on page 224-225

Will put a more informal explanation of Merge and Count below because it's the real important part

This is more of how a person would do it, not at all how the algorithm works because the algorithm is all recursive and such.

Separate list into two parts (Divide is O(1))

Assume both sides are sorted (because they are sorted by Sort and Count

Keep a counter on both sides

If not, move left side over

This whole time, we are also merge sorting the list.

This way, we end up sorting the entire list as well as finding inversions.

We can see how we are able to recursively count inversions this way.

The recurrence relation is T(n) ≤ T(n/2) + T(n/2) + O(n)

We can see that the running time is O(n log n)

Pretty obvious seeing how similar it is to merge sort

Cut initial area that is encapsulated in a box into two boxes

Find closest on each side brute force style. The min of the shortest distances on each side is called delta.

What if the closest points in the whole box happens to be right on the line we cut?

Check within delta of that line.

We are done.

We can see clearly how this can be done recursively

The recurrence relation is T(n) ≤ 2T(n/2) + O(n log n) for the algorithm on page 230

We divide each sub box into two new sub boxes each time

This explains the 2T(n/2)

The O(n log n) combination cost comes from the fact that we must sort the points along the delta strip on the dividing lines

This gives us T(n) = O(n log^2 n)

We can do better and get T(n) = O(n log n)

When we do the recursive step, the sub problem that going up the chain is returning a sublist that is already sorted. We just need to merge these lists instead of merging from scratch.

This gives us T(n) = O(n log n)

xy=(x_1(10^(n/2))+x_0)(y_1(10^(n/2))+y_0)

xy=(x_1*y_1(10^(n/2))(10^(n/2)))+(x_1*y_0+x_0*y_1)*10^(n/2)+(x_0*y_0)

xy=(x_1*y_1*10^n)+(x_1*y_0+x_0*y_1)*10^(n/2)+(x_0*y_0)

Recursively multiply on x and y

Divide into two parts like above

compute x_1+x_0 and y_1+y_0

Recursive step on these two sums

set p = to this value

set x_1*y_1=Recur on x_1 and y_1

set x_0*y_0=Recur on x_0 and y_0

return (x_1*y_1*10^n)+(p-x_1*y_1-x_0*y_0)*10^(n/2)+(x_0*y_0)

(I know this notation is very terrible, but the formal proof is in the book. I wrote it this way so I could understand it better)

Something I find very interesting is that memoizing seems very intensive on I/O actions. It makes the program a lot more efficient in terms of run time, but it really hits the I/O hard because of how much reading and writing we are doing. This really makes me wonder if memoizing is that great after the Andy Danner talk.

Can be easily solved with tail recursion.

The idea is to write things down that you have already computed.

Job j starts at s_j, finishes at f_j, and has weight or value v_j

Two jobs are compatible if they don't overlap

Having to constantly recompute Compute-Opt(p(j)) is stupid. Let's not do that and just compute it once.

This only gives us the total value/weight that is the max achievable. It does not tell us what intervals were chosen.

We can figure this out after the fact.

We still have our M[] array, which is nice.

If I was the author, I would have put that in the last chapter. It has no business being here.

Consider the first and last points.

For every point p_n, it can only belong to one line segment

We define cost for each point as cost: c (segment cost) + error of segment

Let OPT(j) = minimum cost for points p_1, p_i+1 , … , p_j (the min cost of all the points)

Let e(i, j) = minimum sum of squares for points p_i, p_i+1 , … , p_j

The magic really lies in the math behind the least square error. That's how we determine which segment something belongs to.

For some reason the book likes to do things in this very not straightforward way of finding all the data we need using one algorithm and then later using that data to find the information we really need to get our results.

So, since we really need to know how to split up the points into a sequence of segments, we will go through all the segments we just assigned

Input: N, w_1,…,w_N, v_1,…,v_N

return M[n, W]

This is a strange one.

It's Θ(n W)

So it both depends on the knap sack capacity and the number of objects

they call it Pseudo-polynomial.

Weird stuff. Never thought algorithms like this existed.

You have a directed graph

Each edge has a capacity

Have a start node s and end node t

More explanation on page 350

Boom and we are done. Just use the same stuff as in the past section and we have all we need.

Dicusses how to tell if it is impossible to find a perfect matching in a bipartite graph.

We have a directed graph

edges have capacities

nodes have supply and demands

To keep the world form exploding, the sum of supplies == sum of demands

MAGIC: G has circulation iff G' has max flow of value D

MORE MAGIC : Given (V, E, c, d), there does not exist a circulation iff there exists a node partition (A, B) such that the sum of all the demands is greater than cap(A,B)

These two pretty much solve the problem for us. more details are on page 382 if you get confused rereading this sometime in the future

Same givens as last problem

except!!!! we have lower bounds on each edge

algorithm on page 384

Here's how we do

we set teh flow along an edge to be the lower bound and then we update the demand on both nodes attached to it.

the rest is self explanatory