Problem Question (Bits to encode a 75*75 grid)

CS Principles
1

Hello,
So I have a dilemma that I have written about briefly in another post - Assessment question with calendar date

I thought maybe I could make things more clear by asking you guys the answer to this question.

You have a coordinate grid that is 75 x 75. Assuming that you encode the x and y coordinates as separate numbers, what is the minimum number of bits that you will need to encode a coordinate in that space?

Using the method of calculating the number of bits need for the 75 x axis, and the method of 75 y axis, each axis would need 7 bits, for a total of 14 bits.

However the minimum number of bits you need to encode the coordinate grid is 13 bits. As you only need 13 bits to encode (75*75) 5625 different possibilites/grid coordinates.

Any help on guiding my students on the methodology they should use? Am I seeing the above question incorrectly?

2

Hi @glenn.crane

I think it might help to look at what’s happening with you case study is to look at a smaller example:

Consider a grid of 3x3.

By the “suggested” method, each coordinate could be communicated in 4 bits (2 for the x, 2 for the y).

So the coordinate (2,3) would be: 1011 and the coordinate (3,3) would be 1111

By your method, 3x3 = 9 which can be communicated in 4 bits. Here’s how the grid would work, which also
uses only four bits.

0000    0001    0010    0011
0100    0101    0110    0111
1000    1001    1010    1011
1100    1101    1110    1111

Let’s step it up to a 5 by 5 grid. Suggested method: 6 bits (3 to communicate 5).

Your method: 5*5 = 25, which can be communicated in 5 bits.

00000  00001  00010  00011  00100  00101
00110  00111  01000  01001  01010  01011
01100  01101  01110  01111  10000  10001
10010  10011  10100  10101  10110  10111
11000  11001  11010  11011  11100  11101

So as the number scales up, your method appears to sometimes take less bits to send. This is because at it’s maximum, not every bit is “turned on” (to communicate five, we use 101 and never reach 111). However, it requires that every position in the grid be mapped to a specific number, which takes time to translate, particularly when considering the Sending Numbers activity.

Thank you for exploring this option - playing with numbers is fun!

1 Like
3

I’m going to piggy back on @hannah’s reply to go philosophical…

This is what makes computer science different from the natural sciences – all laws are human-made. There is no “right” methodology and the method you choose depends on the circumstances. Computer scientists run into these dilemmas of representation all the time, and honestly might decide either way – which is a good meta point for your students!

The essential dilemma you have is: do I represent the coordinate-space in binary, or should I represent the individual cells that make up the area? There are pros and cons to these choices, but they are choices and both could be “right” depending what you’re trying to do.

— intellectual dalliance warning —

This particular one is interesting though! If you plot out the side-length of square v. the size of the area and calculate how many bits it would take to represent these two things you’ll see that representing the area can only EVER be a 1-bit improvement over the representing the coordinates. Please note: this was not intuitive to me at all, I had to run an experiment in a spreadsheet!

Here’s a snippet – the patterns are interesting

image
image.png308×806 19.8 KB

Cheers,

Baker

1 Like
4

Thank you both for your answers.

I understand fully (I believe what you are both saying). My question would then be the following:

If the minimum bits for a 75*75 coordinate grid came up in an exam, would you suggest that they therefore put the answer as 13bits as it would technically be the minimum, even though we are teaching the ‘quicker’ method of using the coordinates of X and Y?

I know this may be arbitrary as hopefully the examiners would not put this type of question which could purposefully confuse…

Also thanks both for writing out your examples, both make it clearer to explain/understand.

5

@glenn.crane To my knowledge, there aren’t any questions exactly like this on the exam. The main concepts we want students to grapple with are:

  1. The same piece of data can communicate different things, depending on the context. 1010 in binary can represent the decimal number 10, or depending on my protocol, could represent the coordinates (2,2).
  2. The range that we can represent is limited by the number of bits that we have to work with.
  3. There is not one right way of representing the data. As @baker was saying, questions like the ones you asked are the types of questions that computer scientists deal with. There are tradeoffs involved in all these decisions.

I found it helpful when thinking about this topic to go back and reread the purpose of this lesson. Hopefully that will help clarify the key takeaways here as well.

1 Like
6

Thanks again for the explanation.

I guess in my response I am just trying to play the ‘what if’ game, if that specific question came up in the exam would there be points deducted (not awarded) for an answer of 14 bits compared to an answer of 13 bits.

Like you said it should not come up in the exam, so hopefully it would not be a problem. I just know that my students will ask that question of ‘What if it came up in the exam’, and as it is a multiple choice exam there is no room/scope for explaining why they have chosen the method they have chosen.

Part of this is also the culture of the school I work at in Korea (culturally there is always a right answer).

7

Since we’re both involved now :)… The AP exam works really hard and has a very long process to ensure that questions aren’t ambiguously worded. So if even this were fodder for an exam question (it’s not) it would never be asked this way.

1 Like
8

Thanks for both of your understandings and explanations. I will definitely be having a long talk with my students about this, including using some of the examples and explanations you have communicated above.

Thanks again.

PS: I wonder if it would be worth in the future using the 75 * 75 grid as an example ‘Check Your Understanding’ question, with a follow up question of how using different method may come up with slightly different answer (+ or - variance).

9

Thank you for the explanation of questions students will have as they work through this exercise. A question came up about setting the bits per chunk between the sender and the receiver. Is this something that the sender needs to send to the receiver depending on the grid they are planning on using for the image or is this something that is set up before hand so they both will be able to recognize the values being sent?

10

That’s a great question! I like to think about scaling it up to the “internet size” of things. By that I mean, how will it work in real life. I like to think that we could agree that the first 4-8 bits will determine the chunk size. If we always know the first 8 bits in the message tell us our chunk size, then we can change our chunk size to match what our partner intended. We could also say “we always use 8 bits per chunk” but that probably isn’t as efficient.

The goal of this lesson to me is to raise questions just like this one! I think it shows students are understanding the complexity of the problems the creators of the internet encountered.