{"id":1766,"date":"2017-10-08T22:35:30","date_gmt":"2017-10-08T11:35:30","guid":{"rendered":"http:\/\/casestudyhelp.com\/sample-questions\/?p=1766"},"modified":"2018-01-19T18:25:39","modified_gmt":"2018-01-19T07:25:39","slug":"programming-assignment-on-comp4418-2017-assignment-2","status":"publish","type":"post","link":"https:\/\/casestudyhelp.com\/sample-questions\/programming-assignment-on-comp4418-2017-assignment-2\/","title":{"rendered":"Programming Assignment on COMP4418, 2017 \u2013 Assignment 2"},"content":{"rendered":"

Due: 14:59:59pm 04 October (Week 10)<\/strong><\/p>\n

Late penalty: 10 marks per day<\/strong><\/p>\n

Worth: 15 %<\/strong><\/p>\n

 <\/p>\n

This assignment consists of five questions.<\/p>\n

1-[20 Marks] <\/strong>(Answer Set Programming)<\/p>\n

A clique <\/em>of a graph is a set of vertices C <\/em>that are all adjacent to each other. That is, for a graph with vertices V <\/em>and undirected edges E <\/em>\u2286 <\/em>{{<\/em>x, <\/em>y<\/em>}<\/em> | <\/em>x, y <\/em>\u2208 <\/em>V <\/em>}<\/em>, a clique is a set C <\/em>\u2286 <\/em>V <\/em>such that for all x <\/em>\u2208 <\/em>C <\/em>and y <\/em>\u2208 <\/em>C<\/em>\u00a0<\/em>, if x <\/em>= y<\/em>, then {<\/em>x, <\/em>y<\/em>}<\/em>\u00a0<\/em>\u2208 <\/em>E<\/em>. A k-clique <\/em>is a clique of size k<\/em>, that is, |<\/em>C<\/em>\u00a0<\/em>| <\/em>= k<\/em>.<\/p>\n

(a) Write an ASP program that decides the k<\/em>-Clique problem:<\/p>\n

Input: \u00a0A graph with vertices V <\/em>and edges E <\/em>\u2286 <\/em>V <\/em>\u00d7 <\/em>V <\/em>, and a natural number k <\/em>\u2265 <\/em>0.<\/p>\n

Problem: decide if there is a k<\/em>-clique.<\/p>\n

Assume the input parameters \u00a0V <\/em>, E<\/em>, k <\/em>are encoded in ASP in the form of a unary predicate v, a binary predicate e, and a constant symbol k, respectively. Use a unary predicate c to represent the vertex cover C <\/em>. Your program should have no more than two rules.<\/p>\n

(b) \u00a0Use an ASP solver1 to determine how many k<\/em>-cliques the graph has for k <\/em>\u2208 <\/em>{<\/em>3,<\/em>\u00a0<\/em>4, <\/em>5, <\/em>6}<\/em>.\u00a0 Hint: \u00a0the number of 2-cliques is 11.<\/p>\n

\"programing\"<\/a><\/p>\n

    \n
  1. [20 Marks] <\/strong>(Answer Set Programming) Consider the following logic program P <\/em>.<\/li>\n<\/ol>\n

    a <\/em>:- not b, <\/em>not c. <\/em><\/p>\n

    b <\/em>:- not a, <\/em>not c. <\/em><\/p>\n

    c <\/em>:- not a, <\/em>not b. <\/em><\/p>\n

    d <\/em>:- a.<\/em><\/p>\n

    d <\/em>:- b. <\/em>d <\/em>:- c.<\/em><\/p>\n

    Determine stable models of this program. For every candidate interpretation S<\/em>, specify the reduct\u00a0P<\/em>\u00a0<\/em>S<\/em>\u00a0<\/em>. Give your solution in a table of exactly (!) the following form and order:<\/p>\n

    ———<\/p>\n

     <\/p>\n

    1\u00a0For instance, you can download the Clingo ASP solver from https:\/\/potassco.org\/ and run your program with\u00a0 clingo –const k=k \u00a0<\/em>-n \u00a00 clique.lp or .\/clingo \u00a0–const k=k \u00a0<\/em>-n \u00a00 clique.lp where k <\/em>\u2208 <\/em>N is the size of the clique.<\/p>\n

     <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    Candidate S<\/td>\nReduct P S<\/td>\nStable model?<\/td>\n<\/tr>\n
    {a, b, c, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    d :- a.\u00a0\u00a0\u00a0 d :- b.\u00a0\u00a0\u00a0 d :- c.<\/td>\n\u2717<\/td>\n<\/tr>\n
    {a, b, c}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a, b, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a, c, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {b, c, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a, b}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a, c}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {b, c}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {b, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {c, d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {a}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {b}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {c}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {d}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    {}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
      \n

    1. \n[20 Marks] <\/strong>(Reasoning about Knowledge) Suppose all you know is the KB<\/li>\n<\/ol>\n

      \u2200<\/em>\u00a0<\/em>x <\/em>(P<\/em>\u00a0<\/em>(x<\/em>) \u2194 <\/em>x <\/em>= #\u00a01 \u2228 <\/em>x <\/em>= #\u00a02) \u2227 <\/em>\u2200<\/em>\u00a0<\/em>x <\/em>(P<\/em>\u00a0<\/em>(x<\/em>) \u2194 \u00ac<\/em>Q<\/em>(x<\/em>))<\/p>\n

      (a) Determine the set of known instances of P <\/em>(x<\/em>) \u2227 \u00a0<\/em>Q<\/em>(y<\/em>), \u00a0that \u00a0is, all pairs of standard names<\/p>\n

      (n<\/em>1 , <\/em>n<\/em>2 ) \u2208 <\/em>{<\/em>#\u00a01, <\/em>#\u00a02, <\/em>#\u00a03, . . <\/em>.<\/em>}<\/em>\u00a0<\/em>\u00d7 <\/em>{<\/em>#\u00a01, <\/em>#\u00a02, <\/em>#\u00a03, . . <\/em>.<\/em>}<\/em>\u00a0\u00a0<\/em>such that O<\/strong>KB |<\/em>=\u00a0K <\/strong>(P<\/em>\u00a0<\/em>(n<\/em>1 ) \u2227 <\/em>Q<\/em>(n<\/em>2 )).<\/p>\n

      (b) \u00a0Determine RES[KB, <\/em>(P <\/em>(x<\/em>) \u2227 <\/em>\u00ac<\/em>Q<\/em>(y<\/em>))].<\/p>\n

      You may simplify the resulting formula to eliminate true and false.<\/p>\n

        \n
      1. [20 Marks] <\/strong>(Limited Belief ) Consider the knowledge base<\/li>\n<\/ol>\n

        (F <\/em>\u2192 <\/em>C<\/em>\u00a0<\/em>) \u2227 <\/em>(C <\/em>\u2194 \u00ac<\/em>U<\/em>\u00a0<\/em>).<\/p>\n

        (a) Bring this knowledge \u00a0base into proper+\u00a0\u00a0form.<\/p>\n

        Let KB denote the resulting proper+\u00a0\u00a0knowledge base.<\/p>\n

        (b) \u00a0Determine the minimal k <\/em>\u2265 <\/em>0 such that O<\/strong>KB |<\/em>\u2248 <\/em>K<\/strong>k <\/em>(F <\/em>\u2228 <\/em>U <\/em>\u2228 <\/em>C<\/em> ) hold? (c) Determine the minimal k <\/em>\u2265 <\/em>0 such that O<\/strong>KB |<\/em>\u2248 \u00ac<\/em>K<\/strong>k <\/em>\u00ac<\/em>(\u00ac<\/em>F <\/em>\u2227 <\/em>\u00ac<\/em>U<\/em> ) hold?<\/p>\n

        [20 Marks] \u00a0<\/strong>(Reasoning about Action)<\/p>\n

        Suppose we have a domestic service robot cleaning up our house. It has a box, and into that box it can put objects. The robot can also shake the box to test whether something is in it. \u00a0Finally it can move the box and its contents to other locations. We assume that in reality, the box does contain some object, but the robot does not know that. \u00a0This scenario is modelled by the following basic action theory:<\/p>\n

        \u03a30 \u00a0= {\u2203<\/em>\u00a0<\/em>x <\/em>InBox(x<\/em>)}<\/em><\/p>\n

        \u03a3dyn = {<\/em>DPoss(a<\/em>)\u00a0\u2194 <\/em>true<\/p>\n

        DSF(a<\/em>) \u2194 <\/em>(a <\/em>= shakeBox \u2192 \u2203 <\/em>x <\/em>InBox(x<\/em>))<\/p>\n

        D[a<\/em>]InBox(x<\/em>) \u2194 <\/em>a <\/em>= putInBox(x<\/em>) \u2228 <\/em>InBox(x<\/em>)<\/p>\n

        D[a<\/em>]location(x<\/em>) = y <\/em>\u2194 <\/em>(a <\/em>= moveBox(y<\/em>) \u2227 <\/em>InBox(x<\/em>)) \u2228 <\/em>(\u2200<\/em>\u00a0<\/em>y<\/em>l<\/em>\u00a0<\/em>a <\/em>= moveBox(y<\/em>l<\/em>\u00a0<\/em>) \u2227 <\/em>location(x<\/em>) = y<\/em>)}<\/em><\/p>\n

        Prove or disprove the following projection problems using regression: (a) \u03a30 \u2227 <\/em>\u03a3dyn |<\/em>= \u2200<\/em> x <\/em>[putInBox(x<\/em>)]InBox(x<\/em>)<\/p>\n

        (b) \u00a0\u03a30 \u2227 <\/em>\u03a3dyn |<\/em>=\u00a0\u2200<\/em>\u00a0<\/em>y<\/em>\u00a0<\/em>[moveBox(y<\/em>)]\u2200<\/em>\u00a0<\/em>x <\/em>(InBox(x<\/em>) \u00a0\u2192 <\/em>location(x<\/em>) = y<\/em>)<\/p>\n

        (c) \u03a30 \u2227 <\/em>\u03a3dyn \u2227 <\/em>O<\/strong>\u03a3dyn |<\/em>=\u00a0[shakeBox]K <\/strong>\u2203<\/em>\u00a0<\/em>x <\/em>InBox(x<\/em>)<\/p>\n

        (d) \u00a0\u03a30 \u2227 <\/em>\u03a3dyn \u2227 <\/em>O<\/strong>\u03a3dyn |<\/em>=\u00a0[shakeBox]\u2203<\/em>\u00a0<\/em>x <\/em>K <\/strong>InBox(x<\/em>)<\/p>\n

         <\/p>\n

        You may abbreviate putInBox by p<\/em>, moveBox by m<\/em>, shakeBox by s<\/em>, InBox by I <\/em>, and location by \u00a3<\/em><\/p>\n

        for better readability.<\/p>\n