Exam #3 study guide

You should be receiving an email with your seat assignment sometime before 9:00 AM today (Wed 12/14). This exam is OPEN BOOK for both sections. The exam is in WTHR 200 @ 10:30am-12:30pm. Bring your reference sheet.

The scope of exam #3 will include everything we have done up to the exam date, including homework, lectures, and the relevant parts of the reference sheet—except Vim. This exam will be open book for both sections.

Before the exam, you must do a few things.

1. Bring your course reference sheet. ⇐ IMPORTANT
2. Read the policies to learn the rules (e.g., what items are allowed, etc.).
3. Check your email the morning of the exam for your assigned seat number.
4. Bring photo ID.
5. Use the restroom. Bathroom breaks are not allowed.

Topics

Exam #3 questions will be drawn from the topics below.

The example questions are to help you self-test your understanding. They are not exhaustive. Actual exam questions may be of a different form.

1. memory
   1. representing numbers (number bases and ASCII)
      1. Convert a number from any base to any other base (between 2 and 36). Example: convert 0x3f (hexadecimal) to base 27.
      2. Understand the relationship between (a) number base used to express numbers in your code, (b) representation in memory with no number base, and (c) number base used to print numbers on the screen.
      3. Understand the relationship between digit characters (e.g., '5') and the values they traditionally represent (e.g., the result of two plus three).
      4. Given a single character (e.g., 'A') show how it would look when stored in memory.
      5. Explain why 6 * 8 == '0'.
      6. Write a print_integer(…) function that works with only integers between 0 and 9.
   2. memory model
      1. Draw the state of memory as of line ██ in the given code using this memory form.
      2. Fill in the blanks in a GDB session.
      3. Given a small program, draw the call stack, including the parameters, return address, and local variables. For the return address, it's okay to be vague (e.g., "somewhere in main(…)).
      4. Given a small program, say what data is in the stack segment, heap segment, data segment, and text segment.
      5. Read and write code that uses memory addresses, arrays, or strings, including any of the syntax in your reference sheet under addresses (pointers), arrays, and strings.
      6. Find the bug(s) in a small program that uses memory addresses.
      7. Describe code using memory addresses in English phrases such as "__ gets the address of __," "__ gets the value at __," "__ gets the address of a new allocation block sufficient for __," and "store __ at address __.".
      8. Predict the output of a function that receives a memory address as a parameter and uses it to modify local variables of the caller and/or memory on the heap.
      9. Write a swap function.
      10. Use arithmetic operators with memory addresses to find the i'th element of an array, either on the stack or in the heap. (It doesn't really matter.)
   3. malloc(…)
      1. Given a small program that uses malloc(…) and free(…), draw the contents of the stack and heap at a given point in the execution.
      2. Write a very small program that allocates and deallocates memory for an array and/or a single value on the heap. For example, write a program that allocates an array of 3 integers, fills it with values, and then frees it.
      3. Find the bug(s) in a small program that uses malloc(…).
      4. (See the memory safety section below for more.)
   4. stack frames and function calls (low-level, x64 architecture)
      1. What happens on the stack when a function is called?
      2. How are $rbp (base pointer) and $rsp (stack pointer) used to demarcate a stack frame?
      3. What happens with $rbp (base pointer), $rsp (stack pointer), and $rip (instruction pointer) when a function is called?
      4. What happens in the prologue and epilogue of a function?
2. memory safety
   1. basics
      1. Detect and fix any of the types of memory faults listed on the back of your reference sheet. (We have touched on some of these already, but we will go over all of them on Mon 9/19. However, most should be self-explanatory from the examples given on your reference sheet.) To practice, try to create buggy programs that illustrate those problems. Then, compile your buggy programs and run them in valgrind.
   2. segmentation faults – causes and diagnosis
      1. Fix the given code to stop it from triggering a segmentation fault.
      2. Write a single line of code that causes a segmentation fault by writing memory.
      3. Write a single line of code that causes a segmentation fault by reading memory.
      4. Write a single line of code that causes a segmentation fault using va_arg(…).
      5. Write a single line of code that causes a segmentation fault without any of the following characters: < > . * & [ ]
      6. Give the GDB commands that you would use to diagnose the segmentation fault from the given code.
      7. The following code triggers a segmentation fault. What are all of the possible causes?
   3. Valgrind messages – know everything on the back of the reference sheet
      1. Fill in the blanks in the given Valgrind output.
      2. For which of the following bugs would GDB be the best tool to diagnose?
      3. Which of the following messages would result from the following buggy code?
   4. buffer overflow attacks
      1. How does an attacker perpetrate a buffer overflow attack?
      2. How can gdb be used in perpetrating an attack?
      3. How can you write C code that is resistant to such attacks?
3. data structures and algorithms
   1. linked lists
      1. Find the bug in the given code.
      2. Write a good test case to catch the bug at line ██ in the given code.
   2. data types
      1. In the following snippet, what is the type of the expression *n[2]?
      2. In GDB, what would whatis ██ print?
   3. binary search trees (BSTs) — including pre-order, in-order, post-order traversal
      1. Draw the state of memory as of line ██ in the given code using this memory form.
      2. Find the bug in the given code.
      3. Write code to do a post-order traversal of a given BST.
      4. What kind of traversal does the given code accomplish?
   4. sorting – including merge sort, qsort(…), and tree sort
      1. Draw the state of memory as of line ██ in the given merge sort code using this memory form.
      2. Write code to sort struct Person objects using qsort(…)
      3. Fix the given (broken) compare function for qsort(…)
      4. Compare two implementations of merge sort or tree sort and say which is correct, or if there are any other subtle differences.
      5. Look at a buggy merge sort or tree sort and predict the output.
      6. Say when a buggy implementation of merge sort or tree sort will work and when it won't.
      7. Fill in the blanks in an incomplete merge sort or tree sort.
   5. recursion
      1. Predict what a simple recursive function will print or return.
      2. Predict the number of times a recursive function will call itself.
      3. Draw the state of memory as of line ██ in the given code using this memory form.
4. C language
   1. structures
      1. Write a struct type definition suitable for writing programs about mechnical pencils.
      2. Rewrite the following struct type definition using the more concise typedef syntax.
   2. C syntax related to addresses, struct objects, and arrays – including effects of * and & on type, equivalence of address operators on the reference sheet
      1. Rewrite line ██ without using the * operator.
      2. Rewrite line ██ without using the . operator.
   3. function addresses
      1. What is a function address? What will you find at that memory address? Where else could you find the same bytes?
      2. If f is the address of a function, in what segment is the memory f refers to?
      3. How can you find information about pthread_create(…) without Google?
      4. Explain why qsort(…) takes a function address as a parameter.
      5. Write a function that takes a function address as an argument.
      6. Given a variable containing a function address, call the function.
      7. What is a function address?
      8. What does a function address look like in GDB?
   4. sizeof(…)
      1. What will sizeof(██) return (e.g., sizeof('0'))?
      2. Find the bug in the given linked list or BST code (where the bug is due to a faulty use of sizeof(…)).
   5. preprocessor
      1. What are the three ways to use #define?
      2. How do you make a macro that takes arguments?
      3. What can you do with a macro that you can't do with a function?
      4. What can you do with a function that you can't do with a macro?
      5. What are the "two rules" regarding parentheses with preprocessor macros? What can go wrong if they are not followed?
   6. variadic functions.
      1. Write simple programs using variadic functions. For example, make a function that takes one or more characters as arguments and prints them as a string.
      2. Understand the difference between accessing arguments in a variadic function versus accessing elements from an array. What can one do that the other can't?
      3. Give an example of something va_copy lets you accomplish that you couldn't do otherwise.
5. files
   1. file basics
      1. How can a struct object be stored in a binary file?
      2. What do we mean by a "binary file" (as opposed to a "text file")?
      3. How are things like tabs and new lines represented in files?
      4. What do the following do? How are they useful? fopen(…), fread(…), fwrite(…), fclose(…), fseek(…), ftell(…)
      5. What are the three modes for opening files, and how are they different?
      6. What would happen if you try to read objects in a different order than they were written? You have to think about the bytes in the file and in memory and work through the endian-ness.
   2. endian-ness
      1. Is ecegrid little endian or big endian? ... and what does that mean?
      2. How are colors represented in BMP?
      3. How is little endian different from big endian?
      4. Is the BMP file format little endian or big endian? ... and what does that mean?
6. threads and processes
   1. What is the relationship between threads and processes?
   2. How does pthread_create(…) and pthread_join(…) affect the flow of execution? (Some might find the diagram used in class to be helpful for visualizing this.)
   3. What are three options for boosting the performance of a program?
   4. What is the most important way to improve performance of a program?
   5. How do you compile code that uses the pthread library?
   6. What is a process? What does it encompass?
   7. How much could multi-threading improve the performance of a program?
   8. Given some code, say whether the threads might end up writing to the same memory at the same time, or reading from memory that could be written to at unpredictable times.
   9. Suggest how to divide up the threads for a problem.
   10. Write a worker function, or correct an existing one.
7. software engineering
   1. test-driven development
      1. Given a planned sequence of steps for constructing a program, find any flaws in the plan.
      2. Given a description of a program to be built, write out the first few steps, following TDD.
      3. Explain the benefits of TDD.
      4. Explain how you used (or could have used) TDD on one of the assignments so far.
      5. Suggest the next step in the given TDD sequence for the given code.
   2. code quality – know all of the code quality standards, including reasons for each rule; you are expected to read the code quality standards carefully
      1. Fix the given poor quality code.
      2. Make the given code worse by breaking more rules.
      3. Give an example of what could go wrong if we didn't follow rule ██.
      4. Critique the given code, according to the code standards used in this class.
      5. What is the purpose of capitalizing struct types (e.g., struct Node not struct node)?
      6. Why is it bad to mix tabs and spaces for indent?
      7. Given some poorly-written code, identify and/or fix the problems relative to the Code Quality Standards used in this class.
      8. Given a code quality problem, explain why it might lead to bugs and/or make the code more difficult to read or maintain.
   3. code deduplication (DRY rule)
      1. Dedupe the given code.
      2. Give a few advantages of deduped code.
   4. software testing — including edge cases, corner cases
      1. Write a test case that would reveal the bug at line ██ in the given code.
      2. What is missing from the following test suite?
      3. Cross out the test that is truly redundant.
   5. gdb
      1. Know the following commands, including how to use them and what output to expect: backtrace, break, continue, display, down, finish, info locals, info args, info breakpoints, help, list, next, return, run, set args, step, until, up, watch, whatis, p/…, and x/….
         Note: For an open book exam, we will not deliberately test memorization of commands, but we may assume some familiarity with GBD and its commands, especially for the purpose of testing other concepts, or testing your knowledge of how to debug different kinds of errors.
      2. Fill in the blanks in a GDB session, especially for the purpose of testing understanding of memory or other concepts.
      3. What does p/ tell you that x/ doesn't? … and vice versa?
      4. What kind of bugs can GDB help you find?
      5. Explain the conceptual and practical differences between breakpoints and watchpoints.
      6. Given a description of a need (e.g., "run the program, break at line 25, and print the value of n as hexadecimal"), give the appropriate commands.
      7. Given a GDB session with the commands removed, give the command that would produce the given output.
      8. What command will print the type of variable a?
      9. What command will cause gdb to break (stop executing your program) whenever the value of n changes?
      10. What command will display all local variables in the current frame?

Review session

Prof. Quinn will hold a review session Fri 12/9 at 10:30-11:20am in MATH 175. All are welcome (up to safe room capacity).

Past exams and quizzes

Below are all the past exams and quizzes we could dig up. Some of these may include topics that are not in scope for the current final exam. Also, the emphasis in ECE 26400 shifts slightly from semester to semester. Some of these have been edited slightly since first given (e.g., to correct typos). The list of topics above is your guide to the scope for this semester's final exam.

Lu

Quinn

Not in scope

The following are not in scope for this exam.

• Vim commands
• bash commands—except that questions may assume that you understand the commands to run gcc, gdb, and valgrind commands, and your own program, from the command line
• motivating discussion of code quality from day 1
• assert(…)
• Big-O
• BSS segment

Updates