Assignment 1: Functional Programming Recap and Semantic Tableau

Due Friday, February 2 at 11:59 PM

Goals for This Assignment

By the time you have completed this work, you should be able to:

• Monitor class announcements with Piazza
• Write some purely functional code in Racket
• Implement a basic Boolean evaluator in Racket
• Implement a basic SAT solver using the semantic tableau technique, in Racket

• boolean_evaluator.rkt
• sat_solver.rkt
• assign1_questions.txt
• collaborators.txt

Step-by-Step Instructions

Step 1: Sign up for Piazza

Click this link to sign up. All course announcements will be through Piazza, so it is very important that you sign up!

Step 2: Download and Install Racket

For this assignment, you'll be using Racket, a functional programming language very similar to Scheme. Racket provides some nice capabilities we'll use in this assignment (namely pattern-matching and immutable hash tables). It can be downloaded from this link.

The file extension for Racket code is .rkt.

Step 3: Implement an Evaluator of Boolean Expressions

Download boolean_evaluator.rkt. You will need to define a recursive evaluator of Boolean expressions in this file. The comments in the file provide more details.

Step 4: Implement a SAT Solver Based on Semantic Tableau

Download sat_solver.rkt. You will need to define a SAT solver using the semantic tableau technique. The comments in the file provide more details.

(OPTIONAL BONUS WORTH +15%) Step 5: Answer Related Questions

Download assign1_questions.txt. There are two questions in this file, related to how you might implement two possible extensions to your SAT solver implementation. You do not need to write any code for this portion, though you may write short snippets if it'd help explain your approach. I'm interested in seeing your general approach to these problems; there are many possible correct answers.

Step 5: Turn in Your Answers Using Canvas

Log into Canvas, and go to the COMP 410 class. Click “Assignments” on the left pane, then click “Assignment 1”. From here, you need to upload the following files:

• boolean_evaluator.rkt
• sat_solver.rkt
• assign1_questions.txt (only if you attempted the bonus)

In addition, if you collaborated with anyone else, be sure to download collaborators.txt and write the names of the people you collaborated with in the file, one per line. Please submit this file along with the other files.

You can turn in the assignment multiple times, but only the last version you submitted will be graded.