Computer Science & Engineering 505
Assignment 4

Due: October 27, 1999

  1. Write rules for manipulating sorted lists of numbers. Duplicate elements are allowed in the list. You should have the following rules:

    smember(A,L) -- succeeds if A is a member of list L. This should be similar to the ordinary member rule, but be sure to stop searching if A is larger than the element you're checking against.

    insert(A,L1,L2) -- L2 should be a new list formed by inserting A into list L1 at the correct location

    delete(A,L1,L2) -- L2 should be a new list formed by deleting A from list L1. If there are several occurences of A in the list, just delete one of them. If there is no occurence of A, then fail.

    Test your rules on suitable test cases, including some cases where A is left as a variable.

  2. The CLP(R) code in ~borning/505/resistors on the instructional machines solves some resistor/battery/meter circuit problems. Copy the file to your directory so that you can edit it. Add rules that define a switch: switch(Lead1,Lead2,State). If State=open, then there should be no current through the switch. If State=closed, then the currents in the leads should be equal and opposite, and the voltages at Lead1 and Lead2 should be the same.

    Write a rule that defines the following circuit. The states of the three switches should be parameters. First, use it to find the ammeter reading when all the switches are closed. Second, use it to find all possible switch settings such that the current is less than or equal to 1 ampere.

    Your rule could thus be something like the following:

    three_resistors(Amps,Switch1,Switch2,Switch3) :- .....
    To find the answer to the first part of the question, use this goal:
    ?- three_resistors(Amps,closed,closed,closed).
    To find the answer for the second part, use this. (Backtrack to get all possible answers.)
    ?- three_resistors(Amps,S1,S2,S3), Amps <=1.0.

    Generalize your rule to make a circuit with n resistor/switch pairs, where n is a parameter of the rule. Thus if n=5 you should get the following circuit. Demonstrate your rule working with n=20 to find the current with all switches closed, and then find at least one setting for all the switches such that the current is between 0.1 and 0.5 amperes.

  3. Consider the following version of the append rule:
    append([],Ys,Ys) :- !.
    append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
    Compare the behavior of this rule with the traditional version of append. Explain any differences.