Letter 004: Data Structures and Algorithms
From a life lesson to computer science
Hello everyone,
Today I saw below tweet on my timeline:
It’s indeed a good story. I appreciate the professor who gave us this genius lesson. But for me it goes beyond that lesson and inspired me about how to explain data structures and algorithms.
Computer science is all about modeling the real life problems in the math domain, so that computers can solve them. Because they don’t understand anything about the real life. You have to choose the right data structure and algorithm to solve a problem faster. Sometimes it’s even impossible to solve if you are not using the right algorithm or data structure.
In the first case, the professor wanted everyone to find her own balloon. N person has to search N balloon in the hallway. In the worst case scenario there will be NxN=N^2 lookups since N students has to check N balloons to find theirs. This is equivalent to searching N items N times in an array in computer science. An array is a data structure that holds items sequentially. You have an object at location #1, and the next one is at #2 and so on. You know where is #1 or #N but you don’t know what is in it. To find something in the content you have to search all locations starting from the first one until you find it.
array[1] = alice, array[2] = bob, array[3] = john
In the second case, professor wanted them to pick a balloon and give it to its owner. In that case every student will perform only one lookup and total N lookups will be performed. Finding the owner of a balloon doesn’t require any search because you know that person from her name or face and you will go to her directly. That is equivalent to hash maps in computer science. A hash map is like dictionary. You access to the explanation with a keyword. Or like phonebook. You give a name, it returns the phone number. You don’t need to search whole phonebook. Searching N items in a hash map requires N lookup. Each item stored at a special location whereas the location can be calculated with the keyword. As students have unique faces and you can remember faces from their name, likewise in hash map, you can access a value immediately by using its unique name.
hashmap = { 'hello': 'hola', 'book': 'libro', 'bye': 'adiós' }
You might ask, if hash map is the fastest one why do we even have arrays? Well, this problem and similar problems (giving the key and asking the value for this key) is suitable for hash maps. But there are some other problems that can be solved via arrays faster. For example, imagine a graphic engine of a game. The engine treats your screen as a matrix: Each row on your screen is an array of sequential pixels. Let say, your character is looking at a mirror in the game. She sees her reflection. Creating reflection from the original object is actually a matrix calculation. For this specific problem hash map is not a good solution. Because there is no key based search.
