CSC 270H1Y -- Summer 2001

Homework 0
Due Thursday June 7 at 6 p.m.

Your code will be graded on both its correctness and its elegence. So please take the time to try to come up with short and easy to understand solutions. Please read the programming guides on the Assignments page.

Please consult the directory ~hsc/classes/270/examples on CDF. Some of the examples may prove useful in solving these problems.

1. Dot Product (10%)

Write a program "dotproduct.c" which computes the dot product of 2 vectors. The dot product is the summation of the element-wise product of each vector.

Example: (1, 4, 2) * (3, 5, -1) = 1*3 + 4*5 + 2*(-1) = 3 + 20 - 2 = 21

Here, each vector is stored as an array of integers.

I have started the program for you: dotproduct.c

Please place your code into a file called dotproduct.c.

2. String Intersection (10%)

Write a program called "intersect.c" which computes an intersection of two words/strings. The program will read in each word from the command line, and it will compute the intersection of the two words. A character is in the intersection if it exists in the same position in both strings.

Example: word1 = "ABCABCD", word2 = "BBADBGD"

The matching characters are the 2nd, 5th and 7th so the result will be "BBD".

Use pointers and not array indices to write intersection();

I have started the program for you: intersect.c

Sample execution:
eddie% intersect ABCABCD BBADBGD Intersection string is BBD eddie% intersect HowIHateUnix HowILoveWindows Intersection string is HowIe

3. Fliping Words (40%)

Write a program that inputs text from standard input, reverses the order of word in a line, and outputs the line. The program should continue until EOF (end-of-file) is read. If a line has more than 80 characters, you can ignore all characters past the 80th.

Note: The words can be separated by spaces or by tabs ('\t').

Hint:If you place your input into a file and pipe the file to your executable (remember the first lecture), then the EOF character will be sent at the end of the file. If you type the input in yourself, you can send and EOF character by typing control-D.

Call the program flipwords.c

Sample execution:
eddie% flipwords

Mary had a little lamb
lamb little a had Mary
Whose fleece was white as snow.
snow. as white was fleece Whose

Hint: Try to break the problem up into pieces and solve each piece separately. It may be easier than trying to solve the whole problem. Each piece will then become a separate function in your program.

4. Counting Characters (40%)

Write a program which performs the following steps.

Reads in text from standard input until the EOF is reached.
Counts the occurance of each character in the file.
Outputs each character which occurs at least once, the number of occurances, and the frequency of the character as a percentage of its number of occurances divided by the total number of characters. The output for each character should be on a separate line.
The output format is:
character: number times, percentage percent
The number of occurances value should be printed with at least 5 spaces of cushion, flush right, and the percentage value should be printed with 2 decimal places and the decimal points should align vertically.
The output should be sorted from the most frequent character to the least. Ties may be broken arbitrarily.

As for problem 3, if any of the lines in the file exceed 80 characters, you can ignore all characters past the 80th.

Call the program countchars.c

Sample execution:
eddie% countchars

"Look out!", shouted Steve as the rock just missed my head.
"Wow, that was close," I said.
 :    15 times, 16.48 percent
s:     8 times,  8.79 percent
o:     7 times,  7.69 percent
e:     7 times,  7.69 percent
t:     7 times,  7.69 percent
a:     5 times,  5.49 percent
d:     4 times,  4.40 percent
":     4 times,  4.40 percent
h:     4 times,  4.40 percent
,:     3 times,  3.30 percent
u:     3 times,  3.30 percent
k:     2 times,  2.20 percent
m:     2 times,  2.20 percent
.:     2 times,  2.20 percent

:     2 times,  2.20 percent
c:     2 times,  2.20 percent
i:     2 times,  2.20 percent
w:     2 times,  2.20 percent
l:     1 times,  1.10 percent
L:     1 times,  1.10 percent
S:     1 times,  1.10 percent
r:     1 times,  1.10 percent
W:     1 times,  1.10 percent
!:     1 times,  1.10 percent
j:     1 times,  1.10 percent
v:     1 times,  1.10 percent
I:     1 times,  1.10 percent
y:     1 times,  1.10 percent

Note that special characters like "return" and "tab" will mess up the output. That is ok, you do not have to handle these characters specially.

Hint: See the hint for Problem 3. This problem can also be solved by breaking it up into pieces. Also, think about what data structures you will need to solve this problem.

You can use any sorting method you wish, but here is a simple sorting algorithm which works well when sorting a small number of items.

for i = 1 to end
   for j = i+1 to end
      if ith element is less than the jth element
         swap the ith and jth elements