Tying It All Together
Episode #10 of the course Kurt Anderson by Computer science fundamentals
Welcome to the last lesson of the course!
We’ve learned a lot in the past ten days. Everything from how computers work to data structures and sorting algorithms. This is what computer science is in its essence, using all these tools to come up with efficient ways to accomplish tasks. Let’s move from the abstract into more concrete examples of everything we have learned.
If you have used any technology in the past ten years, there is a 100% chance you have interacted with an array in some shape or form. A common example is a layout of a smartphone homescreen. In this situation, an array is used. Why? Because we want the same run time if we select the first app or the last app.
Imagine if we had to wait a little bit longer for apps on the last screen? This is a situation where an array would be superior to a linked list.
Linked lists are used just as much as arrays, but for more technical reasons. They are typically the basis for many other more advanced data structures.
Another common use of linked list is keeping track of memory on a hard drive. Many times, a hard drive won’t have a chunk of space large enough to store a program. However, it may have some space near the front, some near the middle, and some near the back. The program is then inserted in all these places and linked together through a linked list.
Stacks and Queues
Stacks and queues are also widely used. Stacks actually create the basis of every operating system, while queues are used to process commands in the processor.
Have you ever used the undo and redo feature on a text document? That is typically implemented with two stacks.
The left side is the current stack. The right side is the undo stack. Every command we do is pushed on to the current stack. Whenever we undo a command, it is popped off the current stack and pushed onto the undo stack. This allows us to go back in time.
If we wish to redo, we will pop off the undo stack and then push it back onto the current stack.
Sorting algorithms are some of the easiest to prove. Data is constantly sorted for us. Think about the transactions on your bank statement. That data is typically sorted by the date.
If you are a business and have hundreds of thousands of transactions a day, then the speed of the sorting algorithm begins to become important. Let’s say we have to sort 6,765,432,432 transactions. If we have an algorithm that can do it in n time, then our final time is 6,765,432,432 units. Now, if we used bubble sort, for example, which runs in n^2, the sorting would run around 457,710,760,000,000,000,000,000,000, which is roughly 6,765,432,432 times slower.
If those were nanoseconds (10^-9), the first would take about 6.76 seconds to sort. The second would take 145,139,129 centuries to sort. Efficiency is important!
Trees are often used to store data that needs to be accessed quickly.
The most common example is the file system on your computer. A tree helps keep the data organized in a way that makes logical sense. Each directory leads to another directory or file. This allows us to quickly find a file on a machine that might have a million different files on it.
There you have it. I hope you have enjoyed your days learning about the computer world. This all just scratches the surface of computer science. It is a large and expansive field that is advancing every day!
It’s been an honor teaching you!
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Share with friends