Onye's Journal

Algorithms are important. They help us solve problems. They help us understand stuff. This book is about algorithms.

Section 1.1 talked about the stable matching problem and the gale shapely soluition to it. A typical example of the stable matching problem is n men and n women looking to be matched, with each man and woman having a strict order of preferences. For a given matching, m and w form an unstable pair if they each prefer each other to their current partner. For n men and n women with strict preferences, it is always possible to find a matching with no unstable pairs, and the gale shapely algorithm does just that. This works by taking any single man and attempting to pair him the his highest rated woman that we have not attempted to pair him with yet. If she prefers him to her current match, the pairing is successful, and she is paired with him and her current partner becomes single again. Repeat this until every man has proposed to every women.

Chapter 2 discusses the computational tractability and the running time of algorithms. It also discusses asymptotic order of growth and Big O. Algorithms that are polynomial time are O(n^k) for some k. These are said to be efficient. As opposed to that, some algorithms may be O(k^n), for some k > 1, for example. These algorithms are incredibly computationally intensive and quickly become impossible to calculate in a reasonable amount of time. For example, an exponential algorithm may run in under a second for n = 1, but take billions of years for n = 20.

In order to get the Gale-Shapely algorithm running in O(n^2) steps we need to get each step of the loop running in constant time.

Because of we need to both add and remove elements from the set of free men it is preferable to use a list to an array. (Though, it is entirely feasible for this problem to use arrays correctly without increasing the complexity. You can, for example, implement a stack with an array and since the maximum number of men is fixed there will be no fear of running out of space in the array so all stack actions will be constant time).

To keep track of the woman a man will next propose to you can use an array called Next where Next[m] is the number of the woman man m will have to propose to next. Of course, alternatively you could have kept the men's preference list as a list and deleted woman as he proposed to them.

Finally, we need an array Ranking[w,m] that gives the ranking of man m in w's list. This allows us to compare 2 men to see which one she prefers easily. This should be done outside of the loop.

This shows some running times and how some examples of algorithms that run in that time with explanations for why that is the case.

Linear Time: 1. An Algorithm can be linear if it processes the input as a single pass, spending a constant amount of time on each part of the input. An example of this is the most direct algorithm for computing the maximum of a list of numbers.

Another mehtod of looking at sort of accouting scheme. Charge the cost of each iteration to an element so the total cost will be bounded by the number of elements. An example where this approach works is analazying the running time of merging two sorted lists.

N log N:

N log N is common to “divide and conqure” strategy algorithms where the input is cut into pieces, each piece is analyzed separately and then it's all put together again. For example, sorting algorithms such as mergesort or quicksort. It is also appears as the running time where sorting is the most expensive component of the algorithm .

Quadratic Time: Quadratic running time is appears when processing is done on every possible pair of a set of n elements. For example, comparing the distance between every two points in a set to find the minimum. It can also arise from nested loops.

Cubic Time:

From triply nested loops. Or perhaps from selecting a pair and then performing a loop.

O(n^k) Time:

From k nested loops. Or from selecting a subset of k elements.

Beyond Polynomial Time: Some algorithms take even more than polynomial time. Some examples of running times like this are O(2^n) and O(n!). O(2^n) might arise in cases where we look at every possible subset of n elements. O(n!) might arise when looking at all the possible permutations of n items or matching n items to n other items.

Sublinear Time: Sometimes algorithms take less than linear time. Since just reading the input is linear time, these algorithms often work by having the input queried indirectly rather than read completely. An example of such an algorithim is the binary search algorithm for

Using a heap which is a tree where each node has a key and the key of a nodes children are not smaller than the key of that node. Using operations HeapifyUp and HeapifyDown, which fix the heap if it is messed up at one particular location it is possible ot implement insertion and deletion in logarithmic time. The heap is a natural choice for implementing a priority queue because the highest priority element is naturally at the top, and it works better than other implementations which require at least one operation to run in O(n).

Breadth first search can be used to test biparteness. A graph is bipartite if and only if there are no odd cycles. Color vertices based on the parity of the distance between them and an arbitrary starting node.

A directed graph is a graph where edges are directed arrows pointing from one vertex to another. The concept of connected component changes somewhat on directed graphs since just because there is a path from vertex a to vertex b doesn't mean there is one from b to a. A graph is strongly connected every vertex is reachable from every other vertex.

Directed Acyclic Graphs (DAGs) are directed graphs that are acyclic. Any DAG has at least one toplogical ordering, an ordering of the vertices such that if a has an arrow going to b then a comes before b. To find such an ordering just recursively build it by taking out the “least” element in the DAG, that is one with no arrow pointing to it. You will always find one of these if you try. You just have to believe.

Given a list of tasks with the time it takes to do the task and the deadline of the task the problem is to find a scheduling of the tasks to minimize the maximum lateness. Some incorrect approaches:

1. Do the shortest length tasks first. If a short task has a far deadline and a long task has a close deadline, then this will fail. 2. Define slack time as the difference between the task length deadline. Try to do tasks in order of increasing slack time. This is wrong because if something has a small slack time but a far away deadline, performing that before something with a slightly larger slack time but a much sooner deadline will result in a muc greater amount of lateness.

Djikstra's algorithm is one that can find the shortest path from a start node s to every other node on a weighted directed graph, so long as all the weights are nonnegative. It works by maintaining a set of explored nodes, for which the shortest path to is known, and a set of unexplored nodes. At each step, the edge of smallest length moving out from the explored set to the unexplored set can be used to extend the explored set, obviously. Using a priority queue Djikstra's algorithm can be implemented in O(m log n) time

The minimum spanning tree problem is to take a graph of weighted edges and to find a subgraph that is a tree, connects all edges, and has the minimum total weight. There 3 obvious algorithms:

Kruskal's Algorithm: Start with no edges. Move through the set of all edges in order of increasing weight, adding each edge so long as it does not form a cycle

Prim's Algorithm: Similar to djikstra's algorithm. Start with the root node by itself and simply add extending from explored nodes of smallest weight

Reverse-Delte Algorithm: Similar to Kruskal's but backwards. Start with all edges, delete the weightiest unless it would make the graph disconnected.

To see that these algorithms work, obsrve that if S is any nonempty proper subset of the set of vertices, the minimum cost edge extending from that set to a vertex not in that set must be included in the minimum spanning tree. If you have a spanning tree where it isn't used, it can replace any edge extending from S to a vertex out of S for a minimaler spanning tree.

Another example of a divide and conquer algorithm is used to count the numer of inversions in a scrambled list. This can be used to measure the similarity between two people's rankings of a particular subject. It works by simply using mergesort and counting the number of inversions observed along the way. It runs in O(n log n) time, just like merge sort.

Finding the Closest pair of point surprsingly has a O(n log n) solution, so it's an improvement on the O(n^2) brute force algorithm. This solution works taking the set of points P and sorting them in terms of their x coordinate and then sorting them again in terms of their y coordinates creating lists Px and Py. Then, using Px creating the lists Q and R where Q consits of the half points with the lower x coordinates and R contains the rest. Use Px and Py to construct Qx, Qy, Rx, and Ry of points of Q and R sorted in terms of x and sorted in terms of y. Recursively call the function using Qx and Qy to find the closest pair of points in Q, and using Rx and Ry to to find the closet set points in Q and in R. Then let delta be the smaller of the two distances. Let x be the x coordinate of the rightmost point of Q and let L be the line with constant x-value of x. Let S be the set of points whose distance from L is less than delta and Sy that set sorted in terms of y values (constructed using Py). Now, it turns out that any two points whose distance is less than delta must lie within 15 of one another in the sorted list Sy. To see this, consider a grid with boxes of length and with delta/2 around the line L extending two boxes from either side of L (to get a distance of delta from L). Each box can contain only one point since they belong to only one side and delta is a minimum in that case. So if a point is separated by 15 people it'll go through at least 3 rows so the total distance will be at least 3 delta / 2 which is greater than delta. So comparing each point with points up to 15 units ahead of itself will find the minimum in O(n) time. With the sorting, the entire algorithm runs in O(n log n) time.

Multiplying integers. Separate the values into a large end and small end like n = x1*2^(n/2) + x0. Expand the multiplication and rmeember to use (x1 + x0)(y1 + y0) = x1*y1 + x0*y1 + x1*y0 + x0*y0 so you can calculate three multiplications (x1*y1, x0*y0, and (x1+x0)(y1+y0)) instead of 4 (x1*y1,x0*y0,x1*y0,x0*y1), which would result in a quadratic algorithm just like the brute force solution (which can be seen for the general form of creating a recursive procedure whose running time satisfies the recurrence relation T(n) = q*T(n/2) + cn when q > 2)

Dynamic program is similar to divide and conquer because we solve a larger problem by solving smaller problems and combining the solutions. It differs due to the fact that the computations done on certain subproblems “overlap”, or can inform the computations of other solutions. Because this, the process of memoization, where computed results are stored in an array, can be used to create efficient algorithms.

The process of memoization only computes the value of the solution. In order to obtain the actual solution one must look at the method used to combine the solutions. In the case of the interval scheduling problem, the value of the vj + M[p(j)] is compared to the value of M[j-1] and that value is stored in M[j]. Thus, you can determine the solution by computing these values and seeing which is stored in M[j]. If it is the first, the solution includes j, if it is the second, then it does not include vj.

Once the p function is computed the algorithm runs in O(n) time, but computing the p function takes n log n so the total running time is O(n log n) time.

Segmented least squares is a problem that can be solved efficiently using dynamic programming practices. The problem is an extension of the problem of finding the line of best fit through a set of lines. In this problem, one can use several lines, but the there is a cost function that cL + E, where L is the number of lines used and E is the total square error of all the lines.

A direct implementation of the dynamic programming scheme results in an O(n^3) running time but it is possible to make the computation of all the square erros more efficient to bring the total cost down to O(n^2)

This version of the knapsack problem is as follows: You are given a list of N items each with “weights” and “values”. You have a specified weight limit, and must find a set that maximizes total value while coming under the weight limit. This case differs because the number of variables is two instead of 1, resulting in a 2-D array. Still, dynamic programming applies and the algorithm that results runs in O(NW) time