Last Updated: 2024-09-17 Tue 14:46

CMSC216 HW04: Review for Exam 1

CODE DISTRIBUTION: hw04-code.zip

  • Download the code distribution every lab
  • See further setup instructions below

CHANGELOG: Empty

1 Rationale

This HW reviews concepts from earlier labs and lecture to prepare for an exam. Solutions to the this HW along with past HWs will be posted within a few days to aid in students as they prepare for Exam 1. You may wish to consult with TAs during lab or office hours if you are unsure of how to solve problems as the exam is likely to have similar problems.

Associated Reading / Preparation

  • C References: Basics of C programming including control structures, pointers/addresses, memory allocation/deallocation, bit operations
  • Bryant and O'Hallaron: Ch 2.1-2.3 on binary representations of integers in unsigned and two's complement signed format.

Grading Policy

Credit for this HW is earned by taking the associated HW Quiz which is linked under Gradescope. The quiz will ask similar questions as those that are present in the QUESTIONS.txt file and those that complete all answers in QUESTIONS.txt should have no trouble with the quiz.

Homework and Quizzes are open resource/open collaboration. You must submit your own work but you may freely discuss HW topics with other members of the class.

See the full policies in the course syllabus.

2 Codepack

The codepack for the HW contains the following files:

File Description
QUESTIONS.txt Questions to answer
dog_diagram.c C file for Problem 1
badmem.c C file for Problem 2
best_score.c C file to complete for Problem 3
scores1.txt Data file for Problem 3
scores2.txt Data file for Problem 3
scores3.txt Data file for Problem 3
scores-empty.txt Data file for Problem 3

3 What to Understand

Ensure that you have a good understanding of C programming, memory layout, and the binary representations of integers.

4 Questions

Analyze the files in the provided codepack and answer the questions given in QUESTIONS.txt.

                           _________________

                            HW 04 QUESTIONS
                           _________________


Write your answers to the questions below directly in this text file to
prepare for the associated quiz. Credit for the HW is earned by
completing the associated online quiz on Gradescope.


PROBLEM 1: Memory Diagram
=========================

  Examine the code in dog_diagram.c which uses a couple simple functions
  with a struct.
  ,----
  |  1  #include <stdio.h>
  |  2  typedef struct{
  |  3    double weight;
  |  4    int age;
  |  5    char name[8];
  |  6  } dog_t;
  |  7  
  |  8  void init_dog(dog_t *d){
  |  9    strcpy(d->name, "Rolf");
  | 10    d->age = 0;
  | 11    d->weight = 5.0;
  | 12    ////// POSITION A
  | 13    return;
  | 14  }
  | 15  
  | 16  void birthday(int num, dog_t *d){
  | 17    int next = d->age + num;
  | 18    if(next < 3){
  | 19      d->weight += 10.0;
  | 20    }
  | 21    ////// POSITION B
  | 22    d->age = next;
  | 23    return;
  | 24  }
  | 25  
  | 26  int main(){
  | 27    dog_t dog;
  | 28    init_dog(&dog);
  | 29    double curwgt = dog.weight;
  | 30    birthday(2, &dog);
  | 31    printf("%s gained %f pounds\n",
  | 32           dog.name, dog.weight-curwgt);
  | 33    return 0;
  | 34  }
  `----

  Fill in the memory diagrams below for the layout of memory if
  execution stops at the positions given in the comments.


POSITION A
----------

  ,----
  | |------------+-------------+-------+-------|
  | | Frame      | Sym         | Addr  | Value |
  | |------------+-------------+-------+-------|
  | | main()     | curwgt      |       |       |
  | | line:28    | dog.name[7] |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             | #1208 |       |
  | |            | dog.weight  | #1200 |   5.0 |
  | |------------+-------------+-------+-------|
  | | init_dog() | d           |       |       |
  | | line:??    |             |       |       |
  | |------------+-------------+-------+-------|
  `----


POSITION B
----------

  ,----
  | |------------+------------+-------+-------|
  | | Frame      | Sym        | Addr  | Value |
  | |------------+------------+-------+-------|
  | | main()     | curwgt     |       |       |
  | | line:??    |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            | #1208 |       |
  | |            | dog.weight | #1200 |       |
  | |------------+------------+-------+-------|
  | | birthday() |            | #1192 |       |
  | | line:??    |            |       |       |
  | |            |            |       |       |
  | |------------+------------+-------+-------|
  | 
  `----


PROBLEM 2: Valgrind Debugging badmem.c
======================================

  The file badmem.c has functions main() and set_pn() in it but has a
  bad memory problem associated with it.  A sample compile and run is as
  follows.

  ,----
  | > gcc -g badmem.c
  | > a.out
  | Segmentation fault (core dumped)
  `----


A
~

  Below is some output from Valgrind. Explain the errors that are
  identified by Valgrind and inspect the source code of badmem.c to
  discover the source of the error. Clearly identify whether there is a
  problem in main() or set_pn().

  ,----
  | >> cat -n badmem.c                       # show code for badmem.c
  |      1	#include <stdio.h>
  |      2	#include <stdlib.h>
  |      3	
  |      4	
  |      5	// Struct to count positive/negative
  |      6	// numbers in arrays.
  |      7	typedef struct {
  |      8	  int poss, negs;
  |      9	} pn_t;
  |     10	
  |     11	void set_pn(int *arr, int len, pn_t *pn);
  |     12	// Scans through array arr counting positive/negative numbers and
  |     13	// adjusting the fields of the specified. Zero is considered a
  |     14	// positive number. If arr is NULL or len is less than 0, does not
  |     15	// change pn.
  |     16	
  |     17	int main(){
  |     18	  int arr1[5] = {3, 0, -1, 7, -4};
  |     19	  pn_t *pn1;
  |     20	  set_pn(arr1, 5, pn1);
  |     21	  // pn1: {.poss=3, .neg=2}
  |     22	  
  |     23	  int arr2[3] = {-1, -2, -4};
  |     24	  pn_t *pn2;
  |     25	  set_pn(arr2, 3, pn2);
  |     26	  // pn2: {.poss=0, .neg=3}
  |     27	
  |     28	  int *arr3 = NULL;
  |     29	  pn_t *pn3;
  |     30	  set_pn(arr3, -1, pn3);
  |     31	  // pn3: NULL
  |     32	
  |     33	  return 0;
  |     34	}
  |     35	  
  |     36	void set_pn(int *arr, int len, pn_t *pn){
  |     37	  if(arr==NULL || len < 0){
  |     38	    return;
  |     39	  }
  |     40	  pn->negs = 0;
  |     41	  pn->poss = 0;
  |     42	  for(int i=0; i<len; i++){
  |     43	    if(arr[i] < 0){
  |     44	      pn->negs++;
  |     45	    }
  |     46	    else{
  |     47	      pn->poss++;
  |     48	    }
  |     49	  }
  |     50	  return;
  |     51	}
  | 
  | >> gcc -gc badmem.c                      # compile with debug information
  | 
  | >> valgrind ./a.out                      # run compiled program under valgrind
  | ==15611== Memcheck, a memory error detector
  | ==15611== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
  | ==15611== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
  | ==15611== Command: ./a.out
  | ==15611== 
  | ==15611== Use of uninitialised value of size 8
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611== 
  | ==15611== Invalid write of size 4
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611==  Address 0x5 is not stack'd, malloc'd or (recently) free'd
  | ==15611== 
  | ==15611== 
  | ==15611== Process terminating with default action of signal 11 (SIGSEGV): dumping core
  | ==15611==  Access not within mapped region at address 0x5
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611==  If you believe this happened as a result of a stack
  | ==15611==  overflow in your program's main thread (unlikely but
  | ==15611==  possible), you can try to increase the size of the
  | ==15611==  main thread stack using the --main-stacksize= flag.
  | ==15611==  The main thread stack size used in this run was 8720384.
  | ==15611== 
  | ==15611== HEAP SUMMARY:
  | ==15611==     in use at exit: 0 bytes in 0 blocks
  | ==15611==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
  | ==15611== 
  | ==15611== All heap blocks were freed -- no leaks are possible
  | ==15611== 
  | ==15611== For counts of detected and suppressed errors, rerun with: -v
  | ==15611== Use --track-origins=yes to see where uninitialised values come from
  | ==15611== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
  | Segmentation fault (core dumped)
  `----


B
~

  Fix badmem.c so that it works correctly. Your fix should NOT change
  the prototype for the set_pn() function but can make other adjustments
  to local variables.


PROBLEM 3: Number Conversions
=============================

  Complete the following table of conversions between CS numbering
  systems. The "Signed Decimal" column presumes the Two's Complement
  convention for number representation; review this with a TA if you are
  not clear on it.

  ,----
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       | Unsigned | Signed  |
  | | Num | Binary    |  Hex | Octal |  Decimal | Decimal |
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       |          |         |
  | |   1 | 1011 1000 |      |       |      184 |         |
  | |     |           |      |       |          |         |
  | |   2 |           | 0x80 |  0200 |          | -128    |
  | |     |           |      |       |          |         |
  | |   3 | 0011 0010 | 0x32 |       |       50 |         |
  | |     |           |      |       |          |         |
  | |   4 |           |      |  0234 |      156 |         |
  | |     |           |      |       |          |         |
  | |-----+-----------+------+-------+----------+---------|
  `----


PROBLEM 4: Best Score in File
=============================

  A grading file has scores for an exam formatted as in the following
  example:
  ,----
  | Darlene 91.0
  | Angela  76.5
  | Elliot  94.5
  | Tyrell  87.5
  | Dom     70.0
  | Phillip 55.5
  `----
  The names of students are the first item followed by a numeric score
  on their programming exam.  Write `main()' function in the file
  `best_score.c' which
  - Opens the file
  - Reads through all the contents
  - Prints out the name and score of the highest scorer

  Make use of the following small struct in this exercise to ease the
  process of copying information as indicated.
  ,----
  | typedef struct {
  |   char name[128];               // name of student
  |   double score;                 // score on exam
  | } grade_t;
  | // struct which allows assignment of name/score such as in
  | //   best = curgrade;
  | //   printf("best is now: %s %f\n", best.name, best.score);
  `----
  - Don't forget to close the file
  - Study the session below for special cases such as empty files

  ,----
  | > gcc -g best_score.c
  | > ./a.out 
  | usage: ./a.out <filename>
  | <filename> should have columns of names, numbers as in
  | Darlene 91.0
  | Angela  76.5
  | Elliot  94.5
  | Tyrell  87.5
  | Dom     70.0
  | Phillip 55.5
  | > ./a.out scores1.txt
  | Best score: Elliot 94.500000
  | > ./a.out scores2.txt 
  | Best score: Student13 90.800000
  | > ./a.out scores3.txt 
  | Best score: Student43 99.300000
  | > ./a.out scores-empty.txt
  | file was empty
  | > ./a.out no-such-file.txt
  | could not open the file
  `----

Author: Chris Kauffman (profk@umd.edu)
Date: 2024-09-17 Tue 14:46