POTS

Ryan Chen

2/22/17

POTS

The book pattern on the stones I think was an interesting book. You learn a lot of stuff you didn’t know much about computers. There are a lot of difficult words and information they throw at you in the book which when you read it sometimes it doesn’t make sense. You would have to google some words to know the definition before you can understand what they’re talking about. It was easy to understand when they tell us how they program a computer to make the best move possible every move you make so it’s like the computer is programmed to win. When they talk about Invert, And, and or blocks that was when it got confusing. The algorithm chapter was kind of confusing but when the professor explained it in class I had a better understanding.

The most interesting thing I learned from the book is probably some of the problems you think a computer can solve can’t actually solve it. Like the traveling salesman problem trying to find the shortest route possible. It was also interesting when the book talked about how a computer uses 1s and 0s to created other numbers or letters. I liked how the books gives a story of an example at the beginning of every chapter like pairing up socks in (Chapter 5) because those were the things I understand in the book the most. It was also interesting when the book talked about storing memory and how they try to compress the most common word or letter to take up less memory in (P.93-94).

The parts I don’t like about the book is in almost every reading we do there’s always information we read that’s confusing or words that we know nothing about like the hierarchy. There’s a lot of information as you read the book and you really have to slow down and process the information or look up words and try to understand it throughout the reading. It’s not a book where you can read the entire book then write a lot about because it’s a lot of information to how a computer works and you might have to go back through the book to jog some memory.

There were many things I looked up on google because I didn’t understand the concepts. One for example I googled what pseudorandom is when they used it on (P.71) when they were explaining quantum computing. According to (Google) pseudorandom is (of a number, a sequence of numbers, or any digital data) satisfying one or more statistical tests for randomness but produced by a definite mathematical procedure. So basically it’s a number that appears to be random but it’s not. The numbers are generated by a sequence so they appear statistically.

The book gave me a good understanding about computers. I didn’t really have any questions going into this book except just reading it to see what it’s about. It explain about how data gets stored and how expensive it was back then for memory on a computer when today we might use a bunch of memory on our phone and not think about any of this since iphone changed it’s lowest gigs to 32gb.

For me since this is the first book about computers I’ve read I would recommend it to a friend. But it takes a while for you to process the bunch of information they give you as you read the book and there might be multiple things you need to look up in order for you to understand the reading.

This book is significant because it’s the basics and the history of how computers work and they break everything down. I think the book was chosen in this class was because the lectures in class had to do with the book. Every chapter I read before class the next day I go to lecture the teacher basically explains what we read. I didn’t understand the reading much sometimes then the next day I see the professor go through it in class it kind of made sense because I read about it before class. It’s good this book was chosen as the textbook so you’re not clueless during lectures as the professor is going through slides.

Algorithm

Ryan Chen

2/13/17

Bitap Algorithm

There are lots of algorithms out there but the algorithm I’ve decide to choose is Bitap Algorithm because it talked about strings at the beginning and it looks interesting. This algorithm is also known as shift-or, shift-and or Baeza-Yates-Gonnet. The algorithm was written by  Udi Manber, Sun Wu, and Burra Gopal. It was first invented by Balint Domolki in 1964 and extended by R. K. Shyamasundar in 1977 then Manber and Wu reinvented in the context of fuzzy string searching in 1991. In 1996 Baeza-Yates and Navarro improve the algorithm.

The way this algorithm work is they are string searchings that tells you weather if the text has a substring that is approximately equal to the pattern. There are two types of searching called fuzzy or exact searching. Exacting string searching uses zeros and ones. If a bit indicates a zero that means there is a match. If it indicates a one that means there are no matches. The algorithm can be written with the intuitive semantics for 0 and 1, but we must introduce another instruction into the inner loop to set R=1. In this implementation, left-shifting a value shifts in zeros on the right, which is precisely the behavior we need.

Fuzzy searching is a little different than exact searching. To use fuzzy string searching for the bitap algorithm, you need to extend the bit array R into a second dimension. Rather than of having one array R that changes over the length of the text, we now have k distinct arrays R1k. Array Ri holds a representation of the prefixes of pattern that match any suffix of the current string with i or fewer errors.An error may be an insertion, deletion, or substitution using this context.

I think what makes these algorithms special and unique is that it's a string matching and there are two different ways to do this algorithm by exact searching or fuzzy searching. I personally like exact searching because it made more sense to me when I read it. It uses ones and zeros and we talked about that kind of stuff in class so it makes more sense.

I found that Jaro-Winkler distance that was created by Winkler in 1990 is similar to the Bitap Algorithm because it measures a similarity between two strings. But, it is only best suited for short strings such as someone's name. It uses ones and zeros just like exact string matching one indicating an exact match and zero indicating no similarity.

There are some algorithms that can be done manually for example like sorting out a deck of cards. For the Bitap algorithm I didn’t see any sources saying you can do it manually but I assume you will be able to sort out words similarity to have it match but it will take a very long time. The reading in the textbook relate to this algorithm in (Chapter 5) where it talks about matching socks, traveling salesman problem, and the possibilities of a certain move. The textbook reading did give me a better understanding of how algorithms work by giving examples like the shortest time possible to match your socks(P.77-78) because before the reading I had no idea what algorithms were. I also learned computers can’t solve every problem using algorithms like the traveling salesman problem(P.87-89).

Bitap Algorithm helps you match a text that is approximately equal(Wikipedia). You can use it in a real world situation for example if you want to find how many students in a school has the same name or a most common name you would use Bitap algorithm. Another example you can use this algorithm in a real world is to find out what is the letter that is being used the most to name a word so you can encode it to save data.

"Bitap Algorithm." Wikipedia. Wikimedia Foundation, n.d. Web. 13 Feb. 2017.