Final Programming Check

 Background:

In PC1 you had a good deal of specific preparation for the problem you were asked to solve. The purpose of this final check is to verify that you can handle a wider variety of problems without requiring such specific preparation.

For the final programming check I will give you a problem similar to one of those described below, but requiring different data and probably a different combination of basic operations. But the basic operations required will be drawn from this list.

How to prepare:

Be SURE you can write, compile and run ALL of the following kinds of programs. To do this you should not only do all of the examples shown, but you should also devise and solve another example of each kind (a good way to do this would be to trade problems with members of your team or other classmates.)

I've included solutions at the end of the notes.

If you have trouble with ANY of this material, it's critically important that you (1) ask about the material in class (2) work with your team mates on it (3) come and see Clayton (4) work with the TA.

Note that knowledge, speed and skill are interrelated. You need to be sure you can solve problems of this kind reliably and fast, not just be able to do them "eventually". So just "knowing the concepts" is not enough. As with any skill, which is what programming largely is, practice makes perfect, practice makes reliable, and practice makes fast.

Being able to solve these problems fast is not an artificial requirement arising from the time constraints of the Programming Check. Look ahead to next semester's course: your work there and in later courses will assume that you will need little time to deal with issues at this level, so you can concentrate on the new material without being distracted by wrestling with the basics.

Do not spend time committing this material to memory, since you will have access to these notes during the Programming Check. Concentrate on understanding the material and (most important) being able to write programs that work.

Priorities:

Passing this Programming Check is MORE IMPORTANT than contributing to your team project. Take the time you need to master this material as the semester nears its end!

The Problems:

I. Representing collections.

You should be able to define a struct that contains an array of elements, which could themselves be structs, and a count, and perform the following operations on it. In the examples I use the following structs:

struct student_record

{

int student_no;

int grade;

};

struct grade_book

{

struct student_record records[MAX];

int count;

};

Make the collection empty (by setting its count to 0)

 

Get the value of an element, given its position (subscript) in the collection (if possible, and indicate if not possible.

Be sure to check that the subscript is in range!

Add a new element on the end (if possible, and indicate if not possible)

Remove an element from anywhere in the collection, and repack the contents (if possible, and indicate if not possible)

Remember that all of the "good" elements of a collection have to be packed into the slots 0...count-1, with no gaps. Also remember that you can't remove something from an empty collection, and that you can't remove something from a position (subscript) out of range.

Perform an operation, by calling a function, on or with each element of the collection.

Ex: increase all the grades in the gradebook by calling a function that adds 1 to a grade

Find the sum or product or ... of the elements or parts of elements in the collection... use the Running Total Plan (or a variant)

Ex: Find the overall average grade in a grade book...find the sum and divide by the count

 

Find the position or the value of minimum or maximum element in the collection (if possible, and indicate if not possible)...use the Knockout Plan

Ex: (minimum student no, give position)

Ex: (maximum grade, give the student record)

 

Find find the position or the value of an element in the array that satisfies some property (if possible, and indicate if not)

Ex: Find value of a student record that has a given student number

 

II. Other operations

read an element from a file (if possible, and indicate if not possible)

Ex: read a student record

 

read an element from the keyboard (and detect an entry indicating user wants to quit)

Ex: Read a student record; user types -1 instead of student number to quit

 

print an element

Ex: Print a student record.

 

III. Combinations

The above operations can be combined to do all kinds of things, and you should be able to handle combinations like the following:

Read elements from the keyboard and store them in a collection. Then perform an operation on each element.

Ex: Read in a bunch of student records and then increase each grade.

 

Sort the elements in a collection, by finding the minimum element in the collection, removing it, adding it to a new collection, repeating until the original collection is empty, and replacing the original collection by the new one.

Ex: sort the elements in a grade book by student number

Note: Next semester you'll learn better ways of sorting. The point here is that you can sort by combining basic operations that you know how to do.

 

Ask the user to type in an element, and show whether that element is or is not in a collection

Ex: prompt for a student record, and indicate whether of not it is already in a grade book

Ask the user to type in the value of part of an element, and print the values of the other parts on any elements that contain that part that is in a collection (if any)

Ex: ask for student number, print grades for that student

Ask the user to type in the value of part of an element, and print the minimum or maximum value of some part of any elements in the collection that contain the value typed in (or indicate if there are none)

Ex: ask for student number, print highest grade (if any)

plan: prompt for student no, add all matching student records to collection temp, find max grade in temp, print it

 

IV. Putting it all together.

For any of the above kinds of work, you have to be able to create a complete program that can be executed and tested.

Ex: read in a bunch of student records. Then ask for student number, print highest grade (if any).

 

Example Solutions

Note: You do not have to solve these problems exactly as shown. I've constructed all the solutions to emphasize the building block character of these ideas: you can learn standard ways of doing the basic operations, so that you can write functions that do these things; then you can combine these basic functions to do more complex things, and so on.

In some cases there are simpler ways of doing some of the combinations that involve modifying the building blocks. If these are clear to you, great; if not, stick with the building block ideas.

Note: Part of my personal building block style is heavy use of return codes that functions use to tell me whether they worked or not. Doing this often comes in handy by allowing me to control functions using while(), and it's also useful in detecting errors.

I. Representing collections.

You should be able to define a struct that contains an array of elements, which could themselves be structs, and a count, and perform the following operations on it. In these examples I use the following structs:

struct student_record

{

int student_no;

int grade;

};

struct grade_book

{

struct student_record records[MAX];

int count;

};

Make the collection empty (by setting its count to 0)

Ex:

void make_empty(struct grade_book *pg)

{

pg->count=0;

}

Get the value of an element, given its position (subscript) in the collection (if possible, and indicate if not possible.

Ex:

int get_value(int index, struct grade_book gb, struct student_record *psr)

{

if ((index<0) || (index>gb.count))

return 0;

*psr=gb.records[index];

return 1;

}

Add a new element on the end (if possible, and indicate if not possible)

int add(struct grade_book *pgb, struct student_record sr)

{

if (pgb->count >=MAX)

return 0;

pgb->records[pgb->count]=sr;

pgb->count++;

return 1;

}

Remove an element from anywhere in the collection, and repack the contents (if possible, and indicate if not possible)

int rem(int index, struct grade_book *pgb)

{

if (pgb->count<=0)

return 0;

if ((index<0)||(index>pgb->count-1))

return 0;

pgb->records[index]=pgb->records[pgb->count -1];

//that copies the last element into the space vacated by the element removed

pgb->count--;

return 1;

}

Perform an operation, by calling a function, on or with each element of the collection.

Ex: increase all the grades in the gradebook by calling a function that adds 1 to a grade

void bump(struct student_record *psr)

{

   psr->grade=psr->grade+1;

}

void bump_grades(struct grade_book *pgb)

{

   int i;

   for(i=0;i<pgb->count;i++)

      bump(&pgb->records[i]);

}

Find the sum or product or ... of the elements or parts of elements in the collection... use the Running Total Plan (or a variant)

Ex: Find the overall average grade in a grade book...find the sum and divide by the count

float average(struct grade_book gb)

{

   int runningtotal;

   int i;

   if (gb.count==0)

   {

      printf("average of empty collection not defined\n");

      exit(1);

   }

   runningtotal=0;

   for(i=0;i<gb.count;i++)

      runningtotal=runningtotal+gb.records[i].grade;

   return ((float) runningtotal)/gb.count;

//the (float) forces a conversion of runningtotal to float. If you do not convert either runningtotal or

//gb.count to a float here, you will get integer division, which throws away fractions

}

Find the position or the value of minimum or maximum element in the collection (if possible, and indicate if not possible)...use the Knockout Plan

Ex: (minimum student no, gives position)

int min(struct grade_book gb, int *pos)

{

   int i;

   int min_so_far;

   int pos_min_so_far;

   if (gb.count<=0)

      return 0;

   min_so_far=gb.records[0].student_no;

   pos_min_so_far=0;

   for(i=0;i<gb.count;i++)

      if (gb.records[i].student_no<min_so_far)

      {

         min_so_far=gb.records[i].student_no;

         pos_min_so_far=i;

      }

   *pos=pos_min_so_far;

   return 1;

}

Ex: (maximum grade, gives the student record)

int max(struct grade_book gb, struct student_record *psr)

{

   int i;

   struct student_record max_so_far;

   if (gb.count<=0)

      return 0;

   max_so_far=gb.records[0];

   for(i=0;i<gb.count;i++)

      if (gb.records[i].grade>max_so_far.grade)

         max_so_far=gb.records[i];

   *psr=max_so_far;

   return 1;

}

Find the position or the value of an element in the array that satisfies some property (if possible, and indicate if not)

Ex: Find value of a student record that has a given student number

int find(struct grade_book gb, int student_no, struct student_record *psr)

{

   int i;

   if (gb.count<=0)

      return 0;

   for(i=0;i<gb.count;i++)

      if (gb.records[i].student_no==student_no)

      {

         *psr=gb.records[i];

         return 1;

      }

   return 0;

}

 

II. Other operations

read an element from a file (if possible, and indicate if not possible)

Ex:

int read_student_record(FILE *fp, struct student_record *sr)

{

   int items_read;

   items_read=fscanf(fp,"%d%d",&sr->student_no,&sr->grade);

   if (items_read!=2)

      return 0;

   return 1;

}

read an element from the keyboard (and detect an entry indicating user wants to quit)

Ex: Read a student record

int read_student_record_from_kb(struct student_record *psr)

{

   int user_input;

   printf("Type student number or -1 to quit: ");

   scanf("%d", &user_input);

   if (user_input==-1)

      return 0;

   psr->student_no=user_input;

   printf("Type a grade: ");

   scanf("%d", &psr->grade);

   return 1;

}

Note: this function is not very robust... what if the user types in garbage, such as a letter? Can you do better?

 

print an element

Ex: Print a student record.

void print_sr(struct student_record sr)

{

   printf("Student no: %d Grade: %d\n", sr.student_no, sr.grade);

}

III. Combinations

The above operations can be combined to do all kinds of things, and you should be able to handle combinations like the following:

Read elements from the keyboard and store them in a collection.

Note: For this kind of job I use a plan I call PUF, for "Process Until Finished". The idea is that we want to carry out a process consisting of two steps, read an element and store an element, until one of the steps fails. The read step will fail if we come to the end of the file, and the store step will fail if the collection fills up. If we write a function for each process step in the PUF plan, and we make each of these functions return a 1 when it works and 0 when it fails, we can use this outline:

while (step1(...) )

{

ok=step2(...);

if (!ok)

break;

}

The test in the while just looks at the number step1() returns: it keeps going as long as that number is 1, that is, as long as step1() succeeds. The body of the loop checks the number step2() returns and terminates the loop as soon as it is 0, that is, as soon as step2() fails.

C offers a shorter way to write the PUF plan. This may be a little hard to understand at first, but once you get used to it it will be not only shorter but also clearer:

while (step1(...) && step2(...));

Yes, this is a while loop with no body! All the work we want to do is done in the test, which calls the functions step1() and step2(). The symbol && is an and operator: it combines two tests and gives true if the first test and the second test are both true. So here, if either step, step1() or step2(), fails, that step returns 0, which make the test false and ends the loop. The test is evaluated over and over again until one of the steps fails.

You might worry that if step1() fails, then step2() will still be called as part of evaluating the test, and that that might cause trouble. But in fact C stops evaluating the parts of a test as soon as the overall result is known. In this case, if step1() returns 0 it is obvious that the test will be false, and no further evaluation is done.

Notice that the PUF plan is easy to extend to processes with more than two steps. As long as you write functions to carry out each step, and each function returns 1 if it succeeds and 0 if it fails, you can write a statement like this:

while(step1(...) && step2(...) && step3(...)&&...&&step27(...));

This is a PUF for a process with 27 steps.

 

Ex: Read in a bunch of student records and then increase each grade.

void read_and_bump()

{

   struct grade_book gb;

   struct student_record sr;

   make_empty(&gb);

   while (read_student_record_from_kb(&sr)&&add(&gb,sr)); //PUF plan

   bump_grades(&gb);

}

Sort the elements in a collection, by finding the minimum element in the collection, removing it, adding it to a new collection, repeating until the original collection is empty, and replacing the original collection by the new one.

Ex: sort the elements in a grade book by student number

int remove_min(struct grade_book *pgb, struct student_record *psr)

{

   int return_code;

   int pos;

   return_code=min(*pgb,&pos);

   if (return_code==0)

      return 0; //collection is empty

   return_code=get_value(pos,*pgb,psr);

   if(return_code==0)

   {

      printf("bad subscript from min\n");

      exit(1);

   }

   return_code=rem(pos,pgb);

   if(return_code==0)

   {

      printf("something badly wrong in remove_min()\n");

      exit(1);

   }

   return 1;

}

 

void sort(struct grade_book *pgb)

{

   struct student_record sr;

   struct grade_book temp;

   make_empty(&temp);

   while(remove_min(pgb,&sr)&&add(&temp, sr));//PUF plan

   *pgb=temp;

}

Ask the user to type in an element, and show whether that element is or is not in a collection

Ex: prompt for a student record, and indicate whether of not it is already in a grade book

 

int matching_record(struct student_record r1, struct student_record r2)

{

   if ((r1.student_no==r2.student_no)&&(r1.grade==r2.grade))

      return 1;

   return 0;

}

int is_there_matching_record(struct grade_book gb, struct student_record sr)

{

   int i;

   for (i=0;i<gb.count;i++)

      if (matching_record(sr, gb.records[i]))

         return 1;

   return 0;

}

void is_in(struct grade_book gb)

{

   struct student_record sr;

   int return_code;

   return_code=read_student_record_from_kb(&sr);

   if (return_code==0)

      return;

   if (is_there_matching_record(gb, sr))

      printf("It's there.\n");

   else printf("It's not there.");

}

Ask the user to type in the value of part of an element, and print the values of the other parts on any elements that contain that part that is in a collection (if any)

Ex: ask for student number, print grades for that student

void print_grade_if_match(struct student_record sr, int student_no)

{

   if (sr.student_no==student_no)

      printf("Grade: %d\n",sr.grade);

}

 

void print_grades_for_sno(struct grade_book gb, int student_no)

{

   int i;

   for (i=0;i<gb.count;i++)

      print_grade_if_match(gb.records[i],student_no);

}

 

void prompt_for_sno_print_grades(struct grade_book gb)

{

   int sno;

   printf("Enter a student number: ");

   scanf("%d", &sno);

   print_grades_for_sno(gb,sno);

}

Ask the user to type in the value of part of an element, and print the minimum or maximum value of some part of any elements in the collection that contain the value typed in (or indicate if there are none)

Ex: ask for student number, print highest grade (if any)

plan: prompt for student no, add all matching student records to collection temp, find max grade in temp, print it

void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb)

{

   int return_code;

   if (sr.student_no==student_no)

   {

      return_code=add(pgb, sr);

      if (return_code==0)

      {

         printf("error in add\n");

         exit(1);

      }

   }

}

 

void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb)

{

   int i;

   for (i=0;i<gb.count;i++)

      add_grade_if_match(gb.records[i],student_no, pnewgb);

}

 

void prompt_for_sno_print_max_grade(struct grade_book gb)

{

   int sno;

   int return_code;

   struct student_record sr;

   struct grade_book temp;

   make_empty(&temp);

   printf("Enter a student number: ");

   scanf("%d", &sno);

   add_grades_for_sno(gb, sno, &temp);

   return_code=max(temp, &sr);

   if (return_code==0)

      printf("No grades for this student.\n");

   else printf("Max grade for this student is: %d\n", sr.grade);

}

Note: There's a good alternative plan for this one, that involves modifying the knockout plan slightly: when you run through the collection doing the knockout, DON'T allow any record with wrong student number to beat the champion:

int max_for_this_sno(int sno, struct grade_book gb, struct student_record *psr)

{

   int i;

   struct student_record max_so_far;

   if (gb.count<=0)

      return 0;

   max_so_far=gb.records[0];

   for(i=0;i<gb.count;i++)

      if ((gb.records[i].student_no==sno)&&(gb.records[i].grade>max_so_far.grade))

         max_so_far=gb.records[i];

   *psr=max_so_far;

   return 1;

}

Using this you can get rid of temp and the calls that empty it and add grades to it, and replace max() by max_for_this_sno().

IV. Putting it all together.

For any of the above kinds of work, you have to be able to create a complete program that can be executed and tested.

Ex:

Ex: read in a bunch of student records. Then ask for student number, print highest grade (if any).

Note: This example is longer than I can ask you to write in a 50 min Programming Check. But it is a good illustration of the building block idea: the only new function I had to write for this was main().

#include <stdio.h>

#include <stdlib.h>

#define MAX 20

struct student_record

{

   int student_no;

   int grade;

};

struct grade_book

{

   struct student_record records[MAX];

   int count;

};

void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb);

void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb);

void prompt_for_sno_print_max_grade(struct grade_book gb);

int read_student_record_from_kb(struct student_record *psr);

int add(struct grade_book *pgb, struct student_record sr);

int max(struct grade_book gb, struct student_record *psr);

void make_empty(struct grade_book *pg);

int main()

{

   struct grade_book gb;

   struct student_record sr;

   make_empty(&gb);

   while (read_student_record_from_kb(&sr)&&add(&gb,sr));//PUF

   prompt_for_sno_print_max_grade(gb);

   return 0;

}

void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb)

{

   int return_code;

   if (sr.student_no==student_no)

   {

      return_code=add(pgb, sr);

      if (return_code==0)

      {

         printf("error in add\n");

         exit(1);

      }

   }

}

void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb)

{

   int i;

   for (i=0;i<gb.count;i++)

      add_grade_if_match(gb.records[i],student_no, pnewgb);

}

 

void prompt_for_sno_print_max_grade(struct grade_book gb)

{

   int sno;

   int return_code;

   struct student_record sr;

   struct grade_book temp;

   make_empty(&temp);

   printf("Enter a student number: ");

   scanf("%d", &sno);

   add_grades_for_sno(gb, sno, &temp);

   return_code=max(temp, &sr);

   if (return_code==0)

      printf("No grades for this student.\n");

   else printf("Max grade for this student is: %d\n", sr.grade);

}

int read_student_record_from_kb(struct student_record *psr)

{

   int user_input;

   printf("Type student number or -1 to quit: ");

   scanf("%d", &user_input);

   if (user_input==-1)

      return 0;

   psr->student_no=user_input;

   printf("Type a grade: ");

   scanf("%d", &psr->grade);

   return 1;

}

int add(struct grade_book *pgb, struct student_record sr)

{

   if (pgb->count >=MAX)

      return 0;

   pgb->records[pgb->count]=sr;

   pgb->count++;

   return 1;

}

int max(struct grade_book gb, struct student_record *psr)

{

   int i;

   struct student_record max_so_far;

   if (gb.count<=0)

      return 0;

   max_so_far=gb.records[0];

   for(i=0;i<gb.count;i++)

      if (gb.records[i].grade>max_so_far.grade)

   max_so_far=gb.records[i];

   *psr=max_so_far;

   return 1;

}

void make_empty(struct grade_book *pg)

{

   pg->count=0;

}

Practice Problems and Further Suggestions

I cannot urge you too strongly to solve at least SOME of the following practice problems before the Programming Check.

If you get help in working any of the examples, fine, but then create a similar example and try to solve that without help. Continue until you can solve them without help. You may create notes to assist you.

Practice Problems

Use the following function as needed in the practice problems below. Be sure to put #include <stdlib.h> in your program when you use this function:

int random() //returns a random int between 0 and 99.

{

   return (100.*rand())/RAND_MAX;

}

An important tip: Don’t try to write the whole program before compiling and testing. This is a bad idea, except for material you have down cold. Instead, you should write the program in stages, compiling and testing as you go. For example, first do the prompt and read a number, and print the number. Compile and test that before going on. Then create a collection (if that's what comes next) and print the collection. Get that working before continuing, and so on.

Prompt the user for a positive number and create a collection containing that many random ints. Print the minimum and maximum.

Prompt the user for a positive number and create a collection containing that many random ints. Sort it in increasing order. Print the numbers.

Prompt the user for a positive number and create a collection containing that many random ints. Remove all those greater than 50. Print the remaining numbers.

Prompt the user for a positive number and create a collection containing that many random ints. Create a new collection containing the numbers less than 25. Print the new collection.

Prompt the user for a positive number and create a collection containing that many random ints. Using a function, multiply each number in the collection by 3. Print.

Prompt the user for a positive number and create a collection of that many random dots. Each dot has an x and y coordinate, each a random int. Print the coordinates of all dots whose x coordinate is greater than 50.

Prompt the user for a positive number and create a collection of that many random dots. Remove all dots whose x coordinate is greater than 50 and print the coordinates of the remaining dots.

Prompt the user for a positive number and create a collection of that many random dots. Print the subscript of the first dot in the collection whose x coordinate is greater than 50, or print a message saying that there are no such dots in the collection.