Computer Science 400 Parallel Processing Siena College Fall 2008

This lab is the first half of a two-part programming assignment. This week, you will be implementing a sequential version of the program, and you will parallelize it with pthreads next week.

There is an online dictionary /usr/dict/words on bullpen that is used by the spell command. You know that a palindrome is a word or phrase that reads the same in either direction, i.e., if you reverse all the letters you get the same word or phrase. A word is palindromic if its reverse is also in the dictionary. For example, "noon" is palindromic, because it is a palindrome and hence its reverse is trivially in the dictionary. A word like "draw" is palindromic because "ward" is also in the dictionary.

Your task is write a C or C++ program to find all palindromic words in the dictionary.

Your sequential program should have the following phases:

• Read the file /usr/dict/words into an array of strings. You can determine the size of this array ahead of time by running wc on the dictionary to see how many words it contains. You may assume that each word is at most 25 characters long.
• For each word, compute its reverse and do a linear search of the dictionary to see if the reverse of the word is in the dictionary. If so, mark the word and increment your counter of the total number of palindromic words.
• Print the total number of palindromic words to the screen (stdout).

The first few words in the dictionary start with numbers; you can either skip over them or process them, as you wish. None are palindromic, so this choice will not affect your total count. Some words start with capital letters (and hence the dictionary is not sorted in ASCII order). To keep your program simple, leave the capitals alone and do case-sensitive comparisons.

The sequential program should be fairly straightforward, but it will likely take longer than you expect to implement. Please ask if you run into trouble with the sequential version! You will need to get it done this week so you can have a starting point for next week's parallelization - which is the whole point of writing this program. Keep in mind that you will be parallelizing your program next week using a bag-of-tasks paradigm. For example, you might want to keep track of the positions in your array that store the first word beginning with each letter of the alphabet. This should also suggest an optimization you can use in your sequential program.

You may use the timer.c and timer.h code from our class examples. Start the clock (take a timer reading) after loading the dictionary and just before you start finding palindromic words; read the timer again as soon as you have finished. Write the elapsed time for the compute phase to stdout.

To summarize, your program should have the following output:

• total number of palindromic words (to stdout)
• the elapsed time for the compute phase (to stdout)

Using the turnin utility, submit your final product as lab2. Include your Makefile, your C source code (including the timer code from class, if you choose to use it), and a brief README file expaining how to run your program. Please do not include object files or your executable.

• My version of the program runs for about 4 seconds using one thread on a Solaris cluster node. You can run it as:

  ~terescoj/shared/cs400/labs/palindromic-serial/palindromic
  

  The executable will work on bullpen.
• I recommend the -xO3 (capital letter 'O', number '3') compiler optimization flag for timing runs. Use -g instead if you're debugging. We have two command-line debuggers installed: dbx and gdb, and one graphical debugger: ddd.
• There is no "string" type in C. You just use an array of char. See string(3C) for details on some useful string manipulation functions.
• Dynamic memory management is done by the malloc(3C) and free(3C) functions. There is no garbage collection, so you need to make sure you return any memory you allocate.
• You can use char variables and constants as ints, if you'd like.

individually, I want to encourage you to ask questions and discuss the program with me, and with each other, as you develop it. However, no direct sharing of code is permitted. If you have any doubts, please check first and avoid problems later.

determined by correctness, design, documentation, and style.