Fig. 1
Drag to turn · shift-drag to pan · click to break it down
Scroll to turn the page
Computer Science Principles · AP Computer Science Principles
bits, compression and information
Everything a computer holds, a number, a name, a photo, a song, is at bottom a pattern of bits.
A bit (short for binary digit) is either 0 or 1. Computing devices represent data digitally: the lowest-level components of any value are bits.
The figure counts in binary. Each tile is one bit, paper side for 0 and red side for 1, under its place value, 128, 64, 32, 16, 8, 4, 2, 1. Each step adds 1: the rightmost bit flips, and wherever a 1 flips to 0 the carry ripples one place left, as when 00000111 (7) becomes 00001000 (8).
Programs keep data values in variables, in lists of items, or as standalone constants, and pass them as input to procedures and get them back as output. Whatever the form, the values are stored as bits, and programs translate them into a form people can read.
This chapter is Big Idea 2 of AP Computer Science Principles, Data, 17–22% of the multiple-choice exam: binary numbers (2.1), data compression (2.2), extracting information from data (2.3) and using programs with data (2.4).
bits grouped into abstractions
A byte is 8 bits. On its own, a byte means nothing: its meaning depends on what the program reading it takes it to be.
Abstraction is the process of reducing complexity by focusing on the main idea. By hiding details irrelevant to the question at hand and bringing together related and useful details, abstraction lets you think about the idea instead of the bits.
Bits are grouped to represent abstractions, including (but not limited to) numbers, characters and color. The figure reads one byte, 01000001, three ways:
| read as | it means |
|---|---|
| a binary number | 65 |
| a character (ASCII and Unicode code 65) | the letter A |
| a pixel’s brightness, 0 (black) to 255 (white) | a dark gray |
So the same sequence of bits may represent different types of data in different contexts. A color image commonly stores three such numbers per pixel, one each for red, green and blue: 3 bytes, 24 bits.
place values, numbered from 0 on the right
Number bases, including binary and decimal, are used to represent data. Decimal (base 10) uses only the digits 0–9; binary (base 2) uses only 0 and 1.
As in decimal, a digit’s position sets its value: the numeric value is the digit times the place value of its position. The place value is the base raised to the power of the position, and positions are numbered from 0 at the rightmost, increasing by 1 to the left. In decimal, 305 = 3 × 102 + 0 × 101 + 5 × 100.
In binary each place is worth twice the one to its right. For 10110101:
| position | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| place value | 27 = 128 | 26 = 64 | 25 = 32 | 24 = 16 | 23 = 8 | 22 = 4 | 21 = 2 | 20 = 1 |
| bit | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Add the place values where the bit is 1: 128 + 32 + 16 + 4 + 1 = 181. A 0 bit adds nothing. The figure reads left to right; each 1 drops its place value into the sum.
take the largest place value that fits
To write a positive whole number in binary, work from the largest place value down: where the place value fits in what remains, write 1 and take it away; where it does not, write 0.
For 100 with eight bits:
| place value | remaining | fits? | bit | left after |
|---|---|---|---|---|
| 128 | 100 | no | 0 | 100 |
| 64 | 100 | yes | 1 | 36 |
| 32 | 36 | yes | 1 | 4 |
| 16 | 4 | no | 0 | 4 |
| 8 | 4 | no | 0 | 4 |
| 4 | 4 | yes | 1 | 0 |
| 2 | 0 | no | 0 | 0 |
| 1 | 0 | no | 0 | 0 |
So 100 = 01100100: 64 + 32 + 4 = 100. Leading zeros change nothing, so 01100100 and 1100100 are the same number.
A second method: divide by 2 again and again, and read the remainders from the last to the first. 100 ÷ 2 = 50 r 0; 50 ÷ 2 = 25 r 0; 25 ÷ 2 = 12 r 1; 12 ÷ 2 = 6 r 0; 6 ÷ 2 = 3 r 0; 3 ÷ 2 = 1 r 1; 1 ÷ 2 = 0 r 1. Read upward: 1100100.
In the figure the blue bar is what remains of 100; each 1 breaks its place value off the bar and turns its tile red.
and comparing binary numbers
One bit has 2 patterns. Each extra bit doubles the count: every old pattern once with a 0 in front, and again with a 1. So n bits have 2n patterns.
The figure builds them: 1 bit, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16. A byte has 28 = 256 patterns, the whole numbers 0 to 255. The largest n-bit number is all 1s: 2n − 1.
How many bits does it take to give each of 26 letters its own pattern? 24 = 16 is too few; 25 = 32 is enough: 5 bits.
Comparing and ordering. Give both numbers the same number of bits (pad with leading zeros) and scan from the left. The first position where they differ decides: the number with the 1 there is larger, because that one place value is worth more than all the places to its right together (2p > 2p − 1).
01101100 and 01011111 first differ at position 5, the 32s place, where the first has the 1: 108 > 95, whatever the bits after it.
overflow and round-off
In many programming languages, integers are represented by a fixed number of bits. That limits the range of integer values and the math done on them, and can cause overflow or other errors.
The figure’s counter (hypothetical) has 4 bits: it holds 0 to 15. Adding 1 to 15 (1111) needs a fifth bit; the carry has nowhere to go, and the counter shows 0. That is overflow.
Other languages provide an abstraction in which the size of integers is limited only by the size of the computer’s memory. The language on the exam reference sheet is one of these: its integers do not overflow.
Real numbers (with fractional parts) are also stored in a fixed number of bits, which limits their range and the math done on them and can cause round-off and other errors: some real numbers are stored only as approximations. With 3 fraction bits (the figure, hypothetical) only multiples of 1/8 = 0.125 exist; 0.1 is stored as 0.125, off by 0.025.
Real languages use many more bits, so the error is far smaller but not gone: in many of them 0.1 + 0.2 evaluates to 0.30000000000000004. The specific range limits for real numbers are outside the scope of the course and the exam.
a digital approximation
Analog data have values that change smoothly, rather than in discrete intervals, over time: the pitch and volume of music, the colors of a painting, the position of a sprinter during a race.
A computer stores bits, so it can only approximate analog data. Using digital data to approximate real-world analog data is an example of abstraction.
Analog data can be closely approximated digitally by sampling: measuring the values of the analog signal at regular intervals, called samples. Each sample is measured to work out the exact bits needed to store it.
The figure samples the same smooth signal twice. First 8 samples, each rounded to one of 4 levels (2 bits): 8 × 2 = 16 bits, a coarse staircase. Then 16 samples at 8 levels (3 bits): 16 × 3 = 48 bits, and the staircase hugs the curve more closely (its average distance from the signal falls by 43%).
More samples and more bits per sample give a closer approximation, and cost more bits to store or send. No finite number of samples makes it exact.
smaller, and back exactly
Data compression can reduce the size (number of bits) of transmitted or stored data. A lossless algorithm can usually reduce it while guaranteeing complete reconstruction of the original data.
The figure’s row has 20 pixels, one byte each: 20 bytes (hypothetical). Run-length encoding stores each run of one color as a count and a color: 7W 4R 6W 3B, 4 runs × 2 bytes = 8 bytes.
Decoding writes 7 white, 4 red, 6 white, 3 blue: exactly the original row, pixel for pixel. Nothing was lost, so fewer bits does not necessarily mean less information.
The amount of size reduction depends on both the amount of redundancy in the original data and the compression algorithm applied. Long runs compress well. A row that alternates colors every pixel (WRWRWR…) has 20 runs of 1: encoded, it takes 40 bytes, more than the 20 it started with.
smaller still, but only an approximation
A lossy algorithm can significantly reduce the number of bits stored or sent, but allows reconstruction of only an approximation of the original.
The figure’s 16 pixels (hypothetical brightnesses, a byte each) keep only the average of each pair: 8 bytes, half the size. Decoding gives each pixel its pair’s average: 14 of the 16 come back different, by up to 10. The gray ghosts are the originals, and nothing in the 8 bytes can bring them back: the pairs 200, 180 and 190, 190 both average to 190.
Lossy algorithms can usually reduce the number of bits more than lossless ones. Which to choose depends on the situation:
| what matters most | typically chosen |
|---|---|
| quality, or the ability to reconstruct the original exactly (a program file, a text document) | lossless |
| minimizing data size or transmission time (streaming video over a slow connection) | lossy |
patterns, and what they do not prove
Information is the collection of facts and patterns extracted from data. Data provide opportunities for identifying trends, making connections and addressing problems.
The figure plots 24 hypothetical days in a beach town: ice creams sold against sunburn cases. As one rises, so does the other: a strong correlation (the correlation coefficient r = 0.86; 1 would be a perfect straight line).
Ice cream does not cause sunburn. Color the days by temperature and the reason shows: the 7 hot days (red, 27 °C or more) bring both more ice cream and more sun. A correlation found in data does not necessarily indicate that a causal relationship exists; additional research is needed to understand the exact nature of the relationship.
Here the sales records alone could not show it. Often a single source does not contain the data needed to draw a conclusion, and data from several sources (sales, clinic visits, weather records) must be combined.
data about data
Metadata are data about data. The photo is the data; its metadata may include the date it was created, its file size, its dimensions and its tags.
Changes and deletions made to metadata do not change the primary data. In the figure the tag “sunset” is deleted; not one of the 64 pixels changes.
Metadata are used for finding, organizing and managing information: a photo library can list every photo taken on June 14, or every one tagged “beach”, without looking at a single pixel. Metadata increase the effective use of data by providing additional information, and allow data to be structured and organized.
On the exam, a scenario gives the data and metadata collected and asks what can be found. Ask what each field records. A library with only dates and tags can answer “how many photos were taken in June?” but not “where was this photo taken?”: no field records a place.
uniform, without changing the meaning
Data sets pose challenges regardless of size: the need to clean data, incomplete data, invalid data, and the need to combine data sources. The ability to process data depends on the capabilities of the users and their tools.
Depending on how data were collected, they may not be uniform. When users type into an open field, the way they abbreviate, spell or capitalize varies from user to user. The figure’s sign-up form (hypothetical) has 7 different spellings of 2 cities.
Cleaning makes the data uniform without changing their meaning, by replacing all equivalent abbreviations, spellings and capitalizations with the same word: 5 entries are rewritten, and 7 spellings become 2. Now a program counting sign-ups per city counts correctly.
Cleaning cannot invent what is missing. One row has no age (incomplete) and one gives −4 (invalid); they are flagged, to be checked or left out of the analysis, not guessed.
more data is not better data
Problems of bias are often created by the type or source of data being collected. Bias is not eliminated by simply collecting more data.
The figure’s poll (hypothetical) only reaches the left side of the population, say the readers of one website. In the whole population 41% hold the red opinion. After 30 answers the poll says 80%; after 60, 78%. Twice the answers, the same wrong picture, because every answer comes from the same unrepresentative source.
Size still matters: the size of a data set affects the amount of information that can be extracted from it. But large data sets are difficult to process using a single computer and may require parallel systems, many processors working on parts of the data at once.
Scalability of systems is an important consideration when working with data sets, as the computational capacity of a system affects how data sets can be processed and stored.
programs that process lists
Programs can be used to process data to acquire information. Search tools are useful for efficiently finding information, and data filtering systems are important tools for finding information and recognizing patterns in data.
Filtering keeps only the elements that meet a condition, such as keeping only the positive numbers from a list, or only the students who signed up for band:
data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } } The figure runs it with the running line in red. Each n is tested; only those with n > 0 are appended. positives ends as [4, 7, 3]; 0 is not kept, because 0 > 0 is false.
Transforming changes every element, such as doubling every element in a list, or adding a parent’s email to every student record. With doubled ← [] first:
FOR EACH n IN data { APPEND(doubled, 2 * n) } doubled ends as [8, −4, 14, 0, −10, 6]. Insight can come from translating and transforming data, and patterns can emerge when data are transformed using programs. Programmers also use programs to filter and clean data.
one number from many, and a chart
Combining or comparing data reduces many values to an answer: adding up a list of numbers, or finding the student with the highest GPA. Visualizing shows a data set as a chart, graph or other visual representation.
A club records sign-ups for 6 weeks (hypothetical): signups ← [12, 18, 9, 22, 15, 20].
total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most) It displays 96 22: 6 weeks, 96 sign-ups in all, 22 in the best week. most starts at signups[1], the first value, not 0, so it would still work if every value were negative. As it runs, the figure draws each week as a bar: the chart forms as the data are read.
Tables, diagrams, text and other visual tools can be used to communicate insight and knowledge gained from data. Programs such as spreadsheets help efficiently organize and find trends in information.
Programs are used in an iterative and interactive way: see the chart, ask a new question, filter or transform again. Combining data sources, clustering data (grouping similar items) and classifying data (sorting items into categories) are parts of using programs to gain insight and knowledge from data.