Math 171 Spring 2005, Lab 19

Due Tuesday, May 3, 11:59 P.M.

Pick one of the projects from the following list.

• Rewrite the anagram finder, making the following efficiency improvements:
  1. Use dynamic memory allocation to allocate arrays exactly large enough to hold the entire dictionary. You will need to read in the dictionary twice (once to determine the number of lines, and once to store it in memory) rather than hardcoding the size of the dictionary in your program.
  2. Rewrite the code that sorts the words in the dictionary and the block data using merge sort.
• Extend lab 17 to create a sequence of files corresponding to the connected components in the graph rather than just determining whether the graph is connected. The files should be named filename.1, filename.2, etc., where filename is the name of the orignal graph file to be split.
• Write a reverse polish notation (rpn) calculator. If you are not familiar with rpn, it works as follows:
  • Every time the calculator sees a number, it gets pushed onto the top of the stack.
  • Every time the calculator sees an arithmetic operator, the top two elements get popped off the stack, the operator is applied to them, and the result is pushed back onto the stack.
  Your calculator should support the following commands:

  operator	description
  +	adds two elements
  -	subtracts two elements
  *	multiplies two elements
  /	divides two elements
  p	prints the value on top of the stack without popping it
  n	pops the top value off the stack and prints it to standard output
  f	prints the entire stack
  r	swaps the order of the top two stack elements
  c	clears the stack
  q	quits the program

  Note that these commands are a subset of the functionality provided by the standard Unix program dc (desk calculator). You will be able to use this program to get a better idea of how your own code should function.
• Write a program that reads in a polynomial expressed in the notation a_n x^n + ... + a_k x^k + ... + a_1 x + a_0, followed by an integer m. The program should then output the m^th derivative of the polynomial. Here are some examples of acceptably formatted polynomials:
  • x^3 + 2 x^2 - 12x + 3
  • -x^2 + 10 x - 5
  • 12 x^10 - 3 x ^ 5 + 30
• Any other program you want to write for your final project may also be acceptable, provided that it makes use of at least five of the following Fortran language features:
  • Dynamic memory allocation
  • Functions or subroutines
  • Loops
  • Branching
  • Arrays
  • User-defined data types
  Additionally, your program should use at least one of the following:
  • Recursion
  • Formatted input and formatted output, including error checking the input
  • Functions or subroutines passed as arguments to another function or subroutine
  • Multidimensional arrays with at least three dimensions
  • Dynamic data types (i.e. user-defined data types containing pointers to dynamically allocated memory)
  • Multiple modules and separate compilation (i.e. each module is contained in a separate file), plus a shell script with the sequence of commands needed to compile your program. Note that a shell script is just a text file beginning with the line

    #!/bin/sh
    
    

    and containing a sequence of commands as you would type them into the shell.

Back to the course information page