5CCS2FC2: Foundations of Computing II
Coursework 1
Issued: 9 November 2020 Deadline: 18 November 2020
Notice to Candidates:
This assessment is to be completed independently and submitted on KEATS by 18:00
on the date specified above. You should submit your solutions via one of the KEATS
quizes provided on the module page. You only need to submit to one of the quizzes
for your preferred language. If you submit more than one version, your highest mark
will be taken.
The assessment is ‘open book’ but you should complete your work independently. Any
submitted code and work will be checked for plagiarism and collusion and discipliniary
action will be taken against any candidates caught colluding.
Please see the Plagiarism Declaration on KEATS.
The CLIQUE problem takes as input an undirected graph G = (V,E) and an integer k > 2,
and returns True if G contains a clique of size k, i.e a set of vertices C ⊆ V such that |C| = k
and (u, v) ∈ E for all u, v ∈ C.
1. Write a function clique_solver(G,k) that takes a graph G (described below) and integer
k as input and return a Boolean: True in that case that G contains a clique of size k and
False otherwise.
[7 marks]
2. Write a function sat_to_clique(F) that takes a formula F (described below) as input and
return a graph G and integer k as output such that:
F is satisfiable ⇐⇒ G has a clique of size k.
[10 marks]
3. Write a function sat_solver(F) that makes use of your previous two functions and takes
a formula F as input and returns a Boolean: True in the case where F is satisfiable and
False otherwise. [3 marks]
Page 1 of 2
4. Describe in your own words, how your function sat_solver(F) works and why it is able to
successfully determine whether the input formula F is satisfiable. [5 marks]
End of Questions
Futher Details
You should make use of the following pre-defined classes (available on KEATS for reference).
Graph
add_vertex(v) Adds a vertex v to the graph. Returns null.
add_edge(u,v) Adds an undirected edge to the graph from u to v.
Adds vertices u and v if not already present. Returns null.
get_vertices() Returns a list of all vertices.
get_edges() Returns a list of all edges.
has_edge(u,v) Returns True if there is an (undirected) edge between
u and v.
Formula
get_clauses() Returns a list of Clauses (described
below)
Clause
get_literals() Returns a list of integers representing each
clause
(positive literals are represented by positive integers and their correspond-
ing negative literals as their negative counterpart. For example, if P is
represented by the integer 2 then ¬P is represented by −2. etc.)
End of Document
Page 2 of 2

欢迎咨询51作业君