Anna's Journal

Preface

Chapter 1

This book puts a lot of emphasis on explaining their approaches to problems. I definitely think this is beneficial because it helps me see the overall goals and processes. This section starts with a basic definition of efficiency, simply that an algorithm is efficient if it runs quickly on real input instances. This definition lacks specifics and a way to quantify how to determine how fast is fast enough. Our final definition of efficiency needs to be independent of the platform and the size of the input set. This section also introduces the concept of worst-case running time as a measure of efficiency. Worst-case measurement is good because it is simpler to find and prove than average-case and more accurate overall than a random test set. A possible better definition of efficiency is that an algorithm is efficient if it is better than brute force search, which looks at every possibility(of perfect matches, for example) to find a stable one. Finally, this section looks at polynomial time, which is the best way to classify an efficient algorithm. The authors make the point that not all polynomial algorithms are faster than all exponential algorithms; it really depends on the practical situation, but it is a good abstraction of most situations.

This sections starts by discussing concepts we learned in CS112 about asymptotic order. However, the use of Θ and Ω are new to me. The O(n) notation that I am used to is used for the asymptotic upper bound. Note that there can be several upper bounds, but the best one to use is the tightest, or least upper bound because it can give a more accurate representation of the actual running time of an algorithm. The tight bound is expressed using Θ(n) and the lower bound is represented by Ω(n). All three of these have the following properties: transitivity, composition/sum of functions. The three most common functions in asymptotic analysis are polynomial, logarithmic, and exponential. Logarithmic function grow slower than polynomials which grow slower than exponential functions.

Because I missed this lecture in class, this section was very helpful in clearing up the differences between O, Θ and Ω and their respective uses, but for the most part, this section was a lot of review.

This section discusses the uses of list and arrays in implementing the Stable Matching Problem discusses earlier. To accurately compare when to use a list vs. an array, we need to know the running times of basic array and list actions and their trade-offs. Some trade-offs to note are as follows:

- An array had constant access time for the ith element, but is not good for dynamically maintaining a list of elements that changes.

- Lists are the opposite, with O(i) time to find an element i, but they are good for dynamically changing sets.

- We can also convert between array and list representation in O(n) time.

Since we want the algorithm to run in n^2 time, each iteration must be in constant time. The preference lists are implemented with an array. There are several lists that contain information about engagements, free men, and a man's next proposal. These all contain elements that will change throughout the algorithm. These data structures allow the G-S algorithm to run in O9n^2) time.

I thought this explanation was a little bit more confusing than when we discussed it in class, mostly because there is not a good way to write the explanation down that is not wordy and has lots of variables. I probably would have been really confused if I had read this section before class.

The goal of this section is to help us have a better understanding of common running times and what their typical algorithms might look like. They start with the running time of the brute-force algorithm, with the goal of being able to improve the algorithm.

A linear algorithm has a running time of at most c*(size of input). Examples of this are computing the maximum of n numbers and merging two sorted lists. O(nlogn) is the running time of many common algorithms, such as mergesort. They all have the property that the algorithm splits the input in half, solves the halves, then puts the solutions back together. Algorithms with nested loops or ones that work on pairs of things(points, for example) generally run in quadratic time. Cubic algorithms are similar to quadratic ones, except they would have three nested loops or points in 3-D space. An example of an O(n^k) algorithm is finding independent sets of size k in a graph with n nodes. This algorithm would enumerate over all sets of k nodes and decide whether it is independent. Similar to this, to find the independent set with the maximum size is O(2^n). This generalizes to search algorithms where we must look at all subsets. n! time usually comes up when we are trying to find all ways to arrange n elements, where order matters (i.e. Travelling Salesman Problem). The best-known example of a sublinear algorithm is binary search, where the input does not need to be completely read in to start.

Starting on page 48, there are many algorithms in this section. Most of them are ones I have seen before, so while this was not a hard section, it is a good reminder of important algorithms and running times.

This section discusses how to implement a priority queue efficiently, using a heap. I learned this in CS112, but I like the different perspective of this book. It constantly reminds us of the usefulness of priority queues and how they can be used to efficiently solve problems.

Priority queues are incredibly useful for implementing an algorithm to schedule real-time events where each event has a ranking, or priority. If we use a list to implement a priority queue, we will have linear time for either add or delete, but our goal in to achieve O(logn). Our solution is to use a heap, which looks like a balanced binary tree, such that the priority of every parent is bigger than or equal to its children. There are picture and examples on page 60. Representing a heap as a array where an element i has children at 2i and 2i+1 is fairly simple and provide O(1) time to find the minimum element, since it is at the root. The add and delete operations require us to Heapify-up or Heapify-down to fix the heap after we add or remove an element. These algorithms are on page 61 and 63. These both fix our heap in O(logi) time, as desired.

This section simply introduces graphs and some basic terminology that is related to them. This section is pretty much review from CS112, but there are definitely a few important concepts that it is helpful to review and remember. Graphs are incredibly useful data structures, especially for modeling a variety of networks, such as social or communication networks.

A path in an undirected graph is a sequence of connected nodes. Paths can be simple, where all vertices are distinct, or there can be a cycle, which is when the path loops back to where it started. A graph is connected if for every pair of nodes, there is a path between the nodes. A tree is an undirected graph that is connected and does not contain a cycle. You can picture it as being able to pick a node as the “top” of the tree and all other nodes can hang down from it. Every tree of n nodes will have n-1 edges. The main theorem of this section is that for an undirected graph G of n nodes, any two of the following imply the third:

i) G is connected

ii) G does not contain a cycle

iii) G has n-1 edges.

This section looks how to efficiently determine if there is a path from node s to node t in G. To do this, we compare breadth-first search(BFS) and depth-first search(DFS). BFS starts at s and explores outward in each direction, considering all nodes 1 step away, then all nodes 2 steps away, and so on. We call these layers, so each layer i of the tree represents the nodes that are i edges from the starting node s. We know there is a path from s to t if and only if t appears in one of the layers. Another property of a BFS tree is that nodes with an edge between them must be in adjacent layers.

In DFS, you follow the first edge out the node s, and follow it until you reach a dead end, where you back-track and explore the next node at that layer, and so on. The key property to remember about a DFS tree is that is that edges not in the tree, but in G can only connect ancestors.

Both BFS and DFS can build the connected component of a graph. However, they visit nodes in a differnet order and BFS produces a dense tree in comparison to DFS. Personally, I think the BFS algorithm and approach is more logical to me. The point of these trees is to show that for any two nodes in a graph, their connected components(which can be represented as a tree) are either identical or disjoint.

A graph can be represented as an adjacency list or an adjacency matrix. In this book, we use the adjacency list. The main reason they chose this implementation is because it corresponds well to the idea of “exploring” the graph. With an adjacency list, if the algorithm is looking at a node, it can read the list of neighbors in constant time for each neighbor. Overall, the adjacency list takes O(m+n) space, which is less than the adjacency matrix.

The BFS can be implemented with an adjacency list and either a stack or a queue(we chose a queue). This ambiguity is because the algorithm can consider the nodes in each layer in any order. This allows us to implement BFS in O(m+n) time. The algorithm for BFS is on page 90-91. DFS, on the other hand, must use a stack in order to get a running time of O(m+n). This is due to the recursive nature of DFS and the fact that the order in which we visit the nodes is important. The algorithm is on page 93.

Because BFS and DFS only spend time on nodes and edges in the connected component of the graph, we can find the set of all connected components in O(m+n) time, even though we may have to run the DFS or BFS multiple times.

A graph is bipartite if all the nodes can be colored red or blue such that each edge has one red end and one blue end. The problem that this section discusses is how we determine if a graph G is bipartite. One easy way to rule out a graph as bipartite is to look at cycles. If a graph has an odd length cycle, it is not bipartite. Designing an algorithm to determine if a graph is bipartite makes use of the layers in a BFS tree. You choose a node s and color it red. Then all the nodes in layer 2 will be blue, and so on. Since we only add a coloring step, the running time for the algorithm is the same as that for BFS, which is O(m+n). If there is an edge between two nodes in the same layer, then there will be an odd length cycle and the graph will not be bipartite.

I have seen problems similar to this in other classes. The two color problem, or the problem of coloring connected nodes with the least number of colors possible. I think it is very interesting and a fairly intuitive problem to me.

This section gives a basic introduction to directed graphs and a few important concepts related to them. In order to represent a directed graph, we will use the adjacency list, as before, but each node will keep track of nodes that point to it and nodes it points to(i,e, to and from nodes). BFS and DFS trees are pretty much the same as with undirected graphs, but it is important to remember that even if there is a path from node s to node t, there may not be a path from t to s.

In talking about a strongly connected graph, it is best to talk about whether or not two nodes are mutually reachable, which means there is a path from the first node to the second, and vice versa. One nice property is that if u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable. This is an intuitive property that is very useful. The strong components of two nodes in a graph are either disjoint or identical.

It seems to me that algorithms for directed graphs only require slight modifications to the algorithms for undirected graphs. In some cases, the algorithms are the same; the results just need to be interpreted differently.