Making Meaning: POTS

The first book used in this computer science course was Pattern on the Stone and will be further referred to as POTS. POTS was written by W. Daniel Hillis and provides the basic information needed to grasp an understanding of algorithms, Turing machines, programming, and a few other important topics that are all required to become a computer scientist/programmer. When I say basic information, I mean that this book doesn't dive too deeply into any particular topic but gives an elementary level of information about multiple topics under the computer science spectrum. For instance, there are far too many algorithms in existence for a book of only 153 pages long to explain in excess, but it focuses chapter 5 on providing the reader with the definition of heuristics and algorithms, explaining the similarities and differences, and providing some hand-picked sorting algorithms that can be used when sorting numbers or playing cards. (80) In our computer science class, we tested a few of these algorithms and their efficiency in sorting standard playing cards. We used the bubble sort, quick sort, insertion sort, and merge sort. Of these algorithms, we found that on average our class was able to sort the cards the fastest through quick sort and that insertion and bubble sort took about the same amount of switches. After completing this in class demonstration, we were each told to select an algorithm from Wikipedia to research. I chose to look into Edmond's Algorithm, and though it was a bit too complex for my understanding, I could tell that it had the same principles of the algorithms mentioned in our textbook because finds the minimum point in graphical data. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) This was a fairly interesting chapter for someone who has had no programming experience before but that enjoys math. SPOILER ALERT: the chapter begins by showing how even matching socks is done through algorithms, making it difficult for anyone to try to deny a need for algorithms in their life. Algorithms are everywhere and are used everyday by everyone. To break away from the algorithms section, I must admit the second half of the book appeared a little more dry and had far less humor and less interesting ways to remember important information or definitions. Chapter 7: Parallel Computers was perhaps one of the most boring sections of the book, however, it was still possibly the most important. It starts by diving into the history of computers which began to be developed in the late 1940's to early 1950's. (107) The chapter continues to show how the speed, prices, and structure of computers have changed throughout time. One of the major causes for this was that computers needed to be able to do multiple operations and be available to more people in different jobs, in schools, or even in homes. The most cost efficient way of creating a computer that could meet these requests was to use microprocessors in large quantities, (for reference, the first parallel computer the author, Hillis, built contained 64,000 processors) and connecting them together to form what is known as a parallel computer. (109-113) I found this little bit to be fairly interesting. Considering using 64,000 microprocessors to ensure a computer would be able to perform multiple operations reliably at a fast pace while still being fairly small in size just seemed absurd! I began wondering how many processors were used on average for parallel computers over the last few decades but couldn't find much except that most computers today are dual or quad-core processors. This book certainly has its ups and downs but I highly recommend it for someone who has yet to take a computer science or computer programming course.

Edmonds' Algorithm

This past week in CIS 115, we have been talking about algorithms. An algorithm is a procedure that is guaranteed to achieve a goal or produce a correct answer to some sort of problem every time. (The Pattern on the Stone by W. Daniel Hillis p.78)  The first algorithms we discussed in class were sorting algorithms: Bubble, Quick, Merge, and Insertion. Each of these can be easy simulated with a deck of cards and will all result in the same conclusion where the cards are sorted from 2-A (low to high) but are varied in their run times and some work better in different situations. For instance, the average run time for quick sort is n(log(n)) but it has the worst possible outcome of n^2 where n is the number of data present. The worst case possible for insertion and bubble sort is also n^2 while the merge sort worst case scenario is only n(log(n)). Generally speaking, algorithms exist solely to make work easier for people and computers. In fact, one of the books we are reading in class is titled Nine Algorithms That Changed the Future by John MacCormick. This book goes in depth on the following algorithms: Euclid's Algorithm which finds the greatest common denominator, Dijkstra's shortest-path algorithm, the nearest-neighbor algorithm, as well as a few others which have shaped coding, databases, and digital signatures. Some of the more common algorithms have to do with sequencing data, sorting data, calculations, and graphs. One algorithm I am specifically interested in that assists in graphing is called Edmonds' Algorithm. This algorithm was first presented Yoeng-Jin Chu and Tseng-Hong Liu in 1965 and was later presented again by Jack Edmonds in 1967; Edmonds' Algorithm is used to find the maximum and minimum points in branching. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) The purpose of Edmonds' Algorithm is to take D = (V,E) where D is a directed graph, V is the set of nodes, and E is the set of edges while the root (r) and weight (w) make up E to find the arborescence (A) in the cycles (C) and (u,v) make up the edges. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) To understand this, people need to first understand what arborescence is. Arborescence is a directed graph (D) with one direct path from u to v. There are three possible outcome for this, one where the edge (u,v) goes towards the cycle (C), one where the edge goes away from the cycle, and lastly one where the edge is unrelated to the cycle. The first one, where the edge goes towards the cycle requires a new edge (E') to be created with the formula w'(e) = w(u,v) - w(pi(v),v). Both others result in a new edge with the formula w'(e) = w(u,v).(https://en.wikipedia.org/wiki/Edmonds%27_algorithm) Once both edges are present, E and E', the algorithm can be used to find the minimum spanning between A' and D' by observing f(D, r, w) and f(D', r, w'). The run time for this algorithm is O(EV) but has been modified a few different times over the years to have some faster and more efficient run times of O(ElogV), O(V^2), and O(E + VlogV). (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) This algorithm, though interesting, is difficult to grasp at this time being that I have no purpose for it nor a way to test it for myself. Even though I have no reason to use this right now, Edmonds' Algorithm is a key component of algorithmic graph theory and has been for roughly 50 years. Without Edmonds' Algorithm, certain graphical data would require more people and time to calculate.