In this project, you need to submit three items: $(1)$ an algorithm report, $(2)$ a program that implements your algorithm, $(3)$

output of your program on test instances.

A$.$ Submission Item One: An Algorithm Report

First, you are to design an efficient algorithm for the $$Condition Satisfiability Problem$,$ and submit it as a report. The report

is just like what we usually do for algorithm design in a homework, and should have the four elements as usual:

$1)$ The main idea of your algorithm.

$2)$ The pseudo code of your algorithm.

$3)$ The proof of correctness for your algorithm.

$4)$ the analysis of time complexity for your algorithm.

B$.$ Submission Item Two: A Program That Implements Your Algorithm

You need to implement your algorithm using a commonly used programming language, such as Python, C$++,$ Java, etc. We

encourage you to use Python if possible, but other languages are fine, too.

Your program will take a list of instances of the $$Condition Satisfiability Problem$$ as input, and return a list of solutions

$($corresponding to those instances$)$ as its output.

To test your program, we will provide you with input instances as a $$dictionary$$ in Python $($after you have submitted the

program$),$ and ask you to submit the output solutions as a $$list$$ in Python. $($Details on the two files, including their formats,

will be explain in the next subsection for $$Submission Item Three$.)$

When you submit your program, you need to explain clearly how to run your code. If your programming language is not

Python, then you also need to include an explanation on how to turn the provided $$dictionary$$ of $$input instances$$ in Python

to your programming language, and how to turn your $$output solutions$$ in your programming language to a $$list$$ in Python

$($following the formats specified in the next subsection$).$