The fundamental toolkit for the aspiring computer scientist or programmer.
In computer science and programming - like in most analytical disciplines - there are several valid solutions to the same problem. The crux of mastering the fundamentals of computer science is making good design choices; that is, finding the “best” solution.
Computers allow us to store and manipulate information, and to perform computations ranging from simple operations like looking up the price of an item in a store to complex modeling like artificial neural networks.
In Computer Science Fundamentals, you’ll build your basic toolkit for how to organize logic (i.e., algorithms) and information (i.e., data) to efficiently solve seemingly complicated problems.
To start, imagine you want to build a personal Twitter feed. You’ll need to store the tweets in some way (so that the feed has the data it needs to display your tweets). Naively, you could start making variables; i.e.,
But this would quickly become cumbersome - a programming nightmare, with an unlimited number of variable names and no easy way to relate the tweets to each other. A simple data type - the list - will make this problem much more manageable.
In short, an array holds an ordered collection of items accessible by an integer index. They’re the simplest way of storing a collection of multiple values.
Imagine you are keeping track of Big Bird’s tweets over time. You create an array,
tweets, with 100 elements to store these strings, and each time you tweet you put your tweet into the left-most unfilled spot in the array, starting with 0. If the first few tweets are shown below, what is
tweets, the item in
tweets associated with index 3?
The items in an array can be anything from primitive types such as integers to more complex types like instances of classes.
There are a couple of points which are important to note:
In this visual representation of an array, you can see that it has a size of six. Once six values have been added, no additional values can be added until the array is resized or something is taken out.
You can also see that each "slot" in the array has an associated number, called an index. By using these numbers, the programmer can directly index into the array to get specific values, which makes them very efficient.
In the Twitter example, we decided to make an array with 100 elements to store the tweets. If you are going to tweet for a 101st time, what should you do so that all of your tweets are stored?
Often, we don’t simply want to store data - we need to use our data to extract some sort of information to answer a real-world question.
For example, imagine we're running a restaurant and we've stored the total price paid (as a float, or decimal number) by each customer on a given night in an array. How can we find the median amount spent by customers?
Note: For convenience, assume that they array is full and that there are an odd number of customers.
From the last question, we can see that a list implemented with an array has a potential drawback: the data is not necessarily sorted or related in any useful way (other than being mapped to indices).
In later quizzes, we’ll develop algorithms to efficiently sort an array. And throughout this exploration, we’ll discuss how to evaluate the pros and cons of different data types and structures when solving a given problem. Sometimes, simplicity will win; other times, we’ll need a more powerful but complex approach.
Which of the following measures of central tendency is easily computed given an unsorted array of integers?
So far, we haven’t touched the question of “how is this data actually stored?”. In this Exploration, we’ll avoid diving into low-level details like how computer memory works.
That said, a short answer is that the simplest implementation of an array (for example an integer array in C) takes up a very organized block of memory, making it very easy to find a particular value.
A more in-depth explanation of array properties can be found in this wiki page. And in an upcoming Exploration, Memory, we’ll take a deep dive into that side of computer science and programming.
We’ve looked at some very simple examples of how data could be stored in a list, implemented as an array. Each of these examples was one dimensional; however, many data sets we might care about have a more useful or natural representation that is two-dimensional or more.
Which of the following data would be more naturally represented by a two-dimensional array than a one-dimensional array?
Assuming that the image above was created by using a simple \(m \times n\) two-dimensional array, where an element of 1 represents black and an element of 0 represents white, what is the minimum possible value of \(m+n?\)
Like we’ve alluded to, the list (even when extended to multiple dimensions) is a fairly simple data type. For more complicated algorithms, we’ll want more complex ways to organize our data.
That said, with some clever algorithms, we can do a lot with lists (and arrays). To dive into these algorithms, we’re going to start with one that seems like it should be trivial: searching for an element. For example, given a list of email addresses, is a certain email address in the list? While a naive approach is to check every element in the list, the investigation into this question is more interesting than we might expect!