A Gentle Introduction to Data Structures and Algorithms

A short Preamble

1. As a race, humans have always been faced with numerous challenges.
2. Computers are arguably the most powerful problem solving tool we have invented yet.
3. There is only one problem, computers live in a virtual world outside our own. They don’t understand the challenges and problems we go through.
4. So we have to describe to them, step by step, instructions for solving any instance of a particular problem. This is often referred to as an algorithm.
5. Now, programming allows us to implement these algorithms on a computer and solve our problems!

Solving Problems with Computers

Short Notes on Data Types

1. To solve problems with computers, we first have to express the problem as something the computer can understand.
2. While trying to describe problems, we often realize they involve some kind of data we have to manipulate. It can be numbers, letters or something more complicated.
3. Now, all programming languages come with some predefined ways of representing data while writing our programs.
4. The most basic form of data representation are data types.
5. Formally, we can define a data type as a set of data values having predefined characteristics.
6. Take for example the integer data type. It allows us to represent whole numbers and thus provides us a way to solve problems that deals with counting.
7. Other example of data types includes Boolean, Float, Double, String and Character.

Working on data

Short Notes on Data Structures

1. Simple data types are great when dealing with individual values, but what happens when we need to perform operations on our data collectively?
2. Well this is where data structures come in. Basically, we can always build data structures to suit the nature of data.
3. Data Structures allow us to group data together and describe the attributes and actions that can be performed on a particular instance of the data.
4. Obviously, programming languages come with some in-built data structures to handle data that are common to most problems.
5. Let’s look at an interesting class of data structures often referred to as collections.
6. As the name implies, a collection is a grouping of similar data items. The items have some shared significance to the problem being solved and need to be operated upon together.
7. Now, depending on the nature of the problem, we might have to keep the items in our collections ordered or we could simply leave them unordered.
8. By ordered, we simply mean the collection remembers the order in which items are added.
9. Take for example you leave 10 books on the floor, next to your table and go out for a walk.
10. To you surprise, when you get back, you meet the books on the table, neatly stacked, one on top of another.
11. Now, although you were not there when the actually stacking took place, simply looking at the books, you can easily point out which book was picked first and the order in which subsequent books were added.
12. We say the stack of books form an ordered collection.
13. In contrast, consider a crate of eggs. It is next to impossible to state correctly the order in which the eggs in the crate were added since honestly we could have put an egg in any of the spots first.
14. Such a collection does not enforce order and as such can be regarded as an unordered collection.
15. So, what are the common example of data structures that can be regarded as collections?
16. Well for ordered collections, we have the stack data structure analogous to our earlier example about stacking books. Another common example would be an array (sometimes called a list).
17. Just think of a simple shopping List. All things being equal, you can correctly point out the order in which the item were added to a shopping list, right?
18. Well how about our unordered collections? A good example would be an hash table. Big word Alert! What is an hash table?
19. Well, simply put, an hash table is a collection made up of key — value pairs. Your pairs can be anything from student names and their scores in a test, to words and their meaning.
20. So how does this form an unordered collection?
21. Okay so let’s imagine the index at the back of a book.
22. Each line contains a word and next to the word, the pages of the book in which the word appears.
23. We can think of it as somewhat an hash table where the word and the page numbers form a key-value pair, aye?
24. Interestingly enough, this type of information provided at the end of the book tells us noting about the position (or order) of the words in the book.
25. The first word in the index, say ‘APPLE’ might occur only on the last page of the book!
26. This lack of order, just as seen in the crate of eggs example tells us the hash table is an unordered collection.

Thanks for reading, stay tuned for more notes in the series.