Using the file I/O style demonstrated on page 638, write a program that reads matrices in from a file and writes the product of the matrices to another file. You may assume that the input file is formatted as follows:
Here is a sample input file.
The program must check for file errors. It must also check that the matrices are compatible (interior dimensions are equal). The product should be output in the same format as the input file. The program should report rational error messages.
Note: It is not necessary to optimize the order in which the matrices are multiplied, a left to right evaluation order is fine. You may assume that no dimension exceeds 20 and allocate memory statically. You may not assume a bound on the number of matrices to be multiplied.
For this problem, you must take as input from a prompt a properly formatted 3SAT Boolean formula in CNF form and return either a satisfying assignment or false. The CNF formula should be of at most 15 variables (labeled '1' through '15', with a negation sign indicating a 'not'). Parentheses indicate clauses. ex: (1 -2 3) (4 -2 6) (-2 5 -3) You may assume a bound on the number of clauses (say 20) and you may assume that no variable appears more than once in a clause. Your output should be either of the form "false" or "true: 1 2 3 -4 5 6 ... " indicating any satisfying truth assignment. You do not have to find more than one satisfying assignment. You should find an assignment involving all 15 variables, even if the actual formula contains fewer than 15.
One algorithm that you might use would be to iterate through all possible truth assignments and test them, stopping the test when you find a clause that the truth assignment does not satisfy.
Hint: If you represent the truth assignment as a 16-bit integer, then you can cycle through the truth assignments by incrementing. Strategic use of bit shifting or exponentiation and modular division (% operator) can then be used to extract specific variable assignments.
Hint: You may read the clauses from the buffer into a 2D array and then use that data structure for testing (passing one row at a time to a clause testing function).
Note: CNF stands for "Conjunctive Normal Form" the formula (1 2) (-2 3) stands for (1 v 2) ^ (~2 v 3). This is a conjunction of disjunctions.
Note: Someone in class asked about a non-satisfiable formula. It is a theorem that all 3SAT formulas with less than 8 clauses are satisfiable. An 8 clause formula that cannot be satisfied can be constructed by choosing any 3 variables and making a formula from each of the possible 8 distinct clauses that can be formed with those three variables. Clearly, this formula must be unsatisfiable.
Take in a line of input, and print 'true' if the line is a palindrome and 'false' if it is not. Spaces, punctuation and capitalization should be ignored in the test. Again, the program should handle any errors in an intelligent way.
Hint: Once you know the length of a string, a stack (which can be emulated with an array) is a good data structure to use for testing if a string is a palindrome.
Hint: The cin.get() function will not "get" the newline character at the end of the input - instead it prompts for more input. However cin.peek() will detect the new line ('\n') so that you can do something about it!
Hint: If your solution is more than 20 lines - redo it! You didn't make use of the facilities available to you. My solution (minus declararions) is under 10 lines.
A good test case: "A man, a plan, a canal, Panama!" is a palindrome.
This page was last edited: Tuesday, December 14, 2004 12:17:55 PM