CMPUT 201 Assignment #1

C/C++ Potpourri

Due before 23:59, Sunday, February 11, 2001

Objective

The assignment consists of a series of small programming tasks intended to make you familiar with C/C++ syntax and with the UNIX way of doing things. Each task is fairly independent and you can start them whenever you are ready. The first few exercises are simple enough that you can do them right away. They require a knowledge of the C material in the first first thirteen chapters of King's book (or the first eight Chapters of Kernighan and Ritchie--that is the whole book), or the first five chapters of Deitel & Deitel. After completing this assignment you should be able to do simple programming tasks and be comfortable with the larger ones in the coming weeks. You can do this assignment in C alone or in C/C++ (using the g++ compiler). If you are new to C/C++, you might want to focus on C and use King's book (or the standard C reference by Kernighan and Ritchie).

Read this assignment through carefully to make sure that you understand what is to be done, what should be handed in, and the format of the submission. Generally, your programs should comply with the guidelines in Notes on Specification and Coding Style. That material, however, assumes that you already know C.

Notes

Collaboration is not allowed for this assignment, that is, each of you must do the task on your own. Obviously you can, and even should, DISCUSS the assignment and its possible solutions with others in your lab section, but you must write your own solutions. We assume that you are aware of the Regulations undergraduates should know, as stated in Undergraduate Laboratories WWW Server.

The assignment consists of a sequence of fairly independent exercises and you can work on them whenever you are ready. You should start them right away, this will guide your study of the C/C++ programming language. Start early!

In Lab 1 you will be shown how to use CVS and to construct a makefile that will be used to create executable modules of all your programs when "make all" is typed. Ensure that the executables produced by your makefile are named exactly as shown in the sample from the lab. If they are not named correctly, they will not be marked!

There are many details that must be handled for you to receive full marks on this assignment. You should pay attention to these details. The makefile must correctly produce all the programs required, and each function/procedure and program file must be correctly named and must behave in the appropriate way. If the details aren't addressed successfully you will lose marks.

You will not have to take action to submit your assignment. Your work will be automatically extracted from your CVS repository on the due date and time. We will also be extracting from your repository at times prior to the due date in order to monitor your progress toward the final submission. Questions about these exercises will be answered in the course newsgroup. You are expected to check that newsgroup regularly, so that you are fully informed.

Exercises

Complete the following exercises, which are typical of the practice problems found in many C/C++ programming texts. The exercises are stated in general terms: this has been done on purpose to make you think about possible solutions. If necessary, clarifications will be given in the course newsgroup, in the labs or in class. The exercises are not specifically ordered by difficulty. By using your makefile effectively you can tackle the problems conveniently and in any order you wish. NOTE: For the first several exercises, use getchar() and scanf() to read from standard input, and putchar() or printf() to output your answers. For the later exercises the more general functions like fgetc(), fgets() and the like may be better. See also the IMPORTANT NOTE near the end of the assignment statement about multiple-line input.

Write a program called eof that prints the value of the pre-defined constant EOF.
Write a program called table that prints the values of a few simple mathematical functions in tabular form. These functions use real-valued numbers, but the table entries are for only the even integers 0 through 100. The first column of the table is x, the independent variable. The other columns are for x^2, x^4 and the cube root of x.
Write a program called longline that echoes all input lines that are longer than 60 characters. The input is to be taken from standard input (i.e. characters typed at the keyboard) and written on standard output (i.e., displays it on the screen). Print the line only if it is strictly longer than 60 characters. As with all the exercises, your program must terminate normally when it receives an end-of-file signal on input (Control-D in Unix).

Write a program called deblank that replaces sequences of one or more consecutive blanks with a single blank. This program reads its input from standard input, and writes its output to standard output. In the process of copying its input to its output, it replaces the sequences of multiple blanks by a single blank. After the replacing of blanks is complete, the program also prints, on a new line, the length of the longest sequence of consecutive blanks encountered in the input stream.

Write a program called squeeze that reads from standard input, compresses the input data and transfers the resultant text to standard output. The compression technique used is very simple. The program looks for sequences where the same character is repeated 2 to 9 times. These sequences are replaced by the character itself followed by a single digit, giving the number of times the character is repeated. If a sequence longer than 9 identical characters is encountered, it is replaced by several sequences with at most 9 characters. (Is this compression method reversible? You do not have to answer this question, but you should know the answer.)
Examples:

Write a program called strip to remove all /* */ comments from a C or C++ program. Don't forget to handle quoted strings and character constants correctly. You definitely want to think of this as a finite state machine process, as per the MyGrep example.
Note: In C/C++ one comment cannot be nested within another.

Write a procedure, called reverse(s), that reverses the character string s. Use this procedure in a program called revline that reverses its input one line at a time. The input should be read from standard input, and the output written to standard output. NOTE: Your program must be able to reverse AT LEAST 99 characters in a line. However, for full marks you must be able to handle any arbitrarily long line (see Labs #2 and #3).

Write a program called convert that reads pairs of integers (separated by whitespace) from standard input, where the first integer is a base and the second integer is the decimal representation of a number to be converted to that base. The converted integer is written on standard output.

Do this by writing a function itob(n,s,b) that converts an integer n into a string s that holds its base b character representation. For example, itob(n,s,8) converts the integer n into its octal representation, and itob(n,s,10) converts the integer into decimal representation. The program that calls itob is responsible for allocating enough space for s. (Hint: Consider the largest number you want to represent in base 2.)

For this exercise, your program should be able to deal with conversions up to base 36. Numbers are represented using characters made up of the digits 0 to 9 and the letters A to Z. It does not matter if you use upper-case or lower-case letters or a combination of both, but explain your decision and its consequences. Differentiating between digits, upper-case letters and lower-case letters could allow you to represent numbers up to base 62. When representing a number in a base larger than 10, it is customary to use digit characters for the lowest numbers, and then to use letters. For example, the octal (base 8) system uses the characters 0 1 2 3 4 5 6 7, and the hexadecimal (base 16) system uses the characters 0 1 2 3 4 5 6 7 8 9 A B C D E F.
Examples:

Write a program called tally that counts how many positive and negative decimal numbers occur on standard input. A number is any sequence of characters built according to the conversion character e of the formatted I/O commands of C (See King p. 494 or K&R p. 246). Is zero positive or negative?

Sample input

Energy content of fuels KJoule/g KJoule/cc

 Hydrogen 124.7 8.7
 Coal C28H42 32.2 41.8
 Wood C.32H.40O.22 17.5 14.2
 Methane gas 61.1 .0044

 Gasoline1 30.9e6 (J/liter))) ; => 3.090e+10

 And -.23 here are some - 3.090e+10 negative -3.090e-10
 numbers.

Output for sample input

There are 19 numbers in the input file.
17 numbers are positive, 2 are negative.

Write a program called 4thpoint that solves the following problem:

Given are the (x,y) coordinates of the endpoints of two adjacent sides of a parallelogram. Find the (x,y) coordinates of the fourth point.

Each line of input contains eight floating point numbers: the (x,y) coordinates of one of the endpoints of the first side followed by the (x,y) coordinates of the other endpoint of the first side, followed by the (x,y) coordinates of one of the endpoints of the second side followed by the (x,y) coordinates of the other endpoint of the second side. All coordinates are in meters, to the nearest mm. All coordinates are between -10000 and +10000.

For each line of input, print the (x,y) coordinates of the fourth point of the parallelogram in meters, to the nearest mm, separated by a single space.

Sample input
```
0.000 0.000 0.000 1.000 0.000 1.000 1.000 1.000
1.000 0.000 3.500 3.500 3.500 3.500 0.000 1.000
1.866 0.000 3.127 3.543 3.127 3.543 1.412 3.145
```
Output for the sample input
```
1.000 0.000
-2.500 -2.500
0.151 -0.398
```

Two additional problems are provided for your interest. These questions require thought as well as skill. They are within your reach, but may take time. The TAs will provide advice and feedback only as time permits.

Write a program called sheep that solves the following problem:
There is a circle of grass with the radius R. We want to let a sheep eat the grass from that circle by attaching the sheep's leash on the edge of the circle. What must be the length L of the leash for the sheep to eat exactly X% of the grass?

Input consists of a sequence of lines each containing two non-negative integers separated by whitespace. The first integer is the value of R and the second is the value of X, 0 <= X <= 100.
For each input line, output a single real number with 5 digits of the fraction, giving the required length of the leash.
Sample input
10 50
50 10
10 0
20 100
37 37
1000 50
Output for sample input
11.58728
23.57857
0.00000
40.00000
35.82576
1158.72847
Write a program called commperm which solves the following problem:
Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.
Input consists of pairs of lines. The first line of a pair contains a and the second contains b. Each string is on a separate line and consists of at most 1,000 lowercase letters.
For each subsequent pair of input lines, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.
Sample input
pretty
women
walking
down
the
street
Output for the sample input
e
nw
et

IMPORTANT NOTE:

If the specifications require a program to read from standard input, DO NOT assume that the input will consist of a single line. Your programs MUST be able to handle multiple input lines in order to receive full marks!!!
Further, since your program will be tested by using the Unix i/o redirection, there is no need for you to prompt the user for input text. There is also no need for you to know the name of the input file (so clearly you won't be prompting for that either). Your programs will be tested with a command of the following type:

yourprogram <inputfile >outputfile

This form of Unix i/o redirection will be discussed in your labs. It is the established method in Unix for assigning standard input and standard output to files. You will certainly want to use this command to bring data from a file into your program.

Marking

The marks breakdown is as follows:

    30 marks (3 marks each) for exercises 1-10
   + 3 marks for a correct makefile
    ------------------------------------------
  = 33 marks total

Marks will be deducted not only for wrong answers, but also for inconsistent or poor formatting (we should be able to read your code!). Further, failure to appropriately document functions, or variables needing documentation will be penalized. Marks will be deducted for each extra file incorrectly committed to the CVS repository. You should be sure that only your C source, your header files and your Makefile are committed to CVS, and NOT ANYTHING ELSE, like object files ( files ending in .o), executable programs, or core dumps (i.e. a file named core).

Your code must compile without error and handle 'normal' input; otherwise it is worth 0. Your code should compile without warning messages when using the flags "-Wall -ansi", otherwise marks will be deducted.

Late assignments will not be accepted, unless there is a special personal emergency recognized by your instructor.

Deliverables

You must create a CVS repository for your assignment. Lab 1 shows you how to do this. Your repository must contain a directory called ass1. In this directory, you must commit all necessary .c and .h files, along with your Makefile. Do not commit other files (core files, backup files, etc.) or you will lose marks.
Your Makefile must have entries in it for each part of this assignment. Each part must be named as described above. Your Makefile must be designed so that a make all compiles all parts of this assignment.
Your code should compile without any warning messages when using the flags -Wall -ansi, otherwise marks will be deducted. Your Makefile should include these flags.

Please make sure that every file (including your Makefile) you submit contains a banner with the following information:

/*-------------------------------------------------------------------------
 # Student's Name:
 # Student's ID:
 # Assignment #1
 # Lab Section: one of {H01, H02, H03, H04, X11, X12}
 # TA's Name: (for the lab group above)
 # CMPUT 201, Class Section: one of {B1, X10}
 # Instructor's Name: (for section above)
 *-----------------------------------------------------------------------*/