Assignment 1: Functional Programming Recap and Semantic Tableau


Due Friday, September 20 at 11:59 PM

Goals for This Assignment

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

Provided files:

Step-by-Step Instructions

Step 1: Implement an Evaluator of Boolean Expressions

For this assignment, you'll be using Python. While Python is not generally considered a functional language, we will be writing code that is mostly functional in nature. Notably, we will be using immutable linked lists, as well as immutable maps.

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

Step 2: Implement a SAT Solver Based on Semantic Tableau

Download sat_solver.py. 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 3: 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 4: 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:

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.