year 9 computer science data representation worksheet 5 answers

• No category

DATA REPRESENTATION (Worksheet)

Related documents

Add this document to collection(s)

You can add this document to your study collection(s)

Add this document to saved

You can add this document to your saved list

Suggest us how to improve StudyLib

(For complaints, use another form )

Input it if you want to receive answer

Computing, Computer Science, and Information Technology resources for GCSE, IGCSE, IB, and GCE A-Level

Teach computing.

Revision notes, activities, lesson plans, teaching ideas, and other resources for GCSE, A-Level, and IB Computer Science teachers and students.

Examples of Local Cryptocurrencies

Digital Money for Local Communities covers three examples of country-wide c...

Hash function A hash function takes arbitrary sized input data (e.g. a fil...

Cryptocurrencies vs regular currencies

What is Bitcoin and How Does it Work? is a high level overview of the Bitco...

Examples of Cryptocurrencies

Bitcoin is by far the most well known cryptocurrency. The Bitcoin website w...

Practice paper 3 exam questions

One of the drawbacks of the yearly case study is that there are no past p...

Emergency Management System Explainer Video

This short video gives an overview of some EMIS features. It includes many ...

Geographic Information Systems (GIS)

For some functionality, an EMIS may also be connected to a GIS (Geographic ...

Programming languages - from Scratch to machine code

The CS Field Guide has a very comprehensive guide to different types of pro...

Assembly language simulators

There are several assembly language simulators available for use online. Si...

1.1 Data Representation

Lesson resources.

In the data representation topic students will study the use of binary and hexadecimal number systems. This includes their roles in computing systems, such as the use of hexadecimal in colour definitions (such as in HTML and CSS). The final part of section 1.1 studies different ways data can be represented and interpreted, covering common file formats for images and sound.

Note: CIE have made some minor changes to this section of the syllabus for the 2016 examinations: students will need to convert binary numbers to decimal numbers, and vice versa (for positive numbers only).

1.1.1 Binary systems

Binary Tetris

Binary Tetris is a flash game designed to help teach students the binary number system. Players must flip bits to achieve the required number, or add up the bits to calculate the number being represented. I'd recommend asking students to turn their sound off before starting this!

This simple game challenges players to flip the right bits to create the specified number. The current total is displayed as bits are changed, and there is a timer to complete against. Students may be surprised to learn this game was created using Scratch.

Binary conversion activities

These two worksheets help students with decimal to binary conversion and vice versa . The activities were created by Gary Kacmarcik at the Computer Science & Engineering for K-12 site and are licensed under the Creative Commons Attribution-Share Alike 3.0 license.

Lesson - Data representation - binary

This download contains all lesson resources necessary to teach students binary. It includes explanations of the system and lesson activities.

This lesson is one of the many excellent resources provided under CC-NC-SA by Mr Colley .

Counting in binary

This handy PDF serves as a good summary sheet for students learning to count in binary. It covers decimal numbers from 0 to 63 (5 bits). It is good for GCSE and younger students, although it can be useful for older students too.

The sheet was created by Gary Kacmarcik at the excellent cse4k12 site and is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported License.

CS Field Guide - Data representation

CS Field Guide is an absolutely fantastic resource filled with material that is well written, clear,and accessible. Each section comes with highlighted key points, extension points, and even interactives to help understand the concepts. The interactives are excellent as teaching resources (many of them are linked here), while the notes themselves make excellent revision resources - particularly for GCSE.

This section covers all aspects of data representation - numbers, text, images, and instructions.

Base 2 calculator

This interactive doesn't actually calculate - instead it lets students flip bits in a byte and see the result calculated automatically. It is most useful when first explaining binary concepts to students.

Binary cards interactive

An online version of binary cards that can be switched on and off to produce a binary number. These are most useful when teaching younger children how binary numbers work.

1.1.2 Hexadecimal

Hexadecimal-binary matching game

This is a fun little matching pairs style game in which players must match decimal numbers with their hexadecimal equivalents. A good way of testing students' ability to quickly perform mental conversions. Click here to play .

Color Picker

A simple HTML colour picker. This one shows a colour wheel plus both the hexadecimal colour values and the RGB (Red, Green, Blue) values. This should help students understand how hexadecimal is used to represent different colours.

Binary to hexadecimal

A worksheet that explains the "divide into groups of 4" method of converting binary numbers to hexadecimal numbers.

This was created by Gary Kacmarcik at the Computer Science & Engineering for K-12 site - an excellent site which I recommend you visit. They are licensed under the Creative Commons Attribution-Share Alike 3.0 license.

Hexadecimal colour codes

Section 5.5.2 of this much bigger page on data representation covers the uses of hexadecimal numbers to represent colours in images. It explains the correlation between the hexadecimal digits and the number of bits available, and the effect the bit depth has on the appearance of the image. The excellent interactives really make the concept come alive and visually highlight these differences to students. A highly recommended resource.

Lesson - Data representation - hexadecimal

This download contains all lesson resources necessary to teach students base 16 (hexadecimal). It includes PowerPoint presentations that cover the number system and converting to denary and binary. There are also some nice hex table handouts for students who may be struggling to grasp the concepts. how sound is represented in binary.

This lesson is one of the many excellent resources provided under CC-NC-SA by Mr Colley . I've added PDF versions of the .pub versions found in the original download, for those who don't have Microsoft Publisher.

Counting in hex

Similar to the binary sheet, this handy document covers decimal numbers 0 to 63. It is useful for teaching students who are new to binary, or as a quick recap for those revising it. The sheet was created by Gary Kacmarcik at the excellent cse4k12 site and is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported License.

Binary and Hexadecimal starter activities

Two lesson starter, plenary, or homework activities are the binary crossword and the matching quiz . They test students' ability to read binary and hexadecimal, and convert between these systems and denary.

1.1.3 Data storage

Image Representation - Flash activity

This Flash activity lets students draw a simple bitmap image and represents it using a simple run-length encoding (RLE) algorithm in real time. Students can also important text representations of the compressed data and the application will draw the corresponding image. The web page is not in English but the application is still perfectly usable.

Image, audio, and text compression

This very comprehensive page from the Computer Science Field Guide has extensive but clear notes on lossless and lossy compression. The page is well written and designed for a high school audience, with easy to understand examples, video, and even interactive sections. There are also extension "Extra for Experts" sections. The page covers image compression, audio compression, and text compression.

Parity and Checksums activity

The card flip 'magic' game is a great idea from Computer Science Unplugged. The teacher sets up a grid of black/white cards and asks students to turn over one card without the teacher seeing. Using parity rules, the teacher is able to 'magically' determine which card the students turned over. This is a really fun game which demonstrates how simple techniques like odd/even partity can be used to solve significant problems.

The Computer Science Unplugged page has a range of support material: instructions for teachers, videos of the activity being performed, and a PDF download with extension activities and details about check digits in ISBNs.

Compression

A short Computerphile video which explains basic compression techniques and how they can be applied to text files and image files. The video also addresses the differences between lossy and lossless compression.

Lesson - Data representation - text

This download contains all lesson resources necessary to teach students how ASCII is used to representation text in a computer system. The download includes several fun activities where students have to uncover 'secret' messages using their understanding of binary and ASCII. There are different worksheets for students of different levels.

Lesson - Data representation - sound

This download contains all lesson resources necessary to teach students how sound is represented in binary. It includes PowerPoint presentations, worksheets, and sample sounds for students to play.

Text representation worksheets

Gary Kacmarcik at the excellent cse4k12 site has created a set of sheets for a lesson activity on text representation. The first sheet is an ASCII table and the other two sheets ask students to encode a text message and decode a message respectively. Note that students are expected to encode and decode using hexadecimal rather than binary (although they could easily be asked to use binary instead).

Pixel colour code viewer

This pixel viewer can help students understand how images are created and represented. Zooming right into the image reveals the RGB values of each pixel, shown in decimal.

Run Length Compression (RLE) interactive

This activity shows how a computer would represent a simple image when using Run Length Compression (RLE). Students can alter the image to see how the compression data would change. This is a good resource for helping students understand how lossless compression does not always result in significant size reduction.

JPEG Compression comparison

A simple interactive that compares a highly compressed JPEG image with a less compressed image. A slide lets you view different parts of the image. JPEG banding is particularly visible in the sky but less so in other areas - the reasons for this make for interesting classroom discussions.

RGB Colour matcher

A colour matching tool that asks users to play with the RGB sliders to match a specified colour. This is a great way to help students understand how red, green, and blue are mixed to produce colours. What makes this colour matcher stand out is that it also represents the colour values in binary (24 bit) at the bottom. This makes it a useful companion for tools like Pixelization (see elsewhere on this page).

Data representations

Curriculum > KS4 > Unit

This unit allows learners to gain the understanding and skills required for the data representation sections of the GCSE computer science exam. First, learners look at binary and hexadecimal numbering systems, how they work, and how to convert between bases. Then, learners explore different coding systems and find out how text, images, and sound are represented in computers. All lessons include worksheets to allow learners to explore each topic through practical application.

Learning graph

Summative assessment, summative answer.

• Lesson 1 What is representation? Log in to download
• Lesson 2 Number bases Log in to download
• Lesson 3 Binary addition Log in to download
• Lesson 4 Binary subtraction Log in to download
• Lesson 5 Binary shifts Log in to download
• Lesson 6 Signed binary integers Log in to download
• Lesson 7 Hexadecimal Log in to download
• Lesson 8 Representing text Log in to download
• Lesson 9 Unicode and file size calculation Log in to download
• Lesson 10 Representing bitmap images Log in to download
• Lesson 11 Bitmap file size calculation Log in to download
• Lesson 12 Representing sound Log in to download
• Lesson 13 Sound file size calculation Log in to download
• Lesson 14 Measurements of storage Log in to download
• Lesson 15 Lossy and lossless compression Log in to download
• Lesson 16 Run length encoding Log in to download
• Lesson 17 Huffman coding Log in to download
• Lesson 18 Summative assessment Log in to download

Help us make these resources better

Or email us at [email protected]

Data representation exercises

Exercises not as directly relevant to this year’s class are marked with ⚠️.

DATAREP-1. Sizes and alignments

QUESTION DATAREP-1A. True or false: For any non-array type X, the size of X ( sizeof(X) ) is greater than or equal to the alignment of type X ( alignof(X) ).

True. This also mostly true for arrays. The exception is zero-length arrays: sizeof(X[0]) == 0 , but alignof(X[0]) == alignof(X) .

QUESTION DATAREP-1B. True or false: For any type X, the size of struct Y { X a; char newc; } is greater than the size of X.

QUESTION DATAREP-1C. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of struct X , given:

struct X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; char newc; };

False (example: A1 = int , A2 = char )

QUESTION DATAREP-1D. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of union X , given:

union X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; };

False (if n = 1 )

QUESTION DATAREP-1E. Assume that structure struct Y { ... } contains K char members and M int members, with K ≤ M , and nothing else. Write an expression defining the maximum sizeof(struct Y) .

QUESTION DATAREP-1F. You are given a structure struct Z { T1 a; T2 b; T3 c; } that contains no padding. What does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

QUESTION DATAREP-1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

• struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
• unsigned short[1]

#6 < #1 < #4 < #2 < #3 < #5

DATAREP-2. Expressions

QUESTION DATAREP-2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86-32 machine: a 32-bit architecture in which pointers are 32 bits long.

• sizeof(&m)
• 16 >> 2

1—5; 2—7; 3—8; 4—6 1—5 is easy. m + ~m + 1 == m + (-m) == 0 , and m & ~m == 0 , giving us 3—8. Now what about the others? m & -m (#3) is either 0 or a power of 2, so it cannot be -1 (#2). The remaining possiblities are m and 1 . If (m & -m) == m , then the remaining pair would be 1 and -1, which clearly doesn’t work. Thus m & -m matches with 1, and m == -1 .

DATAREP-3. Hello binary

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

Examples : The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION DATAREP-3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION DATAREP-3B. Where is 12 located horizontally?

QUESTION DATAREP-3C. Where is 255 located vertically?

DATAREP-4. Hello memory

Shintaro Tsuji wants to represent the image of Question DATAREP-3 in computer memory. He stores it in an array of 16-bit unsigned integers:

Row Y of the image is stored in integer cute[Y] .

QUESTION DATAREP-4A. What is sizeof(cute) , 2, 16, 32, or 64?

QUESTION DATAREP-4B. printf("%d\n", cute[0]); prints 16384 . Is Shintaro’s machine big-endian or little-endian?

Little-endian

DATAREP-5. Hello program

Now that Shintaro has represented the image in memory as an array of unsigned short objects, he can manipulate the image using C. For example, here’s a function.

Running swap produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

For each function, what image does that function create?

QUESTION DATAREP-5A.

H. The code flips all bits in the input.

QUESTION DATAREP-5B.

QUESTION DATAREP-5C.

The following programs generated the other images. Can you match them with their images?

f3 —I; f4 —B; f5 —C; f6 —F; f7 —G; f8 —A; f9 —E

DATAREP-6. Memory regions

Consider the following program:

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. We recommend you draw a picture of the state setup creates.

QUESTION DATAREP-6A. Assume that (uintptr_t) a == 0x8300000 , and that malloc returns increasing addresses. Match each address to the most likely expression with that address value. The expressions are evaluated within the context of main . You will not reuse an expression.

1—D; 2—C; 3—E; 4—B; 5—A Since p has automatic storage duration, it is located on the stack, giving us 5—A. The global variable has static storage duration, and so does its component global.y ; so the pointer &global.y has an address that is below all heap-allocated pointers. This gives us 2—C. The remaining expressions go like this: global.y == e ; p.y == &e[1] , so *p.y == e[1] == (int) &d[100000] , and (int *) *p.y == &d[100000] ; p.x == g , so p.x[0] == g[0] == *g == c , and *p.x[0] == *c == (int) a . Address #4 has value 0x8300000, which by assumption is a ’s address; so 4—B. Address #3 is much larger than the other heap addresses, so 3—E. This leaves 1—D.

DATAREP-7. ⚠️ Garbage collection ⚠️

⚠️ Here is the top-level function for the conservative garbage collector we wrote in class.

This garbage collector is not correct because it doesn’t capture all memory roots.

Consider the program from the previous section, and assume that an object is reachable if do_stuff can access an address within the object via variable references and memory dereferences without casts or pointer arithmetic . Then:

QUESTION DATAREP-7A. Which reachable objects will m61_collect() free? Circle all that apply.

b , f . The collector searches the stack for roots. This yields just the values in struct ptrs p (the only pointer-containing variable with automatic storage duration at the time m61_collect is called). The objects directly pointed to by p are g and e . The collector then recursively marks objects pointed to by these objects. From g , it finds c . From e , it finds nothing. Then it checks one more time. From c , it finds the value of a ! Now, a is actually not a pointer here—the type of *c is int —so by the definition above, a is not actually reachable. But the collector doesn’t know this. Putting it together, the collector marks a , c , e , and g . It won’t free these objects; it will free the others ( b , d , and f ). But b and f are reachable from global .

QUESTION DATAREP-7B. Which unreachable objects will m61_collect() not free? Circle all that apply.

QUESTION DATAREP-7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? Circle all that apply.

• C is generally slower than other languages.
• Conservative garbage collectors must search all reachable memory for pointers. Precise garbage collectors can ignore values that do not contain pointers, such as large character buffers.
• C programs generally use the heap more than programs in other languages.
• None of the above.

DATAREP-8. Memory errors

The following function constructs and returns a lower-triangular matrix of size N . The elements are random 2-dimensional points in the unit square. The matrix is represented as an array of pointers to arrays.

This code is running on an x86- 32 machine ( size_t is 32 bits , not 64). You may assume that the machine has enough free physical memory and the process has enough available virtual address space to satisfy any memory allocation request.

QUESTION DATAREP-8A. Give a value of N so that, while make_random_lt_matrix(N) is running, no new fails, but a memory error (such as a null pointer dereference or an out-of-bounds dereference) happens on Line A. The memory error should happen specifically when i == 1 .

(This problem is probably easier when you write your answer in hexadecimal.)

We are asked to produce a value of N so that no memory error happens on Line A when i == 0 , but a memory error does happen when i == 1 . So reason that through. What memory errors could happen on Line A if malloc() returns non- nullptr ? There’s only one memory operation, namely the dereference m[i] . Perhaps this dereference is out of bounds. If no memory error happens when i == 0 , then a m[0] dereference must not cause a memory error. So the m object must contain at least 4 bytes. But a memory error does happen on Line A when i == 1 . So the m object must contain less than 8 bytes. How many bytes were allocated for m ? sizeof(point2_vector) * N == sizeof(point2 *) * N == 4 * N . So we have: (4 * N) ≥ 4 (4 * N) < 8 It seems like the only possible answer is N == 1 . But no, this doesn’t cause a memory error, because the loop body would never be executed with i == 1 ! The key insight is that the multiplications above use 32-bit unsigned computer arithmetic. Let’s write N as X + 1 . Then these inequalities become: 4 ≤ 4 * (X + 1) = 4 * X + 4 < 8 0 ≤ (4 * X) < 4 (Multiplication distributes over addition in computer arithmetic.) What values of X satisfy this inequality? It might be easier to see if we remember that multiplication by powers of two is equivalent to shifting: 0 ≤ (X << 2) < 4 The key insight is that this shift eliminates the top two bits of X . There are exactly four values for X that work: 0 , 0x40000000 , 0x80000000 , and 0xC0000000 . For any of these, 4 * X == 0 in 32-bit computer arithmetic, because 4× X = 0 (mod 2 32 ) in normal arithmetic. Plugging X back in to N , we see that N ∈ {0x40000001, 0x80000001, 0xC0000001} . These are the only values that work. Partial credit was awarded for values that acknowledged the possibility of overflow.

QUESTION DATAREP-8B. Give a value of N so that no new fails, and no memory error happens on Line A, but a memory error does happen on Line B.

If no memory error happens on Line A, then N < 2 30 (otherwise overflow would happen as seen above). But a memory error does happen on Line B. Line B dereferences m[i][j] , for 0 ≤ j ≤ i ; so how big is m[i] ? It was allocated on Line A with size `sizeof(point2) (i + 1) == 2 * sizeof(double) * (i + 1) == 16 * (i + 1) . If i + 1 ≥ 2<sup>32</sup> / 16 = 2<sup>28</sup>, this multiplication will overflow. Since i < N , we can finally reason that any N greater than or equal to 2<sup>28</sup> = 0x10000000 and less than 2<sup>30</sup> = 0x40000000` will cause the required memory error.

DATAREP-9. Data representation

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-9A. Arrange the following values in increasing numeric order. Assume that x is an int with value 8192.

A possible answer might be “a < b < c = d < e < f < g < h.”

h < a = d = f < b < c < e < g

For each of the remaining questions, write one or more arguments that, when passed to the provided function, will cause it to return the integer 61 (which is 0x3d hexadecimal ). Write the expected number of arguments of the expected types.

QUESTION DATAREP-9B.

QUESTION DATAREP-9C.

"61"

QUESTION DATAREP-9D. Your answer should be different from the previous answer.

" 0x3d" , " 61 " , etc.

QUESTION DATAREP-9E. For this problem, you will also need to define a global variable. Give its type and value.

This code was compiled from: int f4 ( int a, int b) { extern unsigned char y; return (a & 5 ) * 2 + b - y; } A valid solution is a =0, b =61, unsigned char y =0.

DATAREP-10. Sizes and alignments

QUESTION DATAREP-10A. Use the following members to create a struct of size 16, using each member exactly once, and putting char a first; or say “impossible” if this is impossible.

• char a; (we’ve written this for you)
• unsigned char b;

QUESTION DATAREP-10B. Repeat Part A, but create a struct with size 12.

abdc, acbd, acdb, adbc, adcb, …

QUESTION DATAREP-10C. Repeat Part A, but create a struct with size 8.

QUESTION DATAREP-10D. Consider the following structs:

Give definitions for T, U, and V so that there is one byte of padding in struct x after x2 , and two bytes of padding in struct y after y1 .

Example: T = short[2] , U = char , V = int

DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

• free(nullptr) is an error.
• malloc(0) can never return nullptr .

False, False

QUESTION DATAREP-11B. Give values for sz and nmemb so that calloc(sz, nmemb) will always return nullptr (on a 32-bit x86 machine), but malloc(sz * nmemb) might or might not return null.

(size_t) -1, (size_t) -1 —anything that causes an overflow

Consider the following 8 statements. ( p and q have type char* .)

• q = nullptr;
• p = (char*) malloc(12);
• q = (char*) malloc(8);

QUESTION DATAREP-11C. Put the statements in an order that would execute without error or evoking undefined behavior. Memory leaks count as errors. Use each statement exactly once. Sample answer: “abcdefgh.”

cdefghab (and others). Expect “OK”

QUESTION DATAREP-11D. Put the statements in an order that would cause one double-free error, and no other error or undefined behavior (except possibly one memory leak). Use each statement exactly once.

efghbcad (and others). Expect “double-free + memory leak”

QUESTION DATAREP-11E. Put the statements in an order that would cause one memory leak (one allocated piece of memory is not freed), and no other error or undefined behavior. Use each statement exactly once.

efghadbc (and others). Expect “memory leak”

QUESTION DATAREP-11F. Put the statements in an order that would cause one boundary write error, and no other error or undefined behavior. Use each statement exactly once.

eafhcgbd (and others). Expect “out of bounds write”

DATAREP-12. Pointers and debugging allocators

You are debugging some students’ m61 code from Problem Set 1. The codes use the following metadata:

Their linked-list manipulations in m61_malloc are similar.

But their linked-list manipulations in m61_free differ.

Alice’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next != nullptr ) { m -> next -> prev = m -> prev; } if (m -> prev == nullptr ) { mhead = nullptr ; } else { m -> prev -> next = m -> next; } ... }

Bob’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } ... }

Chris’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; m -> next -> prev = m -> prev; m -> prev -> next = m -> next; ... }

Donna’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } else { mhead = m -> next; } ... }

You may assume that all code not shown is correct.

QUESTION DATAREP-12A. Whose code will segmentation fault on this input? List all students that apply.

QUESTION DATAREP-12B. Whose code might report something like “ invalid free of pointer [ptr1], not allocated ” on this input? (Because a list traversal starting from mhead fails to find ptr1 .) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12C. Whose code would improperly report something like “ LEAK CHECK: allocated object [ptr1] with size 1 ” on this input? (Because the mhead list appears not empty, although it should be.) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12D. Whose linked-list code is correct for all inputs? List all that apply.

DATAREP-13. Arena allocation

Chimamanda Ngozi Adichie is a writing a program that needs to allocate and free a lot of nodes, where a node is defined as follows:

She uses an arena allocator variant. Here’s her code.

QUESTION DATAREP-13A. True or false?

• This allocator never has external fragmentation.
• This allocator never has internal fragmentation.

QUESTION DATAREP-13B. Chimamanda’s frenemy Paul Auster notices that if many nodes are allocated right in a row, every 1024th allocation seems much more expensive than the others. The reason is that every 1024th allocation initializes a new group, which in turn adds 1024 nodes to the free list. Chimamanda decides instead to allow a single element of the free list to represent many contiguous free nodes . The average allocation might get a tiny bit slower, but no allocation will be much slower than average. Here’s the start of her idea:

Complete this function by writing code to replace // ??? .

if (n -> key == 1 ) { a -> frees = n -> right; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; a -> frees -> right = n -> right; } Another solution: if (n -> right) { a -> frees = n -> right; } else if (n -> key == 1 ) { a -> frees = NULL ; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; }

QUESTION DATAREP-13C. Write a node_free function that works with the node_alloc function from the previous question.

void node_free (arena * a, node * n) { n -> right = a -> frees; n -> key = 1 ; a -> frees = n; } Or, if you use the solution above: void node_free (arena * a, node * n) { n -> right = a -> frees; a -> frees = n; }

QUESTION DATAREP-13D. Complete the following new function.

arena_group * node_find_group (arena * a, node * n) { for (arena_group * g = a -> groups; g; g = g -> next_group) { if ((uintptr_t) & g -> nodes[ 0 ] <= (uintptr_t) n && (uintptr_t) n <= (uintptr_t) & g -> nodes[ 1023 ]) { return g; } } return nullptr ; }

QUESTION DATAREP-13E. Chimamanda doesn’t like that the node_find_group function from part D takes O ( G ) time, where G is the number of allocated arena_groups. She remembers a library function that might help, posix_memalign :

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr . The address of the allocated memory will be a multiple of alignment , which must be a power of two and a multiple of sizeof(void*) . ...

“Cool,” she says, “I can use this to speed up node_find_group !” She now allocates a new group with the following code:

Given this allocation strategy, write a version of node_find_group that takes O (1) time.

arena_group * node_find_group (arena * a, node * n) { uintptr_t n_addr = (uintptr_t) n; return (arena_group * ) (n_addr - n_addr % 32768 ); }

DATAREP-14. Data representation

Sort the following expressions in ascending order by value, using the operators <, =, >. For example, if we gave you:

• int B = 0x6;

you would write C < A = B .

• unsigned char a = 0x191;
• char b = 0x293;
• unsigned long c = 0xFFFFFFFF;
• int d = 0xFFFFFFFF;
• int e = d + 3;
• size_t g = sizeof(*s) (given short *s )
• long h = 256;
• i = 0b100000000000000000000000000000000000 (binary)
• unsigned long j = 0xACE - 0x101;

b < d < e = g < a < h < j < c < f < i

DATAREP-15. Memory

For the following questions, select the part(s) of memory from the list below that best describes where you will find the object.

• between the heap and the stack
• in a read-only data segment
• in a text segment starting at address 0x08048000
• in a read/write data segment
• in a register

Assume the following code, compiled without optimization.

QUESTION DATAREP-15A. The value 0xdeadbeef, when we are returning from main.

7, in a register

QUESTION DATAREP-15B. The variable maxitems

4, in a read-only data segment

QUESTION DATAREP-15C. The structure s

6, in a read/write data segment

QUESTION DATAREP-15D. The structure at sp[9]

QUESTION DATAREP-15E. The variable u

2, stack, or 7, in a register

QUESTION DATAREP-15F. main

5, in a text segment starting at address 0x08048000

QUESTION DATAREP-15G. printf

3, between the heap and the stack

QUESTION DATAREP-15H. argc

QUESTION DATAREP-15I. The number the user enters

QUESTION DATAREP-15J. The variable L

DATAREP-16. Memory and pointers

⚠️ This question may benefit from Unit 4, kernel programming. ⚠️

If multiple processes are sharing data via mmap , they may have the file mapped at different virtual addresses. In this case, pointers to the same object will have different values in the different processes. One way to store pointers in mmapped memory so that multiple processes can access them consistently is using relative pointers. Rather than storing a regular pointer, you store the offset from the beginning of the mmapped region and add that to the address of the mapping to obtain a real pointer. An alternative representation is called self-relative pointers. In this case, you store the difference in address between the current location (i.e., the location containing the pointer) and the location to which you want to point. Neither representation addresses pointers between the mmapped region and the rest of the address space; you may assume such pointers do not exist.

QUESTION DATAREP-16A. State one advantage that relative pointers have over self-relative pointers.

The key thing to understand is that both of these approaches use relative pointers and both can be used to solve the problem of sharing a mapped region among processes that might have the region mapped at different addresses. Possible advantages: Within a region, you can safely use memcpy as moving pointers around inside the region does not change their value. If you copy a self relative pointer to a new location, its value has to change. That is, imagine that you have a self-relative pointer at offset 4 from the region and it points to the object at offset 64 from the region. The value of the self relative pointer is 60. If I copy that pointer to the offset 100 from the region, I have to change it to be -36. If you save the region as a uintptr_t or a char * , then you can simply add the offset to the region; self-relative-pointers will always be adding/subtracting from the address of the location storing the pointer, which may have a type other than char * , so you'd need to cast it before performing the addition/subtraction. You can use a larger region: if we assume that we have only N bits to store the pointer, then in the base+offset model, offset could be an unsigned value, which will be larger than the maximum offset possible with a signed pointer, which you need for the self-relative case. That is, although the number of values that can be represented by signed and unsigned numbers differs by one, the implementation must allow for a pointer from the beginning of the region to reference an item at the very last location of the region -- thus, your region size is limited by the largest positive number you can represent.

QUESTION DATAREP-16B. State one advantage that self-relative pointers have over relative pointers.

You don't have to know the address at which the region is mapped to use them. That is, given a location containing a self-relative pointer, you can find the target of that pointer.

For the following questions, assume the following setup:

QUESTION DATAREP-16C. Propose a type for TYPE1 and give 1 sentence why you chose that type.

A good choice is ptrdiff_t , which represents differences between pointers. Other reasonable choices include uintptr_t and unsigned long .

QUESTION DATAREP-16D. Write a C expression to generate a (properly typed) pointer to the element referenced by the r_next field of ll1 .

(ll1*) (region + node1.r_next)

QUESTION DATAREP-16E. Propose a type for TYPE2 and give 1 sentence why you chose that type.

The same choices work; again ptrdiff_t is best.

QUESTION DATAREP-16F. Write a C expression to generate a (properly typed) pointer to the element referenced by the sr_next field of ll2 .

(ll2*) ((char*) &node2.sr_next + node2.sr_next)

DATAREP-17. Data representation: Allocation sizes

How much user-accessible space is allocated on the stack and/or the heap by each of the following statements? Assume x86-64.

QUESTION DATAREP-17A. union my_union { ... };

0; this declares the type , not any object

QUESTION DATAREP-17B. void* p = malloc(sizeof(char*));

16: 8 on the heap plus 8 on the stack

QUESTION DATAREP-17C. my_union u;

16 (on the stack)

QUESTION DATAREP-17D. my_union* up = &u;

8 (on the stack)

DATAREP-18. Data representation: ENIAC

Professor Kohler has been developing Eddie’s NIfty Awesome Computer (ENIAC). When he built the C compiler for ENIAC, he assigned the following sizes and alignments to C’s fundamental data types. (Assume that every other fundamental type has the same size and alignment as one of these.)

QUESTION DATAREP-18A. This set of sizes is valid: it obeys all the requirements set by C’s abstract machine. Give one different size assignment that would make the set as a whole invalid.

Some examples: sizeof(char) = 0 ; sizeof(char) = 2 ; sizeof(short) = 8 (i.e., longer than int ); sizeof(int) = 2 (though not discussed in class, turns out that C++ requires ints are at least 2 bytes big); etc.

QUESTION DATAREP-18B. What alignment must the ENIAC malloc guarantee?

For the following two questions, assume the following struct on the ENIAC:

QUESTION DATAREP-18C. What is sizeof(struct s) ?

f1 is 7 bytes. f2 is 16 bytes with 16-byte alignment, so add 9B padding. f3 is 4 bytes (and is already aligned). f4 is 8 bytes with 8-byte alignment, so add 4B padding. That adds up to 7 + 9 + 16 + 4 + 4 + 8 = 16 + 16 + 16 = 48 bytes. That’s a multiple of the structure’s alignment, which is 16, so no need for any end padding.

QUESTION DATAREP-18D. What is alignof(struct s) ?

The remaining questions refer to this structure definition:

Indicate for each statement whether the statement is always true, possibly true, or never true on the ENIAC.

QUESTION DATAREP-18E : sizeof(outer) > sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18F : sizeof(outer) is a multiple of sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18G : alignof(outer) > alignof(struct inner) (Always / Possibly / Never)

QUESTION DATAREP-18H : sizeof(outer) - sizeof(inner) < 4 (Always / Possibly / Never)

QUESTION DATAREP-18I : sizeof(outer) - sizeof(inner) > 32 (Always / Possibly / Never)

QUESTION DATAREP-18J : alignof(inner) == 2 (Always / Possibly / Never)

DATAREP-19. Undefined behavior

Which of the following expressions, instruction sequences, and code behaviors cause undefined behavior? For each question, write Defined or Undefined. (Note that the INT_MAX and UINT_MAX constants have types int and unsigned , respectively.)

QUESTION DATAREP-19A. INT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19B. UINT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19C.

(Defined / Undefined)

Defined (only C++ programs can have undefined behavior; the behavior of x86-64 instructions is always defined)

QUESTION DATAREP-19D. Failed memory allocation, i.e., malloc returns nullptr (Defined / Undefined)

QUESTION DATAREP-19E. Use-after-free (Defined / Undefined)

QUESTION DATAREP-19F. Here are two functions and a global variable:

C’s undefined behavior rules would allow an aggressive optimizing compiler to simplify the code generated for f . Fill in the following function with the simplest C code you can, under the constraint that an aggressive optimizing compiler might generate the same object code for f and f_simplified .

return i * 2;

DATAREP-20. Bit manipulation

It’s common in systems code to need to switch data between big-endian and little-endian representations. This is because networks represent multi-byte integers using big-endian representation, whereas x86-family processors store multi-byte integers using little-endian representation.

QUESTION DATAREP-20A. Complete this function, which translates an integer from big-endian representation to little-endian representation by swapping bytes. For instance, big_to_little(0x01020304) should return 0x04030201 . Your return statement must refer to the u.c array, and must not refer to x . This function is compiled on x86-64 Linux (as every function is unless we say otherwise).

return (u.c[ 0 ] << 24 ) | (u.c[ 1 ] << 16 ) | (u.c[ 2 ] << 8 ) | u.c[ 3 ];

QUESTION DATAREP-20B. Complete the function again, but this time write a single expression that refers to x (you may refer to x multiple times, of course).

return ((x & 0xFF ) << 24 ) | ((x & 0xFF00 ) << 8 ) | ((x & 0xFF0000 ) >> 8 ) | (x >> 24 );

QUESTION DATAREP-20C. Now write the function little_to_big , which will translate a little-endian integer into big-endian representation. You may introduce helper variables or even call big_to_little if that’s helpful.

return big_to_little (x);

DATAREP-21. Computer arithmetic

Bitwise operators and computer arithmetic can represent vectors of bits, which in turn are useful for representing sets . For example, say we have a function bit that maps elements to distinct bits; thus, bit(X) == (1 << i) for some i . Then a set {X0, X1, X2, …, Xn} can be represented as bit(X0) | bit(X1) | bit(X2) | … | bit(Xn) . Element Xi is in the set with integer representation z if and only if (bit(Xi) & z) != 0 .

QUESTION DATAREP-21A. What is the maximum number of set elements that can be represented in a single unsigned variable on an x86 machine?

QUESTION DATAREP-21B. Match each set operation with the C operator(s) that could implement that operation. (Complement is a unary operation.)

intersection & equality == complement ~ union | toggle membership ^

QUESTION DATAREP-21C. Complete this function, which should return the set difference between the sets with representations a and b . This is the set containing exactly those elements of set a that are not in set b .

Any of these work: return a & ~ b; return a - (a & b); return a & ~ (a & b);

QUESTION DATAREP-21D. Below we’ve given a number of C++ expressions, some of their values, and some of their set representations for a set of elements. For example, the first row says that the integer value of expression 0 is just 0, which corresponds to an empty set. Fill in the blanks. This will require figuring out which bits correspond to the set elements A , B , C , and D , and the values for the 32-bit int variables a , x , and s . No arithmetic operation overflows; abs(x) returns the absolute value of x (that is, x < 0 ? -x : x ).

Expression e Integer value Represented set 0 0 {} a == a 1 {A} (unsigned) ~a < (unsigned) a 1 {A} a < 0 1 {A} (1 << (s/2)) - 1 15 {A,B,C,D} a * a 4 {C} abs(a) 2 {D} x & (x - 1) 0 {} x - 1 3 {A,D} x 4 {C} s 8 {B}

DATAREP-22. Bit Tac Toe

Brenda Bitdiddle is implementing tic-tac-toe using bitwise arithmetic. (If you’re unfamiliar with tic-tac-toe, see below.) Her implementation starts like this:

Each position on the board is assigned a distinct bit.

Tic-tac-toe, also known as noughts and crosses, is a simple paper-and-pencil game for two players, X and O. The board is a 3x3 grid. The players take turns writing their symbol (X or O) in an empty square on the grid. The game is won when one player gets their symbol in all three squares in one of the rows, one of the columns, or one of the two diagonals. X goes first; played perfectly, the game always ends in a draw. You may access the Wikipedia page for tic-tac-toe .

QUESTION DATAREP-22A. Brenda’s current code doesn’t check whether a move reuses a position. Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3.

Lots of people misinterpreted this to mean the player reused their own position and ignored the other player. That mistake was allowed with no points off. The code below checks whether any position was reused by either player. if ((b -> moves[XS] | b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[XS] | b -> moves[OS] | ttt_values[row][col]) == (b -> moves[XS] | b -> moves[OS])) { return - 1 ; } OR if ((b -> moves[XS] + b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[p] ^ ttt_values[row][col]) < b -> moves[p]) { return - 1 ; } etc.

QUESTION DATAREP-22B. Complete the following function. You may use the following helper function:

• int popcount(unsigned n) Return the number of 1 bits in n . (Stands for “population count”; is implemented on recent x86 processors by a single instruction, popcnt .)

For full credit, your code should consist of a single “ return ” statement with a simple expression, but for substantial partial credit write any correct solution.

return popcount (b -> moves[XS] | b -> moves[OS]);

QUESTION DATAREP-22C. Write a simple expression that, if nonzero, indicates that player XS has a win on board b across the main diagonal (has marks in positions 0,0 , 1,1 , and 2,2 ).

(b -> moves[XS] & 0x421 ) == 0x421

Lydia Davis notices Brenda’s code and has a brainstorm. “If you use different values,” she suggests, “it becomes easy to detect any win.” She suggests:

QUESTION DATAREP-22D. Repeat part A for Lydia’s values: Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3 in Brenda’s code.

The same answers as for part A work.

QUESTION DATAREP-22E. Repeat part B for Lydia’s values: Use popcount to complete tictactoe_nmoves .

Either of: return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777 ); return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777000 );

QUESTION DATAREP-22F. Complete the following function for Lydia’s values. For full credit, your code should consist of a single “ return ” statement containing exactly two constants, but for substantial partial credit write any correct solution.

return (b -> moves[p] + 0x11111111 ) & 0x88888888 ; // Another amazing possibility (Allen Chen and others): return b -> moves[p] & (b -> moves[p] << 1 ) & (b -> moves[p] << 2 );

DATAREP-23. Memory and Pointers

Two processes are mapping a file into their address space. The mapped file contains an unsorted linked list of integers. As the processes cannot ensure that the file will be mapped at the same virtual address, they use relative pointers to link elements in the list. A relative pointer holds not an address, but an offset that user code can use to calculate a true address. Our processes define the offset as relative to the start of the file.

Thus, each element in the linked list is represented by the following structure:

offset == (size_t) -1 indicates the end of the list. Other offset values represent the position of the next item in the list, calculated relative to the start of the file.

QUESTION DATAREP-23A. Write a function to find an item in the list. The function's prototype is:

The mapped_file parameter is the address of the mapped file data; the list parameter is a pointer to the first node in the list; and the value parameter is the value for which we are searching. The function should return a pointer to the linked list element if the value appears in the list or nullptr if the value is not in the list.

ll_node * find_element ( void * mapped_file, ll_node * list, int value) { while ( 1 ) { if (list -> value == value) return list; if (list -> offset == (size_t) - 1 ) return NULL ; list = (ll_node * ) (( char * ) mapped_file + list -> offset); } }

DATAREP-24. Integer representation

Write the value of the variable or expression in each problem, using signed decimal representation.

For example, if we gave you:

• int i = 0xA;
• int j = 0xFFFFFFFF;

you would write A) 10 B) -1.

QUESTION DATAREP-24A. int i = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

2 16 - 1 or 65535

QUESTION DATAREP-24B. short s = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

QUESTION DATAREP-24C. unsigned u = 1 << 10;

1024 or 2 10

QUESTION DATAREP-24D. ⚠️ From WeensyOS: unsigned long l = PTE_P | PTE_U;

QUESTION DATAREP-24E. int j = ~0;

QUESTION DATAREP-24F. ⚠️ From WeensyOS: sizeof(x86_64_pagetable);

4096 or 2 12

QUESTION DATAREP-24G. Given this structure:

This expression: sizeof(ps);

TRICK QUESTION! 8

QUESTION DATAREP-24H. Using the structure above: sizeof(*ps);

QUESTION DATAREP-24I. unsigned char u = 0xABC;

0xBC == 11*16 + 12 == 160 + 16 + 12 == 188

QUESTION DATAREP-24J. signed char c = 0xABC;

0xBC has most-significant bit on, so the value as a signed char is less than zero. We seek x so that 0xBC + x == 0x100 . The answer is 0x44: 0xBC + 4 == 0xC0 , and 0xC0 + 0x40 == 0x100 . So −0x44 == −4*16 − 4 == −68 .

DATAREP-25. Data representation

In gdb, you observe the following values for a set of memory locations.

For each C expression below, write its value in hexadecimal. For example, if we gave you:

the answer would be 0xa0 .

Assume the following structure and union declarations and variable definitions.

QUESTION DATAREP-25A. cp[4] =

QUESTION DATAREP-25B. cp + 7 =

0x100001027

QUESTION DATAREP-25C. s1 + 1 =

0x100001038

QUESTION DATAREP-25D. s1->i =

0xd3c2b1a0 (-742215264)

QUESTION DATAREP-25E. sizeof(s1) =

QUESTION DATAREP-25F. &s2->s =

0x100001028

QUESTION DATAREP-25G. &u->s =

0x100001020

QUESTION DATAREP-25H. s1->l =

0x9f8e7d6c5b4a3928 (-6949479270644565720)

QUESTION DATAREP-25I. s2->s.s =

0xf201 (-3583)

QUESTION DATAREP-25J. u->l =

0x1706f5e4d3c2b1a0 (1659283875886707104)

DATAREP-26. Sizes and alignments

Here’s a test struct with n members. Assume an x86-64 machine, where each Ti either is a basic x86-64 type (e.g., int , char , double ) or is a type derived from such types (e.g., arrays, structs, pointers, unions, possibly recursively), and assume that ai ≤8 for all i .

In these questions, you will compare this struct with other structs that have the same members, but in other orders.

QUESTION DATAREP-26A. True or false: The size of struct test is minimized when its members are sorted by size. In other words, if s1 ≤ s2 ≤…≤ sn , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample (i.e., concrete types for T1 , …,  Tn that do not minimize sizeof(struct test) ).

False. T1 = char , T2 = int , T3 = char[5]

QUESTION DATAREP-26B. True or false: The size of struct test is minimized when its members are sorted by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample.

True. Padding only occurs between objects with different alignments, and is limited by the second alignment; sorting by alignment therefore minimizes padding.

QUESTION DATAREP-26C. True or false: The alignment of struct test is minimized when its members are sorted in increasing order by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then alignof(struct test) is less than or equal to the struct alignment for any other member order.

True. It’s all the same; alignment is max alignment of every component, and is independent of order.

QUESTION DATAREP-26D. What is the maximum number of bytes of padding that struct test could contain for a given n ? The answer will be a pretty simple formula involving n . (Remember that ai ≤8 for all i .)

Alternating char and long gives the most padding, which is 7*(n/2) when n is even and 7*(n+1)/2 otherwise.

QUESTION DATAREP-26E. What is the minimum number of bytes of padding that struct test could contain for a given n ?

DATAREP-27. Undefined behavior

QUESTION DATAREP-27A. Sometimes a conforming C compiler can assume that a + 1 > a , and sometimes it can’t. For each type below, consider this expression:

and say whether the compiler:

• Must reject the expression as a type error.
• May assume that the expression is true (that a + (int) 1 > a for all a ).
• Must not assume that the expression is true.
• unsigned char a
• struct {int m;} a

1—May assume; 2—Must not assume; 3—May assume; 4—May assume (in fact due to integer promotion, this statement really is always true, even in mathematical terms); 5—Must reject.

QUESTION DATAREP-27B. The following code checks its arguments for sanity, but not well: each check can cause undefined behavior.

Rewrite these checks to avoid all undefined behavior. You will likely add one or more casts to uintptr_t . For full credit, write each check as a single comparison (no && or || , even though the current ptr_into_array check uses || ).

array_size check:

ptr_into_array check:

array_size check: (uintptr_t) array + 4 * array_size < (uintptr_t) array ptr_into_array check: (uintptr_t) ptr_into_array - (uintptr_t) array > 4 * array_size

QUESTION DATAREP-27C. In lecture, we discussed several ways to tell if a signed integer x is negative. One of them was the following:

But this is incorrect: it has undefined behavior. Correct it by adding two characters.

(x & (1UL << (sizeof(x) * CHAR_BIT - 1))) != 0

DATAREP-28. ⚠️ Memory errors and garbage collection ⚠️

⚠️ We didn’t discuss garbage collectors in class this year.

Recall that a conservative garbage collector is a program that can automatically free dynamically-allocated memory by detecting when that memory is no longer referenced. Such a GC works by scanning memory for currently-referenced pointers, starting from stack and global memory, and recursing over each referenced object until all referenced memory has been scanned. We built a conservative garbage collector in lecture datarep6.

QUESTION DATAREP-28A. An application program that uses conservative GC, and does not call free directly, will avoid certain errors and undefined behaviors. Which of the following errors are avoided? List all that apply.

• Use-after-free
• Double free
• Signed integer overflow
• Boundary write error
• Unaligned access

QUESTION DATAREP-28B. Write a C program that leaks unbounded memory without GC, but does not do so with GC. You should need less than 5 lines. (Leaking “unbounded” memory means the program will exhaust the memory capacity of any machine on which it runs.)

while ( 1 ) { ( void ) malloc( 1 ); }

QUESTION DATAREP-28C. Not every valid C program works with a conservative GC, because the C abstract machine allows a program to manipulate pointers in strange ways. Which of the following pointer manipulations might cause the conservative GC from class to inappropriately free a memory allocation? List all that apply.

Storing the pointer in a uintptr_t variable

Writing the pointer to a disk file and reading it back later

Using the least-significant bit of the pointer to store a flag:

Storing the pointer in textual form:

Splitting the pointer into two parts and storing the parts in an array:

DATAREP-29. Bitwise

QUESTION DATAREP-29A. Consider this C fragment:

Or, shorter:

Write a single expression that evaluates to the same value, but that does not use the conditional ?: operator. You will use the fact that a < b always equals 0 or 1. For full credit, do not use expensive operators (multiply, divide, modulus).

Examples: (a < b) * x , (-(uintptr_t) (a < b)) & x

QUESTION DATAREP-29B. This function returns one more than the index of the least-significant 1 bit in its argument, or 0 if its argument is zero.

This function runs in O ( B ) time, where B is the number of bits in an unsigned long . Write a version of ffs that runs instead in O (log  B ) time.

int ffs ( unsigned long x) { if ( ! x) { return 0 ; } int ans = 1 ; if ( ! (x & 0x00000000FFFFFFFFUL )) { ans += 32 ; x >>= 32 ; } if ( ! (x & 0x0000FFFF )) { ans += 16 ; x >>= 16 ; } if ( ! (x & 0x00FF )) { ans += 8 ; x >>= 8 ; } if ( ! (x & 0x0F )) { ans += 4 ; x >>= 4 ; } if ( ! (x & 0x3 )) { ans += 2 ; x >>= 2 ; } return ans + (x & 0x1 ? 0 : 1 ); }

DATAREP-30. Data representation

QUESTION DATAREP-30A. Write a type whose size is 19,404,329 times larger than its alignment.

char[19404329]

QUESTION DATAREP-30B. Consider a structure type T with N members, all of which have nonzero size. Assume that sizeof(T) == alignof(T) . What is N ?

QUESTION DATAREP-30C. What is a C type that obeys (T) -1 == (T) 255 on x86-64?

char (or unsigned char or signed char )

Parts D–G use this code. The architecture might or might not be x86-64.

Assume that (uintptr_t) s2 - (uintptr_t) s1 == 4 and *s1 > *s2 .

QUESTION DATAREP-30D. What is sizeof(a) ?

QUESTION DATAREP-30E. What is sizeof(unsigned) on this architecture?

QUESTION DATAREP-30F. Is this architecture big-endian or little-endian?

QUESTION DATAREP-30G. Might the architecture be x86-64?

DATAREP-31. Memory errors

Mavis Gallant is starting on her debugging memory allocator. She’s written code that aims to detect invalid frees, where a pointer passed to m61_free was not returned by an earlier m61_malloc .

Help her track down bugs.

QUESTION DATAREP-31A. What is sizeof(struct m61_metadata) ?

QUESTION DATAREP-31B. Give an m61_ function call (function name and arguments) that would cause both unsigned integer overflow and invalid memory accesses.

m61_malloc((size_t) -15) . This turns into malloc(1) and the dereference of meta->magic becomes invalid.

QUESTION DATAREP-31C. Give an m61_ function call (function name and arguments) that would cause integer overflow, but no invalid memory access within the m61_ functions . (The application might or might not make an invalid memory access later.)

m61_malloc((size_t) -1)

QUESTION DATAREP-31D. These functions have some potential null pointer dereferences. Fix one such problem, including the line number(s) where your code should go.

C3: if (p) { memset(p, 0, sz * count); }

QUESTION DATAREP-31E. Put a single line of C code in the blank. The resulting program should (1) be well-defined with no memory leaks when using default malloc / free / calloc , but (2) always cause undefined behavior when using Mavis’s debugging malloc / free / calloc .

free(nullptr);

QUESTION DATAREP-31F. A double free should print a different message than an invalid free. Write code so Mavis’s implementation does this; include the line numbers where the code should go.

F4: fprintf(stderr, meta->magic == 0xB0B0B0B0 ? "double free of %p" : "invalid free of %p", ptr) after F6: meta->magic = 0xB0B0B0B0;

DATAREP-32. Memory word search

QUESTION DATAREP-32A. What is decimal 61 in hexadecimal?

0x3d, 2 pts

The following is a partial dump of an x86-64 Linux program’s memory. Note that each byte is represented as a hexadecimal number. Memory addresses increase from top to bottom and from left to right.

QUESTION DATAREP-32B. What memory segment contains the memory dump?

Data segment (globals), 2 pts

For questions 3C–3I, give the last two digits of the address of the given object in this memory dump (so for the object located at address 0x6010a8, you would write “a8”). There’s a single best answer for every question, and all questions have different answers .

QUESTION DATAREP-32C. A long (64 bits) of value 61.

QUESTION DATAREP-32D. A long of value -61.

QUESTION DATAREP-32E. An int of value 61.

QUESTION DATAREP-32F. A pointer to an object in the heap.

QUESTION DATAREP-32G. A pointer to a local variable.

QUESTION DATAREP-32H. A pointer that points to an object present in the memory dump.

QUESTION DATAREP-32I. The first byte of a C string comprising at least 4 printable ASCII characters. (Printable ASCII characters have values from 0x20 to 0x7e.)

DATAREP-33. Architecture

QUESTION DATAREP-33A. Write a C++ expression that will evaluate to false on all typical 32-bit architectures and true on all typical 64-bit architectures.

3pts sizeof(void*) == 8

QUESTION DATAREP-33B. Give an integer value that has the same representation in big-endian and little-endian, and give its C++ type. Assume the same type sizes as x86-64.

2pts ex: int x = 0

QUESTION DATAREP-33C. Repeat question B, but with a different integer value.

2pts ex: int x = -1 :)

QUESTION DATAREP-33D. Complete this C++ function, which should return true iff it is called on a machine with little-endian integer representation. Again, you may assume the same type sizes as x86-64.

3pts bool is_little_endian () { union { int a; char c[ 4 ]; } u; u.a = 0 ; u.c[ 0 ] = 1 ; return u.a == 1 ; }

DATAREP-34. Undefined behavior

The following code is taken from the well-known textbook Mastering C Pointers (with some stylistic changes). Assume it is run on x86-64.

QUESTION DATAREP-34A. List all situations in which this program will not execute undefined behavior. (There is at least one.)

3pts If malloc returns nullptr .

QUESTION DATAREP-34B. True or false? The expression ++x could be replaced with ++y without changing the meaning of the program.

3pts True! The undefined behavior is the same either way.

Here’s an updated version of the program.

QUESTION DATAREP-34C. True or false? The expression *(x + y) could be replaced with x[y] without changing the meaning of the program.

QUESTION DATAREP-34D. True or false? The expression *(x + y) could be replaced by * (int*) ((uintptr_t) x + y) without changing the meaning of the program.

3pts False (address arithmetic isn’t the same for pointer arithmetic, except for pointers with type equivalent to char )

DATAREP-35. Odd alignments

QUESTION DATAREP-35A. Write a struct definition that contains exactly seven bytes of padding on x86-64.

3pts struct {long a; char b;}

QUESTION DATAREP-35B. Can an x86-64 struct comprise more than half padding? Give an example if so, or explain briefly why not.

3pts Yes. struct {char a; long b; char c;} has size 24 and 14 bytes of padding.

The remaining questions consider a new architecture called x86-64-rainbow , which is like x86-64 plus special support for a fundamental data type called color . A color is a three-byte data type with red, green, and blue components, kind of like this:

But unlike struct color on x86-64, which has size 3 and alignment 1, color on x86-64-rainbow has size 3 and alignment 3 . All the usual rules for C abstract machine sizes and alignments still hold.

QUESTION DATAREP-35C. What is the alignment of pointers returned by malloc on x86-64-rainbow?

QUESTION DATAREP-35D. Give an example of an x86-64-rainbow struct that ends with more than 16 bytes of padding.

2pts struct { long a[2]; color b[3]; } has alignment lcm(8, 3) = 24 and size 8 + 8 + 3 + 3 + 3 = 25, so it ends with 23 bytes of padding!

DATAREP-36. Debugging allocators

In problem set 1, you built a debugging allocator that could detect many kinds of error. Some students used exclusively internal metadata , where the debugging allocator’s data was stored within the same block of memory as the payload. Some students used external metadata , such as a separate hash table mapping payload pointers to metadata information.

QUESTION DATAREP-36A. Which kind of error mentioned by the problem set could not be detected by external metadata alone?

2pts Boundary write errors.

The problem set requires the m61 library to detect invalid frees, which includes double frees. However, double frees are so common that a special double-free error message can help users. Jia Tolentino wants to print such a message. Her initial idea is to keep a set of recently freed pointers:

QUESTION DATAREP-36B. What eviction policy is used for the recently_freed array?

2pts FIFO (round-robin).

Jia uses these helpers in m61_free as follows. (You may assume that is_invalid_free(ptr) returns true for every invalid or double free.)

She has not yet changed m61_malloc , though she knows she needs to. Help her evaluate whether her design achieves the following mandatory and desirable (that is, optional) requirements.

Note : As you saw in tests 32 and 33 in pset 1, aggressive attacks from users can corrupt metadata arbitrarily. You should assume for the following questions that such aggressive attacks do not occur. The user might free something that was never allocated, and might double-free something, but will never overwrite metadata.

QUESTION DATAREP-36C. Mandatory : The design must not keep unbounded, un-reusable state for pointers that have been freed. Write “Achieved” or “Not achieved” and explain briefly.

6 pts for C-E together. +5 if one serious error; +3 if two serious errors Achieved. The design only keeps space for 10 recently-freed pointers.

QUESTION DATAREP-36D. Desirable : The design should report a double-free as a double-free, not an invalid free. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. If a pointer falls off the list after 10 frees, Jia’s design will report a double-free of that pointer as an invalid free.

QUESTION DATAREP-36E. Mandatory : The design must never report valid frees as double-frees or invalid frees. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. A recently-freed pointer can be reused by malloc, but she hasn’t accounted for that. So if (1) a pointer is freed, (2) a malloc returns the same pointer, (3) the user frees that pointer again, that valid free will be reported as a double free.

QUESTION DATAREP-36F. Describe code to be added to m61_malloc that will achieve all mandatory requirements, if any are required.

3pts Here’s the cleanest solution to the 4E problem. Remove returned pointers from recently_freed . Add this code to malloc before return ptr : for ( int i = 0 ; i != 10 ; ++ i) { if (recently_freed[i] == ptr) { recently_freed[i] = nullptr ; } }

DATAREP-37. Representations

Your job in the following questions is to complete each C++ program so that it prints 61 to standard output when run. Your answer should fill in the blank _________ , and you may assume system calls execute without error. If a question cannot be answered so that the program reliably prints 61 with no undefined behavior, say so and explain briefly.

To compile these programs, use a command line such as c++ -std=gnu++17 -pthread x.cc .

QUESTION DATAREP-37A.

QUESTION DATAREP-37B.

61L or (long) 61 are best; 61 will cause a compiler warning, because it’s an int and the format expects a long .

QUESTION DATAREP-37C.

6 * 16 + 1 , 0x61 , 97

QUESTION DATAREP-37D.

157 , - x + 61 , 96 + 61

QUESTION DATAREP-37E.

char c[61];

QUESTION DATAREP-37F.

This cannot be done. struct sixtyfun has minimum alignment of 4 (because int has alignment 4), so its size must be a multiple of 4.

QUESTION DATAREP-37G.

Anything with size 20, such as char c[20]; or int x[5]; .

QUESTION DATAREP-37H.

int a = 255, b = 0, c = 61; int a = -1, b = 0 (or anything ≤31), c = 61; unsigned a = 0x10000, b = 12, c = 0xFF; int a = 32, b = 1, c = 63; There are many other possibilities!

QUESTION DATAREP-37I.

This cannot be done without undefined behavior, because y is computed using an uninitialized variable.

QUESTION DATAREP-37J.

Anything that adds 15 total to x[0] … x[2] . For example, 5

QUESTION DATAREP-37K.

{ "echo", "61", nullptr }

QUESTION DATAREP-37L.

dup2(pfd[0], 0); close(pfd[0]); close(pfd[1]); The sleep(3) , which is not waitpid , makes many other solutions work too. dup2(pfd[0], 0); works; pipe hygiene isn't important because the parent exits. printf("61\n"); almost works, but something weird happens on Mac OS X.

QUESTION DATAREP-37M.

waitpid(p, nullptr, 0)

QUESTION DATAREP-37N. Note that there are three blanks to fill in with code (you may also leave them empty).

#1, #3: nothing. #2: std::unique_lock<std::mutex> guard(m); If the lock is in #1 (and there is no unlock in #3), that causes deadlock.

Data Representation Worksheets

£ 1.00

Description

Five data representation worksheets / activities for students – ideal for a quick plenary, starter, revision task or quick quiz to keep the topic alive.

Great to use alongside our data representation recap videos, if needed.

Each worksheet requires students to complete an example of all six conversions, with space for their workings.  Answers included.

• Binary to denary
• Binary to hex
• Hex to binary
• Hex to denary
• Denary to hex
• Denary to binary

This resource is available now for an immediate digital download in PDF format.

Related products

Number Systems Cheat Sheet

Storage Devices Worksheets

Product categories.

• Cheat Sheets
• All Quizzes
• Computer Science Glossary
• Our YouTube Channel
• GCSE GURU Revision Tips +

Small Print

• Cookie Policy
• Privacy Policy
• Terms and Conditions

Downloads Shop

• Information & Terms

Copyright © Computer Science GCSE GURU

Teach Computer Science

KS3 Computer Science Data Representation Resources

Ks3 computer science data representation topics.

This module provides a strong base for your students’ computer science knowledge and allows you to teach the basic concepts of computer science. Including:

Module 32: Binary system Module 33: Hexadecimal system Module 34: Character sets Module 35: Images Module 36: Steganography Module 37: Sound Module 38: Compression Module 39: Encryption algorithms

What’s included?

Each module contains:

• An editable PowerPoint lesson presentation
• Editable revision handouts
• A glossary which covers the key terminologies of the module
• Topic mindmaps for visualising the key concepts
• Printable flashcards to help students engage active recall and confidence-based repetition
• A quiz with accompanying answer key to test knowledge and understanding of the module

As a premium member, you get access to the entire library of KS3 Computer science resources. Choose your modules to below to start your downloads.

Binary system

Download ks3 module 32: binary system.

This download is exclusively for Teach Computer Science subscribers! To download this file, click the button below to signup (it only takes a minute) and you'll be brought right back to this page to start the download!

Hexadecimal system

Download ks3 module 33: hexadecimal system, character sets, download ks3 module 34: character sets, download ks3 module 35: images.

Steganography

Download KS3 Module 36: Steganography

Download ks3 module 37: sound, compression, download ks3 module 38: compression, encryption algorithms, download ks3 module 39: encryption algorithms.

View All Modules

• Skip to main content
• Skip to footer
• Accessibility statement and help

GCSE – Data representations

Curriculum KS4 Unit

This unit allows learners to gain the understanding and skills required for the data representation sections of the GCSE computer science exam. First, learners look at binary and hexadecimal numbering systems, how they work, and how to convert between bases. Then, learners explore different coding systems and find out how text, images, and sound are represented in computers. All lessons include worksheets to allow learners to explore each topic through practical application.

Updated: 10 Feb 2023

Learning graph

Updated: 21 Feb 2023

Summative assessment

What is representation?

Number bases

Binary addition

Binary subtraction

Binary shifts

Signed binary integers

Hexadecimal

Representing text

Unicode and file size calculation

Representing bitmap images

Bitmap file size calculation

Representing sound

Sound file size calculation

Measurements of storage

Lossy and lossless compression

Run length encoding

Huffman coding

Enjoyed teaching these lessons? Found a mistake?

Fill in a short form to give feedback on these resources.

data representation computer science

All Formats

Resource types, all resource types.

• Rating Count
• Price (Ascending)
• Price (Descending)
• Most Recent

Data representation computer science

KS3 Computer Science : Data Representation - Year 7

Computer Science || Data Representation Poster Set

KS3 Computer Science : Data Representation - Year 8

GCSE Computer Science : Data Representation lessons bundle

Unit 3 Data Representation Computer Science Principles Project STEM

GCSE Computer Science : Data representation full lesson 2 (Hexadecimal)

GCSE Computer Science : Data representation full lesson 4 (Binary shifts)

GCSE Computer Science : Data representation full lesson 1 (Binary)

IGCSE Computer Science Chapter 1 - Data Representation [174x Animated Slide+PYQ]

IGCSE Computer Science Chapter 1 - Data representation [Worksheet] (2023 - 2025)

Australian Curriculum Year 3/4 Digital Technologies Data Representations Unit

[1825 Slides] AS & A Level Computer Science 9618 Bundle (2024-2026)

[1067 Slides] AS Level Computer Science 9618 Bundle (2024-2026)

[758 Slides] A Level Computer Science 9618 Bundle (2024-2026)

- Computer Science Principles Project STEM - Complete, All Worksheets, 6 Units

Goldie’s AP® Computer Science Principles – Unit 2 Digital Information

Computer Science Principles ProjectSTEM.org - Complete, All Worksheets, 6 Units

AS & A Level Computer Science 9618 (2024-2026) - C16: Data Representation

Data Representation in a computer

AP® Computer Science A: Complete Course (Slides) - Version 2

KS3 Computer Science SUPER BUNDLE!

Year 3/4 Digital Technologies unit on Data Representations

Year 3/4 Digital Technologies data collection and representation

Computer Science - Data Storage–Characters, Image and Sound-Teaching PowerPoint

• We're hiring
• Help & FAQ
• Privacy policy
• Student privacy
• Terms of service
• Tell us what you think

• International
• Schools directory
• Resources Jobs Schools directory News Search

Fundamentals of Data Representation AQA GCSE Computer Science Workbook (8525)

Subject: Computing

Age range: 14-16

Resource type: Worksheet/Activity

Last updated

4 January 2024

• Share through email
• Share through twitter
• Share through linkedin
• Share through facebook
• Share through pinterest

This data representation workbook is perfect for students studying for the AQA GCSE (9-1) in computer science and has been updated to completely cover the new specification 8525.

It can be used in the classroom as a teaching aid, for self-study or as a revision tool. In this resource you will receive an interactive PDF workbook so your students can either print it out and complete the activities by hand or fill it in electronically making this an ideal workbook for use in school or for students studying at home.

The answer booklet is provided as a separate PDF file so you can assign your students the workbook without including the answers.

This 66-page workbook completely covers the new specification 8525 3.3 Fundamentals of Data Representation theory.

Table of Contents:

• Number bases (decimal, binary and hexadecimal)
• Converting between number bases
• Units of information
• Adding together binary numbers
• Binary shift
• Character encoding
• Representing bitmap images
• Colour depth and image size
• Representing sound
• Sampling rate and sample resolution
• Calculate file sizes
• Data compression
• Huffman code
• Run length encoding (RLE) .

FREE BONUS PRODUCT INCLUDED

As a special thank you for purchasing this product I am pleased to be able to also include a surprise FREE bonus gift. This gift is one of our complete resources which we will usually charge full price for but is yours absolutely free when you purchase this product. Just our little way of saying thank you to our valued customers. I hope you enjoy it and get use out of it, with my compliments.

You may also be interested in these workbooks which have also been updated for the new specification:

Python Programming

Computer Systems

Fundamentals of Computer Networks

Cyber Security

Relational databases and SQL

Ethical, Legal and Environmental Impacts

Tes paid licence How can I reuse this?

Get this resource as part of a bundle and save up to 26%

A bundle is a package of resources grouped together to teach a particular topic, or a series of lessons, in one place.

All AQA 8525 computer Science Workbooks BUNDLE

Looking for a comprehensive and easy-to-use resource to help your students excel in AQA GCSE 8525 computer science? Look no further than our complete set of workbooks! Written specifically to match the requirements of the AQA GCSE Computer Science exams, these workbooks ensure that you cover the entire specification and provide your students with all the information they need for successful revision and exam preparation. But these workbooks are more than just a standard handout or textbook. They're interactive and engaging, combining the best of both worlds to create a powerful addition to your teacher's toolkit. With everything at their fingertips, your students will be able to focus on learning and achieving their best. **What is included?** Our interactive PDF workbooks make it easy to focus on specific sections of the AQA 8525 GCSE in Computer Science syllabus without overwhelming your students. Each workbook is designed to cover a single topic in depth, using student-friendly language and clear explanations of key terminology to help your pupils digest the knowledge and retain it for longer. Throughout each workbook, tasks are included to reinforce learning and allow you to monitor your students' progress. Answers are provided in a separate PDF workbook, giving you the option to issue workbooks without answers for assessment purposes. To help your students take ownership of their learning, each workbook also includes a student checklist. This tool allows students to track their progress and identify areas where they may need more work, helping you make the most of the time you have with your students. This bundle includes all of the following AQA workbooks: * Fundamentals of Algorithms * Programming using Python * Fundamentals of Data Representation * Computer Systems * Fundamentals of Computer Networks * Cyber Security * Relational Databases and Structured Query Language (SQL) * Ethical, Legal and Environmental Impacts of Digital Technology The total individual price for all the computer science workbooks is £135.92 but when purchased as a bundle you can get all this for only £100 saving you more than 25% of the individual price. **How can they be used?** Our AQA 8525 GCSE in Computer Science workbooks are the perfect complement to your classroom teaching. They offer the flexibility to be completed either on-screen or printed and completed manually on paper, ensuring continuity both in the computer room and when your classroom is being used by another subject. In addition, our workbooks can also be given to students as homework or self-study projects to complete on their own at home. This is a great option for students who may need extra practice or who want to reinforce their understanding of a particular topic. The best part? When you purchase our workbooks, you'll receive a PDF file that can be reused time and time again with no further costs or ongoing subscription fees. This means that you can continue to use them year after year, saving time and money in the process. So whether you're looking for an in-class supplement, a homework option, or a comprehensive revision tool, our AQA 8525 GCSE in Computer Science workbooks are an excellent choice.

Your rating is required to reflect your happiness.

It's good to leave some feedback.

Something went wrong, please try again later.

This resource hasn't been reviewed yet

To ensure quality for our reviews, only customers who have purchased this resource can review it

Report this resource to let us know if it violates our terms and conditions. Our customer service team will review your report and will be in touch.

Not quite what you were looking for? Search by keyword to find the right resource:

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Praxis Core Math

Course: praxis core math   >   unit 1, data representations | lesson.

• Data representations | Worked example
• Center and spread | Lesson
• Center and spread | Worked example
• Random sampling | Lesson
• Random sampling | Worked example
• Scatterplots | Lesson
• Scatterplots | Worked example
• Interpreting linear models | Lesson
• Interpreting linear models | Worked example
• Correlation and Causation | Lesson
• Correlation and causation | Worked example
• Probability | Lesson
• Probability | Worked example

What are data representations?

• How much of the data falls within a specified category or range of values?
• What is a typical value of the data?
• How much spread is in the data?
• Is there a trend in the data over time?
• Is there a relationship between two variables?

What skills are tested?

• Matching a data set to its graphical representation
• Matching a graphical representation to a description
• Using data representations to solve problems

How are qualitative data displayed?

• A table summarizes the data using rows and columns. Each column contains data for a single variable, and a basic table contains one column for the qualitative variable and one for the quantitative variable. Each row contains a category of the qualitative variable and the corresponding value of the quantitative variable. [Example]
• A vertical bar chart lists the categories of the qualitative variable along a horizontal axis and uses the heights of the bars on the vertical axis to show the values of the quantitative variable. A horizontal bar chart lists the categories along the vertical axis and uses the lengths of the bars on the horizontal axis to show the values of the quantitative variable. This display draws attention to how the categories rank according to the amount of data within each. [Example]
• A pictograph is like a horizontal bar chart but uses pictures instead of the lengths of bars to represent the values of the quantitative variable. Each picture represents a certain quantity, and each category can have multiple pictures. Pictographs are visually interesting, but require us to use the legend to convert the number of pictures to quantitative values. [Example]
• A circle graph (or pie chart) is a circle that is divided into as many sections as there are categories of the qualitative variable. The area of each section represents, for each category, the value of the quantitative data as a fraction of the sum of values. The fractions sum to 1 ‍   . Sometimes the section labels include both the category and the associated value or percent value for that category. [Example]

How are quantitative data displayed?

• Dotplots use one dot for each data point. The dots are plotted above their corresponding values on a number line. The number of dots above each specific value represents the count of that value. Dotplots show the value of each data point and are practical for small data sets. [Example]
• Histograms divide the horizontal axis into equal-sized intervals and use the heights of the bars to show the count or percent of data within each interval. By convention, each interval includes the lower boundary but not the upper one. Histograms show only totals for the intervals, not specific data points. [Example]

How are trends over time displayed?

How are relationships between variables displayed.

• (Choice A)   A
• (Choice B)   B
• (Choice C)   C
• (Choice D)   D
• (Choice E)   E
• Your answer should be
• an integer, like 6 ‍  
• a simplified proper fraction, like 3 / 5 ‍  
• a simplified improper fraction, like 7 / 4 ‍  
• a mixed number, like 1   3 / 4 ‍  
• an exact decimal, like 0.75 ‍  
• a multiple of pi, like 12   pi ‍   or 2 / 3   pi ‍  
• a proper fraction, like 1 / 2 ‍   or 6 / 10 ‍  
• an improper fraction, like 10 / 7 ‍   or 14 / 8 ‍  

Things to remember

• When matching data to a representation, check that the values are graphed accurately for all categories.
• When reporting data counts or fractions, be clear whether a question asks about data within a single category or a comparison between categories.
• When finding the number or fraction of the data meeting a criteria, watch for key words such as or , and , less than , and more than .

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page

Have an account?

Suggestions for you See more

Network Hardware

9th -  11th  , processor components, 11th -  12th  , 7th -  10th  .

GCSE Computer Science Data Representatio...

GCSE Computer Science Data Representation

25 questions

Introducing new   Paper mode

No student devices needed.   Know more

• 1. Multiple Choice Edit 20 seconds 1 pt Convert 254 to binary 11110000 11111100 11111111 11111110
• 2. Multiple Choice Edit 45 seconds 1 pt Convert 00010001 to decimal 17 27 37 47
• 3. Multiple Choice Edit 1 minute 1 pt Convert 11111111 to decimal 255 245 235 225
• 4. Multiple Choice Edit 1 minute 12 pts Convert 01000100 to decimal 58 68 78 88
• 5. Multiple Choice Edit 10 seconds 1 pt What two digits are used in binary? 0 & 2 1&2 0&1 1&1
• 6. Multiple Choice Edit 10 seconds 1 pt Binary is also known as Base 1 Base 2 Base 10 Base jumping
• 7. Multiple Choice Edit 10 seconds 1 pt A single 0 or 1 is known as a Bit Byte Nibble Binary
• 8. Multiple Choice Edit 10 seconds 1 pt How many bits are there in a byte? 2 4 8 10
• 9. Multiple Choice Edit 20 seconds 1 pt The numbers we normally use are called ________ numbers and have 10 different values. denary binary digital integers
• 10. Multiple Choice Edit 30 seconds 1 pt A9 1010 1011 1010 1001 1001 1001 1110 0101
• 11. Multiple Choice Edit 30 seconds 1 pt 1101 1110 ED DE EC CE
• 12. Multiple Choice Edit 1 minute 1 pt Convert 85 into Hexadecimal 01010101 55 5A A5
• 13. Multiple Choice Edit 20 seconds 1 pt What is the answer to 0110 + 0101? 1011 1101 1110 1111
• 14. Multiple Choice Edit 30 seconds 1 pt How does increasing colour depth affect an image file? Increases number of colours in image Increases resolution of image Increases image width Decreases metadata for an image 
• 15. Multiple Choice Edit 45 seconds 1 pt What sample rate do most CDs have? 44.1kHz 50,000Hz 40.2kHz 4Hz
• 16. Multiple Choice Edit 1 minute 1 pt What is bit depth? Number of bits assigned to each sample Rate at which the binary is calculated How deep the sound can go The speed of the sound wave
• 17. Multiple Choice Edit 10 seconds 1 pt What is ASCII? How the internet displays images A character set A programming language Binary information on the computer
• 18. Multiple Choice Edit 10 seconds 1 pt ASCII stands for… What doesn't it stand for? All Symbolic Computer Instructions Interchange Alternative Standard Computers Interchange Internet American Standard Code for Information Interchange
• 19. Multiple Choice Edit 30 seconds 1 pt What is a pixel? Tiny squares of colour on a screen. A fairy like creature thatlives in a forest. A whole picture. A binary code.
• 20. Multiple Choice Edit 30 seconds 1 pt The higher the colour depth, the _________the image file size. Smaller Larger

How many megabytes in a gigabyte?

Which of these is accurate for smallest to largest?

Kilobyte, Megabyte, Gigabyte, Terabyte

Megabyte, Kilobyte, Terabyte, Gigabyte

Gigabyte, Kilobyte, Terabyte, Megabyte

Terabyte, Gigabyte, Megabyte, Kilobyte

• 23. Multiple Choice Edit 30 seconds 1 pt Makes the file smaller by deleting parts of the file permanently (forever) Lossy Compression Lossless Compression
• 24. Multiple Choice Edit 30 seconds 1 pt Data compression usually works by.. Finding repeating patterns. Deleting random bits data
• 25. Multiple Choice Edit 30 seconds 1 pt What type of compression would you use to compress a text file? Lossy Lossless

Explore all questions with a free account

Continue with email

Continue with phone