assignment 3 1 study guide questions

Understanding Assignments

What this handout is about.

The first step in any successful college writing venture is reading the assignment. While this sounds like a simple task, it can be a tough one. This handout will help you unravel your assignment and begin to craft an effective response. Much of the following advice will involve translating typical assignment terms and practices into meaningful clues to the type of writing your instructor expects. See our short video for more tips.

Basic beginnings

Regardless of the assignment, department, or instructor, adopting these two habits will serve you well :

• Read the assignment carefully as soon as you receive it. Do not put this task off—reading the assignment at the beginning will save you time, stress, and problems later. An assignment can look pretty straightforward at first, particularly if the instructor has provided lots of information. That does not mean it will not take time and effort to complete; you may even have to learn a new skill to complete the assignment.
• Ask the instructor about anything you do not understand. Do not hesitate to approach your instructor. Instructors would prefer to set you straight before you hand the paper in. That’s also when you will find their feedback most useful.

Assignment formats

Many assignments follow a basic format. Assignments often begin with an overview of the topic, include a central verb or verbs that describe the task, and offer some additional suggestions, questions, or prompts to get you started.

An Overview of Some Kind

The instructor might set the stage with some general discussion of the subject of the assignment, introduce the topic, or remind you of something pertinent that you have discussed in class. For example:

“Throughout history, gerbils have played a key role in politics,” or “In the last few weeks of class, we have focused on the evening wear of the housefly …”

The Task of the Assignment

Pay attention; this part tells you what to do when you write the paper. Look for the key verb or verbs in the sentence. Words like analyze, summarize, or compare direct you to think about your topic in a certain way. Also pay attention to words such as how, what, when, where, and why; these words guide your attention toward specific information. (See the section in this handout titled “Key Terms” for more information.)

“Analyze the effect that gerbils had on the Russian Revolution”, or “Suggest an interpretation of housefly undergarments that differs from Darwin’s.”

Additional Material to Think about

Here you will find some questions to use as springboards as you begin to think about the topic. Instructors usually include these questions as suggestions rather than requirements. Do not feel compelled to answer every question unless the instructor asks you to do so. Pay attention to the order of the questions. Sometimes they suggest the thinking process your instructor imagines you will need to follow to begin thinking about the topic.

“You may wish to consider the differing views held by Communist gerbils vs. Monarchist gerbils, or Can there be such a thing as ‘the housefly garment industry’ or is it just a home-based craft?”

These are the instructor’s comments about writing expectations:

“Be concise”, “Write effectively”, or “Argue furiously.”

Technical Details

These instructions usually indicate format rules or guidelines.

“Your paper must be typed in Palatino font on gray paper and must not exceed 600 pages. It is due on the anniversary of Mao Tse-tung’s death.”

The assignment’s parts may not appear in exactly this order, and each part may be very long or really short. Nonetheless, being aware of this standard pattern can help you understand what your instructor wants you to do.

Interpreting the assignment

Ask yourself a few basic questions as you read and jot down the answers on the assignment sheet:

Why did your instructor ask you to do this particular task?

Who is your audience.

• What kind of evidence do you need to support your ideas?

What kind of writing style is acceptable?

• What are the absolute rules of the paper?

Try to look at the question from the point of view of the instructor. Recognize that your instructor has a reason for giving you this assignment and for giving it to you at a particular point in the semester. In every assignment, the instructor has a challenge for you. This challenge could be anything from demonstrating an ability to think clearly to demonstrating an ability to use the library. See the assignment not as a vague suggestion of what to do but as an opportunity to show that you can handle the course material as directed. Paper assignments give you more than a topic to discuss—they ask you to do something with the topic. Keep reminding yourself of that. Be careful to avoid the other extreme as well: do not read more into the assignment than what is there.

Of course, your instructor has given you an assignment so that he or she will be able to assess your understanding of the course material and give you an appropriate grade. But there is more to it than that. Your instructor has tried to design a learning experience of some kind. Your instructor wants you to think about something in a particular way for a particular reason. If you read the course description at the beginning of your syllabus, review the assigned readings, and consider the assignment itself, you may begin to see the plan, purpose, or approach to the subject matter that your instructor has created for you. If you still aren’t sure of the assignment’s goals, try asking the instructor. For help with this, see our handout on getting feedback .

Given your instructor’s efforts, it helps to answer the question: What is my purpose in completing this assignment? Is it to gather research from a variety of outside sources and present a coherent picture? Is it to take material I have been learning in class and apply it to a new situation? Is it to prove a point one way or another? Key words from the assignment can help you figure this out. Look for key terms in the form of active verbs that tell you what to do.

Key Terms: Finding Those Active Verbs

Here are some common key words and definitions to help you think about assignment terms:

Information words Ask you to demonstrate what you know about the subject, such as who, what, when, where, how, and why.

• define —give the subject’s meaning (according to someone or something). Sometimes you have to give more than one view on the subject’s meaning
• describe —provide details about the subject by answering question words (such as who, what, when, where, how, and why); you might also give details related to the five senses (what you see, hear, feel, taste, and smell)
• explain —give reasons why or examples of how something happened
• illustrate —give descriptive examples of the subject and show how each is connected with the subject
• summarize —briefly list the important ideas you learned about the subject
• trace —outline how something has changed or developed from an earlier time to its current form
• research —gather material from outside sources about the subject, often with the implication or requirement that you will analyze what you have found

Relation words Ask you to demonstrate how things are connected.

• compare —show how two or more things are similar (and, sometimes, different)
• contrast —show how two or more things are dissimilar
• apply—use details that you’ve been given to demonstrate how an idea, theory, or concept works in a particular situation
• cause —show how one event or series of events made something else happen
• relate —show or describe the connections between things

Interpretation words Ask you to defend ideas of your own about the subject. Do not see these words as requesting opinion alone (unless the assignment specifically says so), but as requiring opinion that is supported by concrete evidence. Remember examples, principles, definitions, or concepts from class or research and use them in your interpretation.

• assess —summarize your opinion of the subject and measure it against something
• prove, justify —give reasons or examples to demonstrate how or why something is the truth
• evaluate, respond —state your opinion of the subject as good, bad, or some combination of the two, with examples and reasons
• support —give reasons or evidence for something you believe (be sure to state clearly what it is that you believe)
• synthesize —put two or more things together that have not been put together in class or in your readings before; do not just summarize one and then the other and say that they are similar or different—you must provide a reason for putting them together that runs all the way through the paper
• analyze —determine how individual parts create or relate to the whole, figure out how something works, what it might mean, or why it is important
• argue —take a side and defend it with evidence against the other side

More Clues to Your Purpose As you read the assignment, think about what the teacher does in class:

• What kinds of textbooks or coursepack did your instructor choose for the course—ones that provide background information, explain theories or perspectives, or argue a point of view?
• In lecture, does your instructor ask your opinion, try to prove her point of view, or use keywords that show up again in the assignment?
• What kinds of assignments are typical in this discipline? Social science classes often expect more research. Humanities classes thrive on interpretation and analysis.
• How do the assignments, readings, and lectures work together in the course? Instructors spend time designing courses, sometimes even arguing with their peers about the most effective course materials. Figuring out the overall design to the course will help you understand what each assignment is meant to achieve.

Now, what about your reader? Most undergraduates think of their audience as the instructor. True, your instructor is a good person to keep in mind as you write. But for the purposes of a good paper, think of your audience as someone like your roommate: smart enough to understand a clear, logical argument, but not someone who already knows exactly what is going on in your particular paper. Remember, even if the instructor knows everything there is to know about your paper topic, he or she still has to read your paper and assess your understanding. In other words, teach the material to your reader.

Aiming a paper at your audience happens in two ways: you make decisions about the tone and the level of information you want to convey.

• Tone means the “voice” of your paper. Should you be chatty, formal, or objective? Usually you will find some happy medium—you do not want to alienate your reader by sounding condescending or superior, but you do not want to, um, like, totally wig on the man, you know? Eschew ostentatious erudition: some students think the way to sound academic is to use big words. Be careful—you can sound ridiculous, especially if you use the wrong big words.
• The level of information you use depends on who you think your audience is. If you imagine your audience as your instructor and she already knows everything you have to say, you may find yourself leaving out key information that can cause your argument to be unconvincing and illogical. But you do not have to explain every single word or issue. If you are telling your roommate what happened on your favorite science fiction TV show last night, you do not say, “First a dark-haired white man of average height, wearing a suit and carrying a flashlight, walked into the room. Then a purple alien with fifteen arms and at least three eyes turned around. Then the man smiled slightly. In the background, you could hear a clock ticking. The room was fairly dark and had at least two windows that I saw.” You also do not say, “This guy found some aliens. The end.” Find some balance of useful details that support your main point.

You’ll find a much more detailed discussion of these concepts in our handout on audience .

The Grim Truth

With a few exceptions (including some lab and ethnography reports), you are probably being asked to make an argument. You must convince your audience. It is easy to forget this aim when you are researching and writing; as you become involved in your subject matter, you may become enmeshed in the details and focus on learning or simply telling the information you have found. You need to do more than just repeat what you have read. Your writing should have a point, and you should be able to say it in a sentence. Sometimes instructors call this sentence a “thesis” or a “claim.”

So, if your instructor tells you to write about some aspect of oral hygiene, you do not want to just list: “First, you brush your teeth with a soft brush and some peanut butter. Then, you floss with unwaxed, bologna-flavored string. Finally, gargle with bourbon.” Instead, you could say, “Of all the oral cleaning methods, sandblasting removes the most plaque. Therefore it should be recommended by the American Dental Association.” Or, “From an aesthetic perspective, moldy teeth can be quite charming. However, their joys are short-lived.”

Convincing the reader of your argument is the goal of academic writing. It doesn’t have to say “argument” anywhere in the assignment for you to need one. Look at the assignment and think about what kind of argument you could make about it instead of just seeing it as a checklist of information you have to present. For help with understanding the role of argument in academic writing, see our handout on argument .

What kind of evidence do you need?

There are many kinds of evidence, and what type of evidence will work for your assignment can depend on several factors–the discipline, the parameters of the assignment, and your instructor’s preference. Should you use statistics? Historical examples? Do you need to conduct your own experiment? Can you rely on personal experience? See our handout on evidence for suggestions on how to use evidence appropriately.

Make sure you are clear about this part of the assignment, because your use of evidence will be crucial in writing a successful paper. You are not just learning how to argue; you are learning how to argue with specific types of materials and ideas. Ask your instructor what counts as acceptable evidence. You can also ask a librarian for help. No matter what kind of evidence you use, be sure to cite it correctly—see the UNC Libraries citation tutorial .

You cannot always tell from the assignment just what sort of writing style your instructor expects. The instructor may be really laid back in class but still expect you to sound formal in writing. Or the instructor may be fairly formal in class and ask you to write a reflection paper where you need to use “I” and speak from your own experience.

Try to avoid false associations of a particular field with a style (“art historians like wacky creativity,” or “political scientists are boring and just give facts”) and look instead to the types of readings you have been given in class. No one expects you to write like Plato—just use the readings as a guide for what is standard or preferable to your instructor. When in doubt, ask your instructor about the level of formality she or he expects.

No matter what field you are writing for or what facts you are including, if you do not write so that your reader can understand your main idea, you have wasted your time. So make clarity your main goal. For specific help with style, see our handout on style .

Technical details about the assignment

The technical information you are given in an assignment always seems like the easy part. This section can actually give you lots of little hints about approaching the task. Find out if elements such as page length and citation format (see the UNC Libraries citation tutorial ) are negotiable. Some professors do not have strong preferences as long as you are consistent and fully answer the assignment. Some professors are very specific and will deduct big points for deviations.

Usually, the page length tells you something important: The instructor thinks the size of the paper is appropriate to the assignment’s parameters. In plain English, your instructor is telling you how many pages it should take for you to answer the question as fully as you are expected to. So if an assignment is two pages long, you cannot pad your paper with examples or reword your main idea several times. Hit your one point early, defend it with the clearest example, and finish quickly. If an assignment is ten pages long, you can be more complex in your main points and examples—and if you can only produce five pages for that assignment, you need to see someone for help—as soon as possible.

Tricks that don’t work

Your instructors are not fooled when you:

• spend more time on the cover page than the essay —graphics, cool binders, and cute titles are no replacement for a well-written paper.
• use huge fonts, wide margins, or extra spacing to pad the page length —these tricks are immediately obvious to the eye. Most instructors use the same word processor you do. They know what’s possible. Such tactics are especially damning when the instructor has a stack of 60 papers to grade and yours is the only one that low-flying airplane pilots could read.
• use a paper from another class that covered “sort of similar” material . Again, the instructor has a particular task for you to fulfill in the assignment that usually relates to course material and lectures. Your other paper may not cover this material, and turning in the same paper for more than one course may constitute an Honor Code violation . Ask the instructor—it can’t hurt.
• get all wacky and “creative” before you answer the question . Showing that you are able to think beyond the boundaries of a simple assignment can be good, but you must do what the assignment calls for first. Again, check with your instructor. A humorous tone can be refreshing for someone grading a stack of papers, but it will not get you a good grade if you have not fulfilled the task.

Critical reading of assignments leads to skills in other types of reading and writing. If you get good at figuring out what the real goals of assignments are, you are going to be better at understanding the goals of all of your classes and fields of study.

You may reproduce it for non-commercial use if you use the entire handout and attribute the source: The Writing Center, University of North Carolina at Chapel Hill

Make a Gift

Due: Wed Apr 17 11:59 pm Late submissions accepted until Fri Apr 19 11:59 pm

Assignment by Julie Zelenski, with modifications by Nick Troccoli, Chris Gregg, Katie Creel and Brynne Hurst

Along with this assignment, we've posted a page of extra bits practice problems with solutions. There is also an online practice site . These are very helpful to confirm your understanding of bit operators, binary, and more as you get started with this assignment!

We'll cover the remaining shift ( << and >> ) bit operators and the GDB debugger in the lecture following the release of this assignment, both of which are needed to work on the coding portions of the assignment. However, prior to this lecture, you can complete the Case Study portion of the assignment and read through the coding problem descriptions to understand what is being asked in each part.

Learning Goals

This assignment covers topics from the first few lectures and the first lab. You will be building your skills with:

• editing, compiling, testing, and debugging C programs under Unix
• writing code that manipulates bits and integers using the C bitwise and arithmetic operators
• working within/around the limits of integer representation
• understanding the ramifications of integer representations in real-world software

You shouldn't need material related to strings/pointers for this assignment - in other words, this assignment focuses just on the material related to bits and bytes.

This assignment asks you to complete three programs and one case study. Each program explores a particular aspect of bitwise or numeric manipulation:

• Maxwell's Demon has you model gas particles in chambers.
• UTF8 has you create unicode characters by constructing bit patterns.
• Saturated Arithmetic has you detect overflow in addition operations.
• The Ariane-5 Case Study has you examine the consequences of a real-world overflow bug.

The code you will write is short, but these small passages are mighty!

Recommended Timeline For Completion : As with all CS107 assignments, you must start early . There are three different programs to work on for the assignment, and our recommendation would be to try and complete one program every two to three days, with the assignment a bit over a week long in total.

• The working on assignments page contains info about the assignment process.
• The collaboration policy page outlines permitted assignment collaboration, emphasizing that you are to do your own independent thinking, design, coding, and debugging. If you are having trouble completing the assignment on your own, please reach out to the course staff; we are here to help!

To get started on the assignment, clone the starter project using the command

The starter project contains the following:

• readme.txt : a text file where you will answer questions for the assignment
• sat.c . util.c , utf8.c and Makefile : three partially-written programs that you will modify, and their Makefile for compiling
• maxwell_demon.c : the provided partial implementation of the Maxwell's Demon program. You do not need to modify this file.
• custom_tests : the file where you will add custom tests for your programs
• SANITY.ini , sanity.py and prototypes.h : files to configure and run Sanity Check. You can ignore these.
• maxwell_demon_soln , sat_soln and utf8_soln : executable solutions for the programs you will modify.
• tools : contains symbolic links to the sanitycheck and submit programs for testing and submitting your work. It also contains a new codecheck tool for checking for style and other common code issues.

Assignment Support: Through TA helper hours and the discussion forum, our focus will be on supporting you so that you can track down your own bugs. Please ask us how to best use tools (like the brand-new GDB!), what strategies to consider, and advice about how to improve your debugging process or track down your bug. We're happy to help you with these in order to help you drive your own debugging. For this reason, if you have debugging questions during helper hours, please make sure to gather information and explore the issue on your own first, and fill out the QueueStatus questions with this information. For instance, if your program is failing in certain cases, try to find a small replicable test case where the program fails; then, try using GDB to narrow down to what function/code block/etc. you think is causing the issue; then, further investigate just that area to try and find the bug. As another example, if your program is crashing, take a similar approach, but try using GDB and the backtrace command (check it out in lab!) to narrow in on the source of the crash. This information is important for the course staff to effectively help you with debugging. Starting with a future assignment, we will require this information when signing up for helper hours for debugging help , so please make sure to provide as much information as possible.

Tools and Testing

We have added a new tool, codecheck , that can check your code for common style and other issues that are detectable at compile-time. This check is NOT exhaustive; it is only meant to identify common style and other code issues. Check the course style guide and assignment spec for more code guidelines. You can run Codecheck like the sanitycheck and submit tools, from the tools folder, by running tools/codecheck , which runs it on all .c files in the current directory. You can also run it on individual files, like this:

Note that Codecheck does check for magic numbers , but for assign1 it may not align exactly with the best approach, as it considers anything above a certain numeric value automatically a "magic number". For this assignment, it's not necessarily stylistically bad if Codecheck shows any issue messages about magic numbers. But, you should still be vigilant and evaluate each suggestion from Codecheck to decide how you can make your code as clean as possible.

You only need to run codecheck on the files you are modifying for this assignment: sat.c , util.c and utf8.c .

This assignment heavily emphasizes testing. For each program you write below, you should also add at least 3 to 5 additional tests of your own per program (total of at least 10) in the custom_tests file that show thoughtful effort to develop comprehensive test coverage. When you add a test, also document your work by including comments (on their own line, starting with # ) in the custom_tests file that remind you why you included each test and how the tests relate to one another. The tests supplied with the default SanityCheck are a start that you should build on, with the goal of finding and fixing any bugs before submitting, just like how a professional developer is responsible for vetting any code through comprehensive testing before adding it to a team repository.

The best way to approach testing on this assignment is, once you understand the expected program behavior but BEFORE you write any code, write some tests that cover various cases you can think of. This is because once you start writing code, you may start to think in terms of how your code works rather than how the code should work, meaning if you omit handling a case in your code, you may also omit covering that case in your testing. Thus, a good strategy is to write some tests before implementing anything, and then as you implement, you can add further tests. Use the tests as a way to gauge your progress and uncover bugs! We provide some testing recommendations in each problem section below.

How do you brainstorm what additional tests to consider? First review the cases supplied with default sanitycheck to see what is already covered. Then consider the full range of inputs/possibilities beyond those simple cases. If the variety of inputs is sufficiently small, you may be able to enumerate a test case for each possibility. In other situations, exhaustive coverage is not feasible, so you instead identify representative samples to validate the operation on specific cases. You should target ordinary cases as well as edge conditions and unusual inputs. For more advice, check out our guide to testing , from the assignments dropdown.

Review and Comment

When you inherit code to build on, you should first carefully review it to understand its behavior and plan how your code will fit into the existing program. You are given about 25 lines for each of sat.c and utf8.c and will add about a dozen lines of your own for each of the 3 programming parts, so there is more starter code to review than new code to add.

Our provided code for the sat.c and utf8.c programs processes the command-line arguments, handles user error in how the program is invoked, and has a few important details, particularly in converting string arguments to numbers. The triangle program from assign0 used the atoi function, which is simpler to use but has no capability to detect malformed inputs. For these programs, we are using the more robust, but complex, strtol . Read the function documentation at man strtol and review how the function is used in convert_arg in sat.c and utf8.c .

Some questions you might consider as a self-test for the sat.c and utf8.c programs:

• How do the sample programs respond if invoked with missing arguments? excess arguments?
• When converting the user's string argument to a number, what base is passed to strtol ? In which bases does this allow the argument to be specified? How does the user's argument indicate which base to use?
• What does strtol do if it encounters an invalid character in the string to convert?
• How is the second argument to strtol used for error-detection? Why is it ok that the end variable is dereferenced when it is initialized to NULL ? If you did not want that error-detection, what do you pass as the second argument instead?
• What does strtol do if asked to convert a string whose value would be too large to be represented in a long ?
• Do you see anything unexpected or erroneous? We intend for our code to be bug-free; if you find otherwise, please let us know!

After reviewing the code, try experimenting with it! Build and run the programs, invoking them with different arguments to see how each is treated. Run the program under the debugger (check out our Debugger Guide under "Handouts") and step through code, printing intermediate values as you go. Observing the code in action is an excellent way to better understand it. Confirm your answers to the self-test questions above to verify your understanding.

We intentionally left off all the comments on the starter code, so you should add in documentation when implementing each program below. Add an appropriate overview comment for the entire program, document each of the functions, and add inline comments where necessary to highlight any particularly tricky details. (One exception: you do not need to read, modify or add comments to maxwell_demon.c ).

1. Maxwell's Demon

Maxwell's demon is a fun thought experiment about the second law of thermodynamics postulated by James Maxwell. In the original experiment idea, a "demon" controls a little door between two chambers of gas in a box. The demon can see individual molecules of gas, and it is quick enough to open and close the door such that it allows only slow particles to pass through the door in one direction, and only fast particles to pass through the door in the other direction. In this way, the slower particles congregate on one side, causing that side of the box to have a low temperature, and the fast particles congregate on the other side and create a high temperature. This thought experiment turned out to seemingly violate the second law of thermodynamics (though ultimately the second law is safe - read the full article for more information if you're interested!).

We have created a game maxwell_demon loosely based on Maxwell's Demon where the player acts as the "demon" to try and isolate particles in one of the chambers. You will implement 3 short functions in util.c to complete its implementation using bit operations.

The game screen looks as follows - there is a left chamber and a right chamber, with a barrier in the middle separating them. Each chamber is a grid, with particles at different locations within that grid. Gas particles bounce around in each of the chambers, and in this game all particles travel at the same speed.

We represent each of the two chambers as an array of 64-bit unsigned long s, where each unsigned long represents a row of the chamber. The unsigned long for a single row contains information about the gas particles (if any) in that row at that time.

The vertical barrier in the middle separating the two chambers is represented by a separate unsigned long , with a 0 at each place where there is an opening, and a 1 everywhere else - the least significant bit of the unsigned long represents the portion of the barrier at the bottom of the screen, and the more significant bits represent the portions of the barrier towards the top of the screen.

The provided code in maxwell_demon.c implements the game and animations already; your task is to implement 3 key helper functions in util.c , which are used by the provided code, to complete the implementation:

• barrier_from_openings : creates the unsigned long value for the vertical barrier based on the number of openings it should have.
• get_dir_value : gets the information for the gas particle at a given row and column number in one of the chambers.
• set_dir_value : sets the information for the gas particle at a given row and column number in one of the chambers.

(Bonus: this is not required, but if you want a particularly interesting bitwise challenge, trace through the already-implemented count_particles function in maxwell_demon.c for some cool uses of bit operations).

Before you begin, take a moment to run the sample solution (in the samples/ folder) and try out the maxwell_demon game for yourself! You can use the o and c keys to (o)pen and (c)lose the barrier, one step at a time. The object is to get all of the particles onto one side of the barrier. The difficulty changes as more particles are added, and as the simulation speeds up (you can type + to speed up, and - to slow down during the game). There are other configuration options as well - run ./maxwell_demon -h to view the full list. There is also a video below of the game in action:

For the functions below, you are not allowed to use any loops in your implementations. Instead, consider how bit operations can help you implement the necessary functionality.

Step 1: barrier_from_openings

The barrier_from_openings function returns an unsigned long correctly representing a vertical barrier with the specified details:

• barrier_openings : the number of openings in the middle of the barrier (guaranteed to be a number between 0 and 63 inclusive, and <= num_rows )
• num_rows : the number of rows high the barrier is (guaranteed to be a number between 1 and 64 inclusive)

The function should return an unsigned long as follows:

• The least-significant num_rows bits should all be 1s, with the exception of the bits representing the opening, which should be 0s and centered within the num_rows 1 bits.
• The bits in the unsigned long outside of the num_rows bits should be 0s

As an example, barrier_from_openings(3, 20) would return 0000000000000000000000000000000000000000000011111111100011111111 . This would represent a barrier with 3 openings, 20 rows high. Another way to visualize this is as follows:

Note that here, the "extra" unneeded bits in the unsigned long (beyond the least significant 20) are all 0s.

In this example with an even number of rows, if the opening size is even, then the opening should be exactly centered within the least-significant num_rows bits. If the opening size is odd (as above), the extra opening bit should be towards the least significant half (in other words, in the diagram above there are nine 1s above the opening and 8 1s below). The opening should be centered for any number of rows.

Testing Recommendation

To test barrier_openings , you can run ./maxwell_demon -test-barrier barrier_openings num_rows , where barrier_openings and num_rows are the parameters to the function. You can test for the correct values by running the solution code, as in the following example:

In particular, make sure to check edge cases for various values; as a hint, make sure to test the full range of possible values of the two parameters! . Keep an eye out in particular for shifting a value by its bitwidth or more, which is undefined behavior.

Step 2: get_dir_value

The get_dir_value function returns the bits encoding information for the particle at a given row and column index within a chamber:

• rows : an array of unsigned longs representing the rows in one of the two chambers
• row_idx : the index within rows that we want to fetch (guaranteed to be a valid index)
• col_idx : the index (from the left - i.e. col_idx = 0 refers to the leftmost index in the row) within the row that we want to fetch (guaranteed to be a valid index)

So how does an unsigned long encode information about a single row of particles? We might think we could use 1 bit per particle (1 if particle, 0 if no particle), for a total of 64 particles per row. However, in addition to storing whether there is a particle at a given index, we must also store a particle's current direction (e.g. north, south, southwest, etc.). For this reason, we will encode each particle using 4 bits ; this means each row fits 16 indexes of particles, aka 16 groups of 4 bits. Here is how those 4 bits are used to encode a particle:

• The highest-order bit encodes whether or not there is a particle at that index. 1 indicates there is a particle, and 0 indicates no particle.
• The lower three bits encode the direction of the particle, as follows:

Here are a few examples:

• 1000 would encode a particle traveling north
• 0XXX would encode no particle (the lower 3 bits do not matter in this case)
• 1100 would encode a particle traveling south

Thus, each row has 16 indexes, each 4 bits big. For example, a full row could be 0xd8009000000a000 in hex. In binary, this comes out to

This can be broken into 16 four-bit numbers, each representing one of the 16 indexes in this row. Index 0 is the leftmost group, and index 15 is the rightmost group:

rows is an array of these unsigned long encodings, which in total can represent an entire chamber. Neat!

get_dir_value should return the 4 bits that encode information about the specified row/column index. For example, if row_idx refers to the row with the above binary representation:

• if col_idx = 0 , the function would return 0 (the leftmost group of 4 bits)
• if col_idx = 1 , the function would return 13 ( 0b1101 , or 0xd ) (the second-leftmost group of 4 bits)
• if col_idx = 15 , the function would return 0 (the rightmost group of 4 bits)

To test get_dir_value , you can run ./maxwell_demon -test-get-dir row col_idx , specifying the 64-bit row value and the column number. Here are some examples (these are provided as example tests in custom_tests ):

In particular, make sure to check edge cases for various values; as a hint, make sure to test the full range of possible index values! . Keep an eye out in particular for shifting a value by its bitwidth or more, which is undefined behavior.

Step 3: set_dir_value

This function is similar to the get_dir_value function, except instead of returning the bits at the specified index, it changes the 4 bits at the specified index to a new set of 4 bits and stores that updated value back in rows . Specifically, it should overwrite whatever 4 bits are already at that index and replace them with the new bits specified .

new_value 's 4 least-significant bits are the new bits to set at the specified row/col index; all other bits in new_value beyond these are guaranteed to be 0s. As an example, let's say the specified row has the following binary representation:

If col_idx = 12 and new_value = 0x6 , rows would be updated to contain the following new value at the specified row index (underlined), completely overwriting the existing 4 bits :

To test set_dir_value , you can run ./maxwell_demon -test-set-dir row col_idx new_value , specifying the 64-bit row value, the column number and the new value to set at that index. Here are some examples:

You can also test by running the full simulation program - if you run ./maxwell_demon -h you can see the list of options, including an option to set the "random seed" (which means that the game won't be randomly different each time; the same random seed will result in the same particle behavior), and using -d for debug mode to proceed one frame at a time.

A C char is a one-byte data type, capable of storing 2 8 different bit patterns. The ASCII encoding standard ( man ascii ) establishes a mapping for those patterns to various letters, digits and punctuation, but is limited to 256 options, so only a subset are included. Unicode is ASCII's more cosmopolitan cousin, defining a universal character set that supports glyphs from a wide variety of world languages, both modern and ancient ( Egyptian hieroglyphics, the original emoji? ). This large number of characters requires a different system than just a single char , however. For this part of the assignment, you will implement the most popular Unicode encoding, UTF-8, which according to recent measurements , is used by over 93% of all websites (with known character encodings)!

Unicode maps each character to a code point, which is a hexadecimal number. There are over 1 million different code points in the Unicode standard! A character's code point is commonly written in the format U+NNNN , which signifies the hexadecimal value 0xNNNN .

However, the Unicode standard does not specify how to best encode these code points in binary. There are a variety of different possible Unicode encodings which specify, given a code point, how to actually store it. Why multiple encodings? Each may have a different priority, whether it is compatibility with other non-Unicode encodings, the locale it is intended for, space efficiency, etc. Some questions that may have different answers depending on the encoding are: should smaller code points take up the same amount of space as larger code points? If not, how can we tell how long the encoding is? And is it possible to preserve compatibility with other encodings, such as ASCII?

One of the most popular Unicode encodings is UTF-8. UTF-8 is popular partially because it preserves backwards compatibility with ASCII - in fact, it was designed such that ASCII is a subset of UTF-8, meaning that the characters represented in the ASCII encoding have the same encoding in ASCII and UTF-8. The UTF-8 encoding represents a code point using 1-4 bytes, depending on the size of the code point. If it falls in the range U+0000 to U+007F , its UTF-8 encoding is 1 byte long. If it falls in the range U+0080 to U+07FF , its UTF-8 encoding is two bytes long. And if it falls in the range U+0800 to U+FFFF , its UTF-8 encoding is 3 bytes long (there is a 4 byte range, but we'll be ignoring that for this assignment). The way UTF-8 works is it splits up the binary representation of the code point across these UTF-8 encoded byte(s) .

The utf8 program accepts code points as command line arguments and prints out their UTF-8 encoding and the actual character that encoding represents.

( Note: if your Unicode characters are not printing or appear garbled, but the encoded hex bytes are correct, you may need to set your terminal to expect UTF-8. Changing the configuration is OS/terminal-specific, but within 5 minutes of Googling we found utf8 advice for Putty , MobaXterm and Xterm . The default Mac OS X Terminal.app works by default. Note that sanity check should still pass even if your terminal is showing the wrong character.)

Your task is to implement the to_utf8 function that takes a single Unicode code point and constructs its sequence of UTF-8 encoded bytes. This function is called once for every argument specified by the user.

The to_utf8 function has two parameters; an unsigned short code_point and a byte array utf8_bytes . The function constructs the UTF-8 representation for the given code point and writes the sequence of encoded bytes into the array utf8_bytes . The first byte (e.g. leading byte) should go at index 0, and the remaining bytes (if any) should follow at index 1, etc. The utf8_bytes array is provided by the client and is guaranteed to be large enough to hold a full 3 bytes, although only 1 or 2 may be needed. While we will talk about C arrays in more depth later, it turns out that if you pass an array as a parameter, modifying the elements of that array parameter will modify the elements of the original array passed in, so the function above can pass back the byte(s) it creates. The function returns the number of bytes written to the array (either 1, 2, or 3). As an example, if code_point were 0xfc , utf8_bytes would be updated to store 0xc3 at index 0, and 0xbc at index 1, and to_utf8 would return 2.

Your to_utf8 function will need to be written to handle each of the 3 code point ranges and construct the corresponding UTF-8 encoding . You are allowed to use comparison operators to distinguish this. Your code will need to use bitmasks and bitwise operators to manually construct each byte for the UTF-8 encodings.

Testing recommendations: there are some 65,000 possible code points you could feed to utf8 , but given that they all flow through just a few distinct paths, having a test case targeted to hit each of those paths, with a little extra attention at the boundaries, should be sufficient to give you confidence about the rest.

1 Byte Encodings

If a code point is in the range U+0000 to U+007F , inclusive, its UTF-8 encoding is 1 byte. A code point in this range can be represented using at most 7 bits - called its significant bits . The significant bits are the bits that could actually store something meaningful for the code point. It's 7 here because, for a code point from 0 to 0x7f , it would need at most 7 bits to store a value in that range, which are the 7 least significant, so those are all that we care about. The UTF-8 encoding is one byte with its most significant bit 0 , and its remaining 7 bits as the seven significant bits from the code point.

Example: for code point 0x001f (which is 0001 1111 ), its UTF-8 encoding would be 0001 1111 ( 0x001f ) and to_utf8 would return 1.

2 Byte Encodings

If a code point is in the range U+0080 to U+07FF , inclusive, its UTF-8 encoding is 2 bytes. A code point in this range can be represented using at most 11 significant bits. The UTF-8 encoding is:

• The first byte has a leading 110 , followed by the 5 most significant bits in the code point
• The second byte has a leading 10 , followed by the remaining 6 significant bits in the code point

Example: for code point 0x00fc (which is 1111 1100 ), the first byte would be 1100 0011 ( 0xc3 ), the second byte would be 1011 1100 ( 0xbc ) and to_utf8 would return 2.

3 Byte Encodings

If a code point is in the range U+0800 to U+FFFF , inclusive, its UTF-8 encoding is 3 bytes. A code point in this range can be represented using at most 16 significant bits. The UTF-8 encoding is:

• The first byte has a leading 1110 , followed by the 4 most significant bits in the code point
• The second byte has a leading 10 , followed by the 6 next most significant bits in the code point
• The third byte has a leading 10 , followed by the final 6 significant bits in the code point

Example: for code point 0x4751 (which is 0100 0111 0101 0001 ), the first byte would be 1110 0100 ( 0xe4 ), the second byte would be 1001 1101 ( 0x9d ), the third byte would be 1001 0001 ( 0x91 ) and to_utf8 would return 3.

Here is a table containing the design described above. The xxx bits store the binary representation of the code point.

In a single-byte sequence, the high-order bit is always 0 , and the other 7 bits are the value of the code point itself. This is so the first 128 Unicode code points use the same single byte representation as the corresponding ASCII character!

For the multi-byte sequences, the first byte is called the leading byte , and the subsequent byte(s) are continuation bytes. The high-order bits of the leading byte indicate the number of total bytes in the sequence through the number of 1 s (for instance, the leading byte of an encoding for a code point from U+0080 to U+07FF starts with 110 , indicating the entire encoding is 2 bytes long, since there are two 1 s). The high-order bits of a continuation byte are always 10 . The bit representation of the code point is then divided across the low-order bits of the leading and continuation bytes.

Walkthrough Example: (paraphrased from Wikipedia UTF-8 page )

Consider encoding the Euro sign, €.

• The Unicode code point for € is U+20AC .
• The code point is within the range U+0800 to U+FFFF and will require a three-byte sequence. There are 14 significant bits in the binary representation of 0x20AC.
• Hex code point 20AC is binary 00100000 10101100 . Two leading zero bits of padding are used to fill to 16 bits. These 16 bits will be divided across the three-byte sequence.
• Let's calculate the leading byte. High-order bits are fixed: three 1s followed by a 0 indicate the three-byte sequence. The low-order bits store the 4 highest bits of the code point. This byte is 1110 0010 . The code point has 12 bits remaining to be encoded.
• Next, let's calculate the first continuation byte. High-order bits are fixed 10 , low-order bits store the next 6 bits of the code point. This byte is 10 000010 . The code point has 6 bits remaining to be encoded.
• Finally, let's calculate the last continuation byte. High-order bits are fixed 10 , low-order bits store the last 6 bits of the code point. This byte is 10 101100 .
• The three-byte sequence this results in is 1110 0010 10 000010 10 101100 , which can be more concisely written in hexadecimal, as e2 82 ac . The underscores indicate where the bits of the code point were distributed across the encoded bytes.

3. Saturating Arithmetic

The sat program performs a synthetic saturating addition operation. Saturating addition clamps the result into the representable range. Instead of overflowing with wraparound as ordinary two's-complement addition does, a saturating addition returns the type's maximum value when there would be positive overflow, and minimum when there would be negative overflow. Saturating arithmetic is a common feature in 3D graphics and digital signal processing applications.

The sat program accepts different numbers of arguments. With just one argument, it prints the representable range of numbers with that bitwidth:

Any additional specified arguments are added together using saturated arithmetic - for instance, if we add 126 and 5, the result overflows and sticks to the maximum value of 127.

You are to implement these 3 functions for the sat program. You are encouraged to call any of these functions from any of the others as needed to share logic!

For these 3 functions, you may not use the following in your implementations:

• No relational operators or math.h functions . You are prohibited from making any use of the relational operators. This means no use of < > <= >= . You may use != == and all other operators (arithmetic, logical, bitwise, ...). You also should not call any function from the floating point math.h library (e.g no pow , no exp2 ). These restrictions are intended to guide you to implement the operation via bitwise manipulation.
• No special cases based on bitwidth. Whether the value of bitwidth is 4, 64, or something in between, your functions must use one unified code path to handle any/all values of bitwidth without special-case handling. You should not use if switch ?: to divide the code into different cases based on the value of bitwidth. This doesn't mean that you can't use conditional logic (such as to separately handle overflow or non-overflow cases), but conditionals that dispatch based on the value of bitwidth or make a special case out of one or more bitwidths are disallowed.
• No loops or recursion. No loops or recursion at all. (In particular, no loop increment by one and stop at max.)

A solution that violates any of these restrictions will receive zero credit , so please verify your approach is in compliance!

Testing recommendations : your custom tests should cover a variety of different bitwidths, including extreme values, and on sums within range as well as those that overflow.

Step 1: signed_min

signed_min returns the smallest value representable in bitwidth bits. bitwidth is a number between 4 and 64, inclusive. Note, however, that the function returns a long ; your function needs to return the minimum value, but correctly represented in 64 bits, not just bitwidth bits. As an example, with a bitwidth of 4, the min is binary 1000 , which represents the value -8. We want to return the value -8 but represented using 64 bits, which would be 11111...1000 . As a hint, try writing out what the signed min values are for different bitwidths, and see if you notice a pattern in how to go from a given bitwidth to its signed min binary representation. Your goal is to determine an expression based on bitwidth that evaluates to the correct long value. Once you implement this function, you should be able to run sat with just the bitwidth argument and see the correct value outputted for the min.

Step 2: signed_max

signed_max returns the largest value representable in bitwidth bits. It works the same as signed_min , but for the largest value instead of the smallest. Like signed_min , the function returns a long ; your function needs to return the maximum value, but correctly represented in 64 bits, not just bitwidth bits. As an example, with a bitwidth of 4, the max is binary 0111 , which represents the value 7. We want to return the value 7 but represented using 64 bits, which would be 000....0111 . As a hint, try writing out what the signed max values are for different bitwidths, and see if you notice a pattern in how to go from a given bitwidth to its signed max binary representation. You may also notice similarities with your signed_min implementation. Once you implement this function, you should be able to run sat with just the bitwidth argument and see the correct value outputted for the max.

Step 3: sat_add

sat_add returns the saturated addition of the two operands which are guaranteed to fit in bitwidth bits. This means:

• If the sum of the operands does not overflow, we just return the sum
• If the sum of the operands overflows past the max, return the max
• If the sum of the operands overflows past the min, return the min

Remember that you may not use relational operators such as < or > .

The key idea is to try and develop a way to examine a value's binary representation to know whether it has overflowed its bitwidth. As a hint, try picking a bitwidth such as 4, and write out some addition operations that do and don't overflow. Then ask yourself - by looking at the operands and the sum, did this addition overflow? How did I know that? When is it possible for overflow to occur?

4. Case Study: Ariane-5

Once you have implemented your sat program, you will have a taste of functions that work around overflow (completing sat is not required to complete this part, but provides context). Overflow errors can cause many problems, which we saw some examples of in lecture. These errors are not very common, but they can be disastrous when they occur. Read through this article explaining an issue experienced by the European Space Agency, and answer the following questions in the readme.txt file.

View Ariane-5 Article

1) What was the cause of the Ariane 5 rocket failure, and why was it not detected before the rocket was launched? Write your answer in 3-5 sentences.

2) Imagine that you are developing software for Ariane 6. You notice that Ariane 6 takes the average of two different sensors' measurements of horizontal velocity (which are stored as int s) by adding them together and dividing by 2, as in the following code:

What issues might arise from this calculation? How would you test for other potential overflow issues that could arise before the launch date? Write your answer in 3-5 sentences. Note: There are many possible answers to this question. Your answer should rely on critical reflection about appropriate testing strategies.

Submitting and Grading

Once you are finished working and have saved all your changes, check out the guide to working on assignments for how to submit your work. We recommend you do a trial submit in advance of the deadline to familiarize yourself with the process and allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work.

When you submit, you may optionally indicate that you do not plan to make a submission after the on-time deadline. This allows the staff to start grading some submissions as soon as the on-time deadline passes, rather than waiting until after the late period to start grading.

• When in doubt, it's fine to indicate that you may make a late submission, even if you end up submitting on time
• If you do indicate you won't submit late, this means once the on-time deadline passes, you cannot submit again. You can resubmit any time before the on-time deadline, however.
• If you want to change your decision, you can do so any time before the on-time deadline by resubmitting and changing your answer.
• If you know that you will not make a late submission, we would appreciate you indicating this so that we can grade assignments more quickly!

You should only need to modify the following files for this assignment: readme.txt , sat.c , util.c , utf8.c , custom_tests

We would also appreciate if you filled out this homework survey to tell us what you think once you submit. We appreciate your feedback!

Below is the tentative grading rubric. We use a combination of automated tests and human review to evaluate your submission. More details are given in our page linked to from the Assignments dropdown explaining How assignments are graded .

Readme Answers (10 points)

Code Functionality (80 points)

• Sanity cases . (30 points) The default sanity check tests are used for sanity grading.
• Comprehensive cases . (45 points) We will thoroughly test on a variety of an additional inputs ranging from simple to complex, including edge conditions where appropriate.
• Custom sanitycheck tests (5 points) Your custom_tests file should include at least 10 tests of your own, 3-5 per program, that show thoughtful effort to develop comprehensive testing coverage. Please include comments that explain your choices. We will run your custom tests against your submission as well as review the cases to assess the strength of your testing efforts.
• Clean compile . (2 points) We expect your code to compile cleanly without warnings.

Code Quality (buckets weighted to contribute ~10 points)

The grader's code review is scored into buckets to emphasize the qualitative features of the review over the quantitative. The styleguide is a great overall resource for good program style. Here are some highlights for this assignment:

• Bitwise manipulation . We expect you to show proficiency in bitwise manipulation through clean construction and use of masks and proper application of the bitwise operations.
• Algorithms. Your chosen approach should demonstrate that you understand how to leverage bit patterns and numeric representation to directly and efficiently accomplish the task. Avoid unnecessary divergence and special-case code; unify into one general-purpose path wherever possible.
• Style and readability. We expect your code to be clean and readable. We will look for descriptive names, defined constants (not magic numbers!), and consistent layout. Be sure to use the most clear and direct C syntax and constructs available to you.
• Documentation. You should document both the code you wrote and what we provided. We expect program overview and per-function comments that explain the overall design along with sparing use of inline comments to draw attention to noteworthy details or shed light on a dense or obscure passage. The audience for the comments is your C-savvy peer.

Post-Assignment Check-in

How did the assignment go for you? We encourage you to take a moment to reflect on how far you've come and what new knowledge and skills you have to take forward. Once you finish this assignment, you will have completed your first C programs manipulating bits, and understood more about the limitations of integer representations! This assignment may definitely have a bit of a learning curve getting used to the write/compile/debug process in C and the command line. Celebrate this important milestone; the skills you develop now will pay off throughout the quarter!

To help you gauge your progress, for each assignment/lab, we identify some of its takeaways and offer a few thought questions you can use as a self-check on your post-task understanding. If you find the responses don't come easily, it may be a sign a little extra review is warranted. These questions are not to be handed in or graded. You're encouraged to freely discuss these with your peers and course staff to solidify any gaps in you understanding before moving on from a task. They could also be useful as review before exams.

• Consider all negative int s whose absolute value is an exact power of two (-8, -32 and so on). What do their bit patterns have in common?
• How can you determine if an integer bit pattern has a pair of consecutive 'on' bits? (Straightforward to do using a loop, but there is also a clever single expression...)
• How can integer limitations manifest themselves in real-world software?
• A treasure trove of bit wizardry curated by Sean Anderson, Stanford CS PhD.

To help approach this assignment, we've compiled some tips that may help with the various problems, as well as bit manipulation in general.

Don't use 0b -prefixed literals. There is no official support in C for numbers written in binary with 0b . We used this form in lecture to explicitly write out binary numbers, but it's not something you can use in standard C programs. Instead, you should... (see the next part)

Embrace hexadecimal. The base-16 system very conveniently translates to and from binary -- each byte is expressed in two hex digits, one hex digit for the 4 high-order bits, the other for the 4 low bits. Masks in hex or expressed via their construction are more evocative of the binary representation and help you avoid mistakes. For example, a mask to extract the sign bit from a 32-bit value can be cleanly expressed as 1 << 31 or 0x80000000 and both are quite readable. The mask also happens to be decimal 2147483648U , but who can tell? Would you notice if you had accidentally mistyped 2147486348U ? Say no to decimal, hex is your pal!

Learn your bitwise operators. It is wasteful to invoke the (expensive, floating-point) pow function to compute integer powers of two: 1 << 10 does a perfect job of computing pow(2, 10) and requires way fewer compute cycles. The bitwise operations are also the right tools to rearrange/isolate/change bits as opposed to the more indirect use of integer multiply/divide/mod with powers of two.

Aim for directness. There may be more direct ways to write certain bit manipulations. Here are a few:

No left-shift right-shift . In the code below, the first version right-shifts then immediately left-shifts back. This seems to just cycle the bits back to where they were originally, but in fact the right-shift will discard the lsb and the left-shift will then zero-fill. This is roundabout way to wipe the lsb, but the better approach is to just directly mask it off as in second version:

No redundant/unnecessary ops . Imagine your goal is to extract the 4 high-order bits of a byte and shift them down to the lower half-byte. You could do it with two steps (mask and shift), but in fact, the shift will already discard the low-order bits, so there's no need to mask them off first!

Know your identities/relationships . When putting together a bitwise construction, stop and consider whether there is a more direct way to accomplish the same thing, e.g.

At first you may find yourself using a longer expression than needed, but reviewing in a later pass, you can spot these issues and make them more concise. The goal is eventually to go straight to the most direct expressions from the beginning.

Frequently Asked Questions

I'm getting the error warning: left shift count >= width of type . what does this mean.

Code such as this will produce that warning:

An integer constant defaults to type int , so shifting a 32-bit int by 32 positions would effectively shift off all the bits, and thus the compiler warns about it. Assigning the result to a variable of type long (64 bits) doesn't help; you have to start with a 64-bit value if you intend to compute a 64-bit result. Read the next question!

What bitwidth and signedness does a numeric integer constant have?

An integer literal is a signed int by default. Suffixes can be added to the constant to dictate its type. A suffix of L indicates the type is long and U (either by itself or with L ) indicates it is unsigned. E.g. 1UL means a literal 1 that is an unsigned long.

What are the rules for integer promotion in C?

When assigning from narrower bitwidth (e.g. char, short) to a wider one, the source bytes are copied to the low-order bytes of the destination, and the upper bytes are assigned based on the promotion rules. If the source type was unsigned, the upper bytes of destination are zero-filled. If the source type was signed, its sign bit (the msb) is replicated across the upper bytes of destination (this is called sign extension). It may help to trace through this and confirm for yourself how/why this is value-preserving. If an operation is performed on two operands of mixed type, integer promotion is implicitly applied to the narrower first. It also the case (and a bit surprising, too) that integer promotion is also applied to types narrower than int when an operation is performed on them, even if no other wider type is involved. For example, the bitshift and invert operations promote the operand to an int, so bit-shifting a char will promote to an int before shifting, bit-inverting of a char similarly promotes, and the default result type of these expressions will be int. If the bitwidth of the operand was larger than int, the bitwidth will be unchanged by these promotion rules.

• Study Guides
• Homework Questions

Module 3 - Completed