CSE 505: Computing with Logic

Warm-up Problems

1. pick_odd: Write an Prolog predicate pick_odd(L1, L2) that, given a list L1 returns in L2 the elements that occur at odd positions (i.e. 1,3,5,7,...) in L1. (Assume that the first element of a list is at position 1).

   For example, pick_odd([1,1,2,3,5,8,13,21,34,55], L) should return L=[1,2,5,13,34].

   You may define and use any helper predicates you need.

   Answer this question without using arithmetic.

   If you use arithmetic you'll get very little credit even if your predicate works as specified.

2. increasing_subsequence: Write a Prolog predicate incsub such that, given a list of integers L1, incsub(L1, L2) returns in L2 an increasing subsequence of L1. (You may assume that L1 contains distinct elements).

   L₂ is a subsequence of L₁ if all elements of L₂ also occur in L₁, and if a occurs before b in L₂ then a occurs before b in L₁ also.

   L is an increasing sequence if the elements are in ascending order: i.e. if a occurs before b in L, then a < b.

   For instance, incsub([2,4,1,7,3,8], L2) should succeed with answers L2 = [], L2 = [2], L2 = [4], L2 = [2,4], L2 = [1], ... (upon backtracking; a total of 26 distinct answers).

Graph Problems

Each graph is given an identifier (name or number), and we enumerate its edges as triples in a 3-ary edge relation. Each triple of the form edge(i, v1, v2) represents an edge in graph i between vertices v1 and v2. Example graphs and their Prolog encoding are shown below:

Graph ID	Pictorial Representation	Prolog Representation
a		edge(a,1,2). edge(a,2,3). edge(a,3,4). edge(a,1,3). edge(a,2,4).
b		edge(b,1,2). edge(b,2,3). edge(b,3,4). edge(b,4,5). edge(b,5,6). edge(b,6,1). edge(b,2,5). edge(b,3,6).

Given a set of graphs with edge relations specified in Prolog, your task is to write predicates to solve the following problems.

3. Write a unary predicate three_clique that, given a graph id, succeeds if and only if that graph has a 3-clique.

   For example, for graphs a and b in the above example, three_clique(a) should succeed while three_clique(b) should fail.

4. Write a 4-arty predicate simple_path such that, for queries of the form simple_path( i, v1, v2, P) where i is a graph id, v1 and v2 are vertices in graph i, succeeds by binding P to a list of vertices that lie on a simple path (i.e. cycle-free) path between v1 and v2.

   For example, simple_path(a, 1, 4, Y) should succeed with Y=[2], and upon backtracking, Y=[3], Y=[2,3], and Y=[3,2]. The order of answers does not matter.

5. Write a unary predicate non_bipartite that takes a graph id as an argument, and fails if and only if the given graph is bipartite.

   For example, non_bipartite(a) should succeed while non_bipartite(b) should fail.

Analysis of Program Traces

• malloc(p): Allocate a block of memory and assign its address to pointer p.
• read(p): Read value at address in pointer p
• write(p): Write value to address in pointer p
• free(p): Free (i.e. de-allocate) memory located at address in pointer p.

6. Write a predicate invalid_access, that, given a trace, succeeds if and only if the trace has a read/write event after that pointer has been freed, or before that pointer is malloced.

7. Write a predicate memory_safe, that, given a trace, succeeds if and only if all the memory operations are safe:
   1. reads and writes are to previously malloced (and not yet freed) memory.
   2. free refers to a previously malloced (but not yet freed) memory.

8. Write a predicate leak, that, given a trace, succeeds if and only there is a memory leak: a pointer is re-assigned with a malloc without freeing the earlier block.

9. Write a predicate value_safe, that, given a trace, succeeds if and only there all read operations are to addresses that have been previously initialized.

10. ** Come up with your own interesting analysis question over program traces (different from the above four), and write a predicate to solve that problem.

Grading:

3. Correct solution or a solution with very few flaws.
4. Solution that is substantially correct; some flaws but mostly correct.
5. Solution that is substantially incorrect; many flaws with few correct parts.
6. Incorrect or missing solution.

Code documentation is expected, except where the intent of the solution is obvious from its form. Partial credit may not be possible without clear documentation.

Submission:

I will post submission instructions shortly.