CSc 8710, Deductive Databases and Logic Programming
Fall 2008
Homework 2 (Due: 23 September, 2008)

  1. Write a Prolog program to implement the predicate frequencies(L,M), which takes as input a list L and returns a list of pairs [x,n], where x is an element of L and n is the number of times x appears in L. Here are some sample runs in SWI Prolog:
    ?- frequencies([a,b,a,c,a,c,d,a],L).
    
    L = [[a, 4], [b, 1], [c, 2], [d, 1]] 
    
    Yes
    ?- frequencies([],L).
    
    L = [] 
    
    Yes
    
  2. Assume that a binary tree is represented in Prolog using the function term
      tree(X,LeftSubTree,RightSubTree)
    
    where X is the element at any node and LeftSubTree and RightSubTree are the left sub-tree and the right sub-tree for the node respectively. The term nil is used when there is no left sub-tree or right-tree. For example, the following function term:
    tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil))
    
    would represent the following binary (search) tree:
               20
              /  \
            10    40
                 /  
                30  
    
    Recall that a binary search tree is a binary tree in which all the elements in the left sub-tree of a node are less than the element at the node and all the elements in the right sub-tree of a node are greater than the element at the node. Assume that the binary search tree is being used to represent a set of numbers with no duplicates. Write Prolog programs for the following predicates:

Page Maintained by raj@cs.gsu.edu