Making Meaning: 9 Algorithms that Changed the Future

9 Algorithms that Changed the Future by John MacCormick was the third and final book of the semester for my Introduction the Computer Science course; this book was my second favorite.
MacCormick writes more similarly to W. Daniel Hillis (author of Pattern on the Stone) than the journalistic writing approach of Andrew Blum (author of Tubes, my least favorite book in this course). I prefer a textbook or research article type of writing styles. IF you are someone who prefers journals and diaries, perhaps you might dislike this text and find that Tubes is much better. Getting away from simply the writing styles of each author, 9 Algorithms that Changed the Future has content on, as mentioned in the title, algorithms, their uses in indexing and cryptography, and other key examples of where algorithms are needed in computer programming. The one that hooked me the most was cryptography, partially because as I have previously mentioned in other blogs, had a desire to get into cyber security or cyber investigation upon graduation. Chapter 4: Public Key Cryptography discusses the purpose of using public keys to encrypt messages in order to protect private information such as social security numbers, credit card data, and addresses in order to prevent "eavesdroppers" from obtaining the information and stealing people's identities. (39) When we got to this chapter in the text, our professor showed us a video on the Enigma machine that was used by the German army to encrypt messages during WWII. The video, uploaded by numberphile can be found at https://www.youtube.com/watch?v=G2_Q9FoD-oQ and shows how the Enigma machine has different rotors that can encrypt messages in over 150 quintillion settings. Had this machine not been figured out by the allied countries, the German's might have won the war!
Breaking away from the Cryptography section, Chapter 5 relates to the topic of my group project. My group decided to research Genetic and Evolutionary Computation which requires a lot of error correcting codes for Artificial Intelligent programs. Throughout chapter 5, MacCormick shows how the Repetition Trick, Redundancy Trick, Checksum Trick, Pinpoint Trick, and the combination of error correcting techniques are used in the real world to allow programs to self adapt or detect false information for the user to correct. The Repetition Trick is the most fundamental according to MacCormick because in order to make sure the information is relayed properly without errors, a program asks for input multiple times and compares the input; should the input vary, then it is apparent that an error has occurred. (62-63) The Redundancy Trick, although similar to the Repetition Trick uses pattern recognition and prior knowledge to compare faulty input or coded input and compare for possible corrections such as the word "fiqe", if the computer is looking for English numbers and received this, it can determine that the "q" should be a "v" and can change that to output the number 5. (66)  The Checksum Trick assigns a number to each letter, number, or character that the user inputs and checks the sum of the assigned data occasionally in a table both in rows and columns. (68) A great example of this is when entering credit card information online, a program can detect when a number is wrong if it doesn't match up to the possible checksums provided by VISA or Mastercard. Lastly, the Pinpoint Trick is the actual table method of the Checksum trick. For example, if you have 16 characters or digits, arrange them in a 4x4. Add up each of the rows and the columns then compare the sums. whichever row and column is wrong will pinpoint the singular digit that is incorrect. (74) Each of these methods is beneficial and key to improving technology or encryption. Overall, MacCormick's book 9 Algorithms that Changed the Future is a great read that helps the reader prepare for possible encryption, problem solving, or computer related courses and careers.

Computing Science and Mathematics

Coming to the end of the Introduction to Computer Science course, I have learned that mathematics plays a key role in algorithms and programming. In order to major in computer science at Kansas State University, students are required to take Calculus I and II, Statistics, Matrix Theory, and Discrete Math. The reason for this is that high computing and supercomputers require the ability to use logic, graphs, probability, and other math models to perform tasks or calculate results for more complex algorithms. (https://en.wikipedia.org/wiki/Applied_mathematics) Nearly every algorithm has at least some basic addition or algebra. Others require matrices and calculus. With every project or example we do in CIS 115, we use math. Sometimes its needed in order to calculate something small such as how many different possibilities there are to sort data or to provide a user with their GPA based on how many courses they are taking and what their grade in each course is followed by multiplying the hours the class counts for by the value of the letter grade (a project in CIS 111). In other cases, the math is not as easy such as with cryptography through IP public and private keys. Public key cryptography mixes numbers by using powers, primes, and clock arithmetic to provide a secure means through which users can share data with each other without allowing those who don't have the public and private key to see. (MacCormick 56-57) This piece is probably the most interesting to me because I plan on going into cyber security / cyber crime investigation and by being able to determine a person's IP, private, and public keys, it can help convict a suspect since their "private" information such as photos or conversations can be obtained. Unfortunately, being that people can use computers and algorithms to figure out what a person or company's private and public keys are, it can be used to harm individuals by stealing their credit card information, social security number, and other personal information. Another area that interests me is error-correcting codes. A man by the name of Alan Turing once proposed a question: "Can machines think?". This question may have been the starting point for error-correcting codes because if a computer is able to think for itself then it should be able to find errors within its programs and fix them on its own. These codes are necessary when trying to program a computer to be able to adapt and evolve on its own because, as stated in the name, the computer becomes able to correct errors.  Error-correcting codes would therefore play one of the largest roles in creating artificial intelligence.Some examples of error-correcting codes are the repetition trick, redundancy trick, and the checksum trick. The reason that the checksum trick is important is because computers store all information in the form of numbers which then gets translated to words or images. (MacCormick 68) This trick specifically helps determine if there is an error however it doesn't repair the error.  The way it works is that all the digits of a message get added together (which is where the math piece comes in) and the last digit gets saved to compare to other possible messages that are coded in the computer. (MacCormick 69) Another instance through which math gets used in computer science is in computational geometry. Algorithms and equations for different geometric shapes are needed for robotics, graphic design, computer vision, virtual reality, and an infinite amount of other development tasks. (https://en.wikipedia.org/wiki/Theoretical_computer_science) All of the areas I have mentioned in this blog are evidence that shows how important mathematics is in programming and computer science whether its just simple addition or complex calculus based algorithms.

The Filter Bubble

The filter bubble is the personalized search results an individual receives from a website due to an algorithm. (https://en.wikipedia.org/wiki/Filter_bubble) According to Andrew Blum in his book Tubes, Google searches and Youtube videos for people consist of direct links and therefore when considering the idea of the filter bubble, you would expect there to be similar ads on Youtube to compensate for the items and topics searched on Google. Filter bubbles vary from person to person based on political and religious views, purchases, search history, and interests represented through videos and music sources. This can have negative effects due to the fact that people may not always see truthful news articles because the filter bubble will provide them articles that agree with the individual's views. However, I decided to test the filter bubble with two of my friends and an incognito window. First, when I went to my Facebook page, the first ad I saw was for the Samsung Galaxy S5. When I went to Youtube, the first ad I received was for Fragrant Jewel bath bombs that come with rings inside of them. Lastly, when I went to Ebay, I was shown a sale on watches and earrings. Out f these three, two of the ads made sense. I own a Samsung S5 mini and have recently been looking at AT&T to see what phones I could upgrade to. In regards to Fragrant Jewels, I use their site a lot ever since a few of my friends shared the ads to my page on Facebook. However, I have not gone searching for jewelry so the Ebay ad seemed a tad off but I guess it could be related to the Fragrant Jewels searches. When I used an incognito window, I still saw a Samsung S5 ad on Facebook, saw an ad for the new Justice League movie on Youtube, and got an ad for Spring fashion on Ebay. I am assuming each of these three are pretty popular among the general population considering many people use smartphones, the Justice League is coming to theaters soon, and Spring is just around the corner. To compare with my friends' ads, they received ads for DiscountTires, Cricket wireless, Valero gas stations, Grammarly, HP computers, and Alienware. Considering both of my friends are male gamers, one of them has a car, and they don't look for beauty products, it makes sense that they received ads that had more to do with their computers and cars instead of bath bombs and jewelry. In The Pattern on the Stone by W. Daniel Hillis on page 78, Algorithms are a fail-safe procedure in that they will always achieve the goal at hand. The filter bubble, being based on an algorithm oriented towards searches and interests, is guaranteed to make suggestions and recommendations related to each individuals' internet history. This happens on Netflix and Hulu with TV shows, Spotify and Pandora for musicians and songs, and even Ebay or Amazon with shopping suggestions. After showing what the filter bubble is, how it works, and that it does exist by providing different results for individuals, I can say that I do believe it is beneficial in the realm of interests and hobbies but is harmful and obstructive when looking at news, media, and research sources because information may be biased and false. In fact, it may be best for people to open an incognito window when they need to search for political and religious issues. As unfortunate as this is that the filter bubble hinders the democracy of free speech and an individuals' right to know what is going on in their community, proper measures need to be taken. I myself pledge to be more cautious of filter bubbles from this day forward.

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.

Hi everyone! I'm Cynthia Ferguson, a sophomore in Computer Science at K-State University. I grew up in Lansing but decided for my freshman year that I wanted to get out of Kansas. I pursued a forensic science degree at Eastern Kentucky University but due to some complications and a desire to be closer to home, I decided to transfer and change my major. I have always had an interest in computers and crime investigation so I figured computer science would be a good fit for me. Out of all of the chapters we will be reading this semester, I am the most excited to read chapter 3: Programming from The Pattern On The Stone and chapter 6: Pattern Recognition from Nine Algorithms That Changed the Future. I believe these two chapters will have the most new-to-me information in regards to computers being that I have absolutely no programming experience. With any luck, when I graduate from K-State, I can get into the FBI, CIA, or Valve. My reason for wanting to work for Valve is entirely different from the FBI and CIA and simply revolves around the fact that I enjoy pc gaming. I have had an account on Steam for the last three years, through which I have become an addict and avid fan of Valve games such as Half Life, Portal, and Team Fortress 2. Prior to getting a Steam account, I generally just played on Nintendo consoles or played Minecraft. Gaming, though possibly the hobby I participate in the most is not my favorite or only hobby. I enjoy a multitude of things: fishing, camping, hiking, strategy games, singing, poetry, guitar, and baking. I have played the guitar and sang for over half of my life making it my oldest hobby. I enjoy writing my own songs and publishing them on Youtube and Spotify. Youtube.com is probably my favorite website due to the variety of videos that people can publish and watch. My channel is https://www.youtube.com/channel/UC1W3htrFm9XLG716Lw-7ZdA and contains covers and original works. I personally enjoy watching debates, podcasts, gamers, musicians, and karaoke videos. I am hoping that through my computer science courses, I can obtain a better grasp on sound recording and video editing software to improve the quality of my music videos. Aside from hobbies, I enjoy horror movies, have had many pets throughout my life, and am an overall very caring person. I can be the person that gets overly protective of those I care greatly about and I would always rather be in pain than to see someone I love get hurt. I have been told by many people that I care and trust too much about others but its just who I am and I wouldn't have it any other way. I enjoy getting to know new people by playing games with them, talking over tea or coffee, and sharing musical interests. I am a firm believer that someone's music tastes can tell a lot about the kind of person they are, what they have been through in life, and how open-minded they are. For instance, some people will only listen to one genre of music and that generally shows they are not open-minded and not musicians themselves as they don't appreciate other styles. On the other hand, those who listen to Rap, Rock, Country, Hip-Hop, etc. regardless of the time the songs were released often have a greater appreciation and understanding of music and the artists who perform the songs. The people I tend to relate to most however are those who analyze the lyrics to truly understand what they are singing along to. I hardly ever sing along to something without already knowing what the song is about, why the artist wrote it, and what it means to me. Many people say a picture is worth a thousand words, but the quote I prefer is it only takes one song to bring back a thousand memories. I love hearing new songs and bands so by all means, if anyone ever wants to talk about music, know that I am all ears.