CS-341 Extra Credit Options

Introduction

This document gives you some options for improving your grade by doing extra work for the course. One option is to write a paper, and the other is to write a computer program. You may choose either option (or neither), but not both. The paper and program options are described below. If you choose to do one of the options, it will count as an extra exam, which will be averaged in with the three real exams, with the following adjustments:

• Your extra credit work will be ignored if it would lower your grade in the course.
• Each exam and the extra credit work will count 25% of your course average, but if one exam grade is ten points less than the lower of the other two, the weight of that exam will be reduced to 0.15, the other two will have weights of 0.30 each, and the extra credit work will still count 0.25.

The Paper Option

Your paper should be in four parts: An introduction that tells what two systems you are going to compare and why they are important, two sections describing the two systems, and a final section that compares the two.

Your paper will be graded on how clearly written and organized it is, as well as the technical content. For information on the expected writing style, consult [ The Technical Communicators Resource Site ] by Duncan Kent & Associates Ltd. of Vancouver, BC, Canada. (I've found that access to this web site is very slow, but the quality of the material available there is very high.)

You may draw on material from printed publications (technical books and magazines, etc.) and/or web material. Web sites to consult include the vendors who produce the processors and/or chip sets, such as Intel [ www.intel.com ], Advanced Micro Devices [ www.amd.com ] VIA Technologies [ www.viatech.com ], and the sites that provide vendor-neutral information, such as [ www.arstechnica.com ], [ www.slashdot.com ], [ www.aceshardware.com ], and [ www.geek.com ].

Here are some specific links to Intel pages you can look at:

• [ developer.intel.com/update/contents/dt12006.htm ]
• [ developer.intel.com/update/contents/dt12002.htm ]
• [ developer.intel.com/update ]

NOTE: You must cite the sources of all material you used to prepare your paper in the following two ways:

1. Provide a numbered list of your references at the end of your paper, giving complete publication information for each one. There is an example in the References section at the end of this web page. (For a book, this means the author, title, publisher, and date of publication; for an article it means the author, title, publication name, page numbers, and date of publication; for a web page, it means the author, the page's title (the one that appears in the title bar of your navigator), and the complete URL for the web page.
2. Each idea in your paper must be expressed in your own words, and followed by the number(s), in square brackets, of the reference(s) where the idea came from. For example, if I wanted to cite this web page in my paper, the sentence that talks about it would look like this one.[1]

Failing to cite your sources of information accurately is as serious an error as having someone else write your paper for you in academic circles, so be sure to do this right.

The Programming Option

The steps your program should go through are:

1. Read two expressions from the user, either interactively or as command line arguments. The two expressions are entered as strings of characters.
2. Determine how many variables there are by scanning the two strings. Given the total number of different variables in the two expressions, you know how many rows the two truth tables must have. (They both have to have the same number of rows.)
3. Evaluate both expressions for every row of its truth table.
4. Display the two truth tables and a message that tells whether they are the same or diffferent.

• The syntax of the expressions entered should be as natural as possible.
• There should be no limit on the number of variables in an expression.
• Spaces shouldn't matter.
• It's reasonable to allow only single-letter variable names.
• You decide whether variable names are case sensitive or not.
• You decide what symbol to use for NOT, and whether it is a prefix or postfix operator. Someone asked about using uppercase letters for negated variables and lowercase letters for the same variables un-negated. That's okay too.
• You can either require all AND operators to be entered explicitly, or add them yourself when they are missing. (For example, you could automatically convert "abc" into "a*b*c"; it can be tricky to get this right when using parentheses and NOTs.)
• AND should have precedence over OR, and NOT should have precedence over AND. Optional: Allow XOR, with precedence equal to OR.
• Be sure to handle parentheses properly.

1. Create two pushdown stacks, one for operators, and one for operands.
2. Create a new string with the proper zeros and ones substituted for all the variables. (You have to convert the row number of the truth table into the proper set of ones and zeros.)
3. Going from left to right, examine each character in the expression.
   • If the character is a left parenthesis push it onto the operator stack.
   • If the character is an operand, push it onto the operand stack.
   • If the character is an operator, repeatedly evaluate the top operator on the operator stack by combining two operands from the operand stack and pushing the result back onto the operand stack; do this for each operator on the operator stack that has higher precedence than the current operator. Then push the current operator onto the operator stack.
   • If the character is a right parenthesis, repeatedly process operators from the operator stack until reaching a left parenthesis.
4. When the end of the expresion is reached, evaluate any operators remaining on the operator stack. This should leave exactly one value on the operand stack, which is the value of the expression for that row of the truth table.

Be sure to tell me exactly what syntax your program requires for entering the expressions.

Due Date and Collaboration

Put a printed copy of your paper, or a diskette containing the source code for your program, in my mailbox (SB Room A-202) or under my office door (SB Room A-222) by 5:00 PM on December 22. Alternatively, you can submit your material via email as late as midnight on December 22.

References