next up previous
Next: About this document

CS341, Spring 1996
Prolog Assignment #1
Assigned 5/22, due 5/31 midnight



  1. Remember merge sort? Sure you do. We're going to do it again. Write the predicate merge_sort/2 whose first argument is a list of numbers, and whose third argument produces the sorted version of the first argument. In doing so you should write the following predicates.
    1. split_evenly/3. The first parameter is a list of integers, whose elements should be split into lists of ``approximately'' equal length: if the input list has even length the output lists should have equal length; if odd, one should be one longer than the other. The second two parameters hold the output lists.

      One easy way to do this is by ``alternating'' moving elements from the first list to the second list, then from the first list to the third list. Here are some hints. Notice how my split_evenly function splits the list:

      :-  split_evenly([2,1],  L2,  L3)
      
      L2 = [2]
      L3 = [1]
      
      :-  split_evenly([1,2,3,4,5],  L2,  L3)
      
      L2 = [1, 3, 5]
      L3 = [2, 4]
      
      :-  split_evenly([1],  L2,  L3)
      
      L2 = [1]
      L3 = []
      

    2. merge/3. The first two parameters are sorted lists of integers; the third is the merge of the first two.

  2. Consider a directed weighted graph like the one in Figure gif. A common problem is to find the shortest path between any two nodes (for example, between a and g). The ``length'' of a path is defined to be the sum of the weights on the arcs between the nodes.

    One very simple shortest-path algorithm is to find all paths between a and g, compute the length of each path, and take the minimum. That is what you will implement here.

    1. Represent the graph with a set of assertions of the form connects(source, destination, weight) where source and destination are node names (these can be symbols), and weight is a non-negative integer.

    2. Write a predicate path_from(A, B, W) which succeeds if there is a path from node A to node B of length W.

    3. Write a predicate min/2 whose first parameter is a list of integers and whose second parameter holds the minimum of those integers. This predicate should fail if there are no integers in the list.

    4. Write a predicate shortest/3 whose first two parameters are node names, and whose third produces with the shortest path from the first two parameters.

  3. Congratulations! Your status as one of the world expert designers of Employee Databases has been recognized by management, who have called you in to improve on the current system. The current system is the code we have been looking at in class; for this part of the assignment you can use either implementation---whichever you feel most comfortable with.

    1. In the present system, when an employee is added you have to supply an Id number as input. Make it so the system assigns a unique Id number automatically. In doing so you will make add_employee take one fewer parameters.

    2. Management does not like the ``manager'' flag thing. Instead they want to know who manages who. Fix things so when an employee is added, no manager information is added. Then introduce a new predicate make_manager/2 which establishes that the first Id number is the manager of the second Id number. This should fail if the second Id number already has a manager (and that manager is different from the input).

    3. The new predicate subordinates/2 should produce the list of subordinates for the first parameter.

    4. Change the print_nicely predicate so it prints a list of the people the employee manages indented under the employee's name. For example,
      Employee 3: Name is Sally, Wage is 10.00
         Employee 2:  Name is Fred, Wage is 5.00
      
      You should only nest this list one deep, so if Fred manages anybody, they won't be displayed here.

    5. A deadbeat is defined as somebody who doesn't manage anybody, but who makes more than the average wage for all employees. Write the predicate deadbeat(Id) that succeeds if the Id is that of a deadbeat.

    6. Payroll. Write a new predicate add_hours(Id, Hours) that records the fact that the employee worked the specified number of hours. This should be cumulative. Then write the predicate payroll(N) which computes and returns in N the total payroll (total hours times wage rate) for all employees. The predicate should as a side effect reset the cumulative hours for all employees to 0.



    You will hand this assignment in electronically on the MSCC machines. Hand in two files: in one put your solution code, and in the other a transcript that shows tests of all parts of the solution.





next up previous
Next: About this document



Steve Hanks
Wed May 22 17:50:03 PDT 1996