CS211 -  Programming Assignment I - Solved

This assignment is designed to give you some initial experience with programming in C, as well as compiling, running, and debugging. Your task is to write seven small C programs.

Section 1 describes the seven programs, section 2 describes how your project will be graded, and section 3 describes how to structure and submit your project. In particular, section 3.1 gives a simple method for organizing your source code and compiling and testing your code. Please read the entire assignment description before beginning the assignment.


1           Program descriptions
You will write six programs for this project. Except where explicitly noted, your programs may assume that their inputs are properly formatted. However, your programs should be robust. Your program should not assume that it has received the proper number of arguments, for example, but should check and report an error where appropriate.

Programs should always terminate with exit code EXIT_SUCCESS (that is, return 0 from main).

1.1           roman: Decoding Roman numerals
Write a program roman which converts numbers from deciman notation into Roman numerals. roman takes a single argument, a string containing a non-negative integer, and prints its Roman numeral equivalent to standard output.

Usage

$ roman 3

III

$ roman 54

XIV

$ roman 1977

Table 1: Numeric values for Roman numerals

Symbol
Value
Symbol
Value
M
1000
D
500
C
100
L
50
X
10
V
5
I
1
 
 
MCMLXXVII $ roman 0

$ roman 4321 MMMMCCCXXI

Roman numerals Roman numerals are written using the symbols I, V, X, L, C, D, and M. The values for these symbols are given in table 1. Often, the value for the Roman numeral can be found by converting each character to its corresponding integer value and adding up the results. For example MMXX becomes 1000+1000+10+10=2020.

The exception occurs when C, X, or I appear before a symbol in the next higher row of table 1. In that case, the value of the first symbol is subtracted from the value of the next symbol. Thus, IV is 4, IX is 9, XL is 40, XC is 90, CD is 400, and CM is 900.

Note that we do not use any symbols larger than M, so very large numbers may be written with arbitrarily many M’s (e.g., 10,000 is MMMMMMMMMM). In contrast, the output of roman will include C and X at most four times (not more than three consecutively), I at most three times, and D, L, and V each at most once. Thus, your program will write IV and not IIII.

Roman numerals do not have a notation for zero, so your program should print nothing if the input is 0.

Notes     For roman, it is sufficient to use atoi() to convert argv[1] to an int. You will not need to handle any error cases.

The code to handle hundreds, tens, and ones is very similar. Try writing a loop, rather than repeating your algorithm three times.

1.2           palindrome: String operations I
Write a program palindrome that tests whether a string is a palindrome, meaning that the sequence of letters is symmetric and is not changed by reversal. palindrome takes a single argument, which is a string containing any combination of upper- and lower-case letters, digits, and punctuation marks. palindrome prints “yes” if its string is a palindrome, and “no” otherwise.

Usage

$ ./palindrome Bob yes

$ ./palindrome Robert no

$ ./palindrome hohoho no

$ ./palindrome "Madam, I’m Adam." yes

$ ./palindrome "A man, a plan, a canal: Panama." yes

$ ./palindrome "Two men, two plans, two canals: Panamas." no

Notes     Note that palindromes are case-insensitive, meaning that “Bob” is a palindrome because “B” and “b” are considered equivalent.

Note that the definition of palindrome only considers letters, and ignores all other non-letter characters. Therefore, “Rise to vote, sir!” is a palindrome, because it is equivalent to “risetovotesir”, which is clearly symmetric. (The definition of palindrome we are using is unclear regarding digits, so test inputs will not include digit characters.)

You are free to implement palindrome in any manner you find convenient. If you are looking for a challenge, implement palindrome such that it allocates no memory, does not modify its argument, and does not examine any character in the argument more than once.

1.3           rle: String operations II
Write a program rle that uses a simple method to compress strings. rle takes a single argument and looks for repeated characters. Each repeated sequence of a letter or punctuation mark is reduced to a single character plus an integer indicating the number of times it occurs. Thus, “aaa” becomes “a3” and “ab” becomes “a1b1”.

If the compressed string is longer than the original string, rle must print the original string instead.

If the input string contains digits, rle MUST print “error” and nothing else.

Usage

$ ./rle aaaaaa a6

$ ./rle aaabcccc..a a3b1c4.2a1

$ ./rle aaabab aaabab

$ ./rle a1b2 error

Notes     Note that rle prints the original string if its compression method results in a larger string than the input. Thus, in the third example above, it prints “aaabab” (length 6) and not “a3b1a1b1” (length 8).

You MUST NOT assume that input strings have a maximum length. You will need to allocate space to store the compressed string dynamically, based on the length of the input string. Given an input string containing n characters, what is the maximum number of characters it a printed output string? Is it necessary for rle to compress the entire input string before determining that it should output the uncompressed string instead?

You MUST NOT assume any maximum number of times a character will be repeated. rle should work equally well given a sequence of 10 or 1000 A’s. Rather than write your own integer to string function, you can use sprintf or snprintf with an appropriate format string. Remember that these functions work perfectly well when given a pointer to the middle of an allocated char array, and will begin printing after that pointer. Both functions return the number of bytes witten, which you can use to advance your pointer. (Read the manual and do some experiments to make sure you account for terminator characters properly.)

1.4           list: Linked lists
Write a program list that maintains and manipulates a sorted linked list according to instructions received from standard input. The linked list is maintained in order, meaning that the items in the list are stored in increasing numeric order after every operation.

Note that list will need to allocate space for new nodes as they are created, using malloc; any allocated space should be deallocated using free as soon as it is no longer needed.

Note also that the list will not contain duplicate values. list supports two operations:

insert n Adds an integer n to the list. If n is already present in the list, it does nothing. The instruction format is an i followed by a space and an integer n.

delete n Removes an integer n from the list. If n is not present in the list, it does nothing. The instruction format is a d followed by a space and an integer n.

After each command, list will print the length of the list followed by the contents of the list, in order from first (least) to last (greatest). list must halt once it reaches the end of standard input.

Input format                     Each line of the input contains an instruction. Each line begins with a letter (either

“i” or “d”), followed by a space, and then an integer. A line beginning with “i” indicates that the integer should be inserted into the list. A line beginning with “d” indicates that the integer should be deleted from the list.

Your program will not be tested with invalid input. You may choose to have list terminate in response to invalid input.

Output format After performing each instruction, list will print a single line of text containing the length of the list, a colon, and the elements of the list in order, all separated by spaces.

Usage     Because list reads from standard input, you may test it by entering inputs line by line from the terminal.

$ ./list i 5 1 : 5

d 3

1 : 5

i 3

2 : 3 5

i 500

3 : 3 5 500

d 5

2 : 3 500

^D

To terminate your session, type Control-D at the beginning of the line. (This is indicated here by the sequence ^D.) This closes the input stream to list, as though it had reached the end of a file.

Alternatively, you may use input redirection to send the contents of a file to list. For example, assume list_commands.txt contains this text:

i 10 i 11

i 9

d 11

Then we may send this file to list as its input like so:

$ ./list < list_commands.txt

1    : 10

2    : 10 11

3    : 9 10 11

2 : 9 10

1.5           mexp: Matrix manipulation
Write a program mexp that multiplies a square matrix by itself a specified number of times. mexp takes a single argument, which is the path to a file containing a square (k × k) matrix M and a non-negative exponent n. It computes Mn and prints the result.

Note that the size of the matrix is not known statically. You must use malloc to allocate space for the matrix once you obtain its size from the input file.

To compute Mn, it is sufficient to multiply M by itself n−1 times. That is, M3 = M ×M ×M. Naturally, a different strategy is needed for M0.

Input format         The first line of the input file contains an integer k. This indicates the size of the matrix M, which has k rows and k columns.

The next k lines in the input file contain k integers. These indicate the content of M. Each line corresponds to a row, beginning with the first (top) row.

The final line contains an integer n. This indicates the number of times M will be multiplied by itself. n is guaranteed to be non-negative, but it may be 0. For example, an input file file.txt containing

3

1 2 3

4 5 6

7 8 9

2 indicates that mexp must compute

  .

Output format     The output of mexp is the computed matrix Mn. Each row of Mn is printed on a separate line, beginning with the first (top) row. The items within a row are separated by spaces. Using file.txt from above,

$ ./mexp file1.txt

30 36 42

66 81 96

102 126 150

1.6           bst: Binary search trees
Write a program bst that manipulates binary search trees. It will receive commands from standard input, and print resposes to those commands to standard output.

A binary search tree is a binary tree that stores integer values in its interior nodes. The value for a particular node is greater than every value stored its left sub-tree and less than every value stored in its right sub-tree. The tree will not contain any value more than once. bst will need to allocate space for new nodes as they are created using malloc; any allocated space should be deallocated using free before bst terminates.

This portion of the assignment has two parts.

Part 1               In this part, you will implement bst with three commands:

insert n Adds a value to the tree, if not already present. The new node will always be added as the child of an existing node, or as the root. No existing node will change or move as as result of inserting an item. If n was not present, and hence has been inserted, bst will print inserted. Otherwise, it will print not inserted. The instruction format is an i followed by a decimal integer n.

search n Searches the tree for a value n. If n is present, bst will print present. Otherwise, it will print absent. The instruction format is an s followed by a space and an integer n. print Prints the current tree structure, using the format in section 1.6.1.

Part 2                In this part, you will implement bst with an additional fourth command:

delete n Removes a value from the tree. See section 1.6.2 for further discussion of deleting nodes. If n is not present, print absent. Otherwise, print deleted. The instruction format is a d followed by a space and an integer n.

Input format The input will be a series of lines, each beginning with a command character (i, s, p, or d), possibly followed by a decimal integer. When the input ends, the program should terminate.

Your program will not be tested with invalid input. A line that cannot be interpreted may be treated as the end of the input.

Output format The output will be a series of lines, each in response to an input command. Most commands will respond with a word, aside from p. The format for printing is described in section 1.6.1.

Usage

$ ./bst

i 1

inserted i 2

inserted

i 1

duplicate

s 3

absent p (1(2))

^D

As with list, the ^D here indicates typing Control-D at the start of a line in order to signal the end of file.

1.6.1           Printing nodes

An empty tree (that is, NULL) is printed as an empty string. A node is printed as a (, followed by the left sub-tree, the item for that node, the right subtree, and ), without spaces. For example, the output corresponding to fig. 1 is ((1)2((3(4))5(6))).

1.6.2           Deleting nodes

There are several strategies for deleting nodes in a binary tree. If a node has no children, it can simply be removed. That is, the pointer to it can be changed to a NULL pointer. Figure 2a shows the result of deleting 4 from the tree in fig. 1.

If a node has one child, it can be replaced by that child. Figure 2b shows the result of deleting 3 from the tree in fig. 1. Note that node 4 is now the child of node 5.

If a node has two children, its value will be changed to the maximum element in its left subtree. The node which previously contained that value will then be deleted. Figure 2c shows the result of deleting 5 from the tree in fig. 1. Note that the node that previously held 5 has been relabeled 4, and that the previous node 4 has been deleted.

Note that the value being deleted may be on the root node.

 

Figure 1: A binary search tree containing six nodes

 

Figure 2: The result of deleting different values from the tree in fig. 1


3.1           Getting started
The simplest way to set up your environment is to download the auto-grader and use tar to extract it. (The $ in these example indicates a prompt. The command you should type comes after the prompt and does not include the $.)