CMPUT 201 Assignment #1

C/C++ Potpourri

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


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.



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.

    1. Write a program called eof that prints the value of the pre-defined constant EOF.

    2. 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.

    3. 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).

    4. 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.

    5. 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.)


        The input abcddddddeeefghij will produce the output abcd6e3fghij

        The input aaaaaaaaaaaaaaaaaaa will produce the output a9a9a

    6. 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.

    7. 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).

    8. 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.

        itob(43, s, 2) will give s a value of 101011

        itob(43, s, 8) will give s a value of 53

        itob(43, s, 16) will give s a value of 2B

        itob(43, s, 24) will give s a value of 1J

    9. 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?

    10. 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
      Output for sample input
      There are 19 numbers in the input file.
      17 numbers are positive, 2 are negative.

    11. 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

  • 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

    Output for the sample input


    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.


    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.


    Copyright © Department of Computing Science.
    All rights reserved.