-------------------------------------------------------------------------------
Michael Locasto                       Introduction to Computer Programming in C
Homework 2                                                            Fall 2005
$Id: hw2.txt,v 1.6 2005/10/25 03:22:35 locasto Exp $
-------------------------------------------------------------------------------

Due: October 27th, 2005 Before Class (Courseworks timestamp).


0) Boolean Algebra. (50 pts)

   One class of primitive operations in C is logic relations (OR, AND, NOT,
   XOR, etc.). Each of these operators is represented by a few symbols.
   For example, OR is an operation that takes two operands and is represented
   by a double pipe:
    (expression || expression)
   AND is an operation that takes two operands and is represented by a double
   ampersand:
    (expression && expression)
   NOT is a unary operator; that is, it takes only 1 argument or operand and
   is represented by the exclamation point:
    !expression

   Write a program to print out the truth tables for the following
   logic expressions:

   a) p OR q OR (NOT q AND NOT r)
   b) p OR q
   c) p AND q
   d) NOT (p AND (NOT p OR q))

   The program should be called 'logic' and simply output the truth tables.
   It does not need to interpret any command line arguments.

   Note that you should NOT compute the logic tables yourself and simply
   print them out. Rather, you should iterate through the variables and
   the values they can have and have the machine generate the output
   values.

1) Fitting buildings in a town. (50 pts)

   The mayor of Springfield wants to revitalize the downtown to attract
   businesses. Due to a nuclear accident, the west side of Main Street
   is unusable. However, the east side of the street is prime real 
   estate that is going to waste (in other words, it is home to a crack
   house, a den of thieves, a brothel, a coffee shop, and an art gallery).

   The mayor plans to knock down all the structures on the east side of Main
   Street and put up new buildings. The street can hold 4096 meters of
   storefront. The mayor can build 5 types of buildings:

     1) Mom & Pop Shop:   300 meters of streetfront
     2) Acme Apartments:   50 meters of streetfront
     3) Supermarket:     1000 meters of streetfront
     4) House:             40 meters of streetfront
     5) Generic Office:   400 meters of streetfront

   The mayor wants to know how many of each type of building he can put
   up. One possible combination (order doesn't matter) is:

     4 supermarkets, 1 house, 1 apartment

   which leaves 6 meters of wasted space.

   The mayor has estimated that each type of building will bring in a
   certain amount of tax revenue, according to the following list:

     1) Mom & Pop Shop:   1000 dollars of tax revenue
     2) Acme Apartments:   800 dollars of tax revenue
     3) Supermarket:     40000 dollars of tax revenue
     4) House:              10 dollars of tax revenue
     5) Generic Office: 100000 dollars of tax revenue

   Thus, 4 supermarkets, 1 house, and 1 apartment are worth: 
      40000 
    + 40000 
    + 40000 
    + 40000 
    +    10
    +   800
    -------
     160810 dollars of tax revenue.

   Write a program called 'cityplan' to help the mayor figure out 
   what combination (remember, order doesn't matter) of buildings 
   should be built in order to maximize his tax revenue given the 
   available meters of space. 

   Questions:
    0. How many permutations of the solution your program arrived at are 
       there?
    1. Is there a fast way to solve this problem?
    2. A civic association has blackmailed the mayor to dedicate 96
       meters of space to construct a city park on Main Street. How
       does this change your answer? Is the problem any easier?
       Change your program so that it can solve this problem for
       any combination of available space, building size, and
       tax revenue.

/************************** EXTRA CREDIT *****************************/

2) Dump file contents to the standard output. (10 pts)

   Create a program called 'filedump' that is similar to the Unix utility 
   'cat' that prints out a file to standard output.

   filedump [filename]
   
   If no filename is provided, or the filename is the '-' character, then
   read from standard input. 

   As always, your program should handle these two usage cases:

   filedump --help
   filedump --version

   Augment your program to take a command line parameter that causes the
   tool to print out a line number at the beginning of each line of output.

   filedump -n [filename]

   Your program can use the Linux system calls open() and write()
   or the glibc functions fopen() and fprintf().