Programming Problem Set: 99 Problems Chapter 3

Home / Programming Problem Set: 99 Problems Chapter 3

Programming Problem Set: 99 Problems Chapter 3

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Logic and Codes. The problems in this chapter served as continuation of previous problems, therefore the numbering will start from the last problem.

40. Truth tables for logical expression

Define and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which
succeed or fail according to the result of their respective operations;
e.g. and(A,B) will succeed, if and only if both A and B succeed.

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

Example: table_p( A, B, xor(A,B) )
->
true true false
true false true
false true true
false false false

41. Truth tables for logical expressions (2)

Continue problem 40 by defining and/2, or/2, etc as being operators. This allows to write the
logical expression in the more natural way, as in the example: A and (A or not B).
Define operator precedence as usual; i.e. as in C.

Example: table2_p( A, B, A and (A or not B) )
 ->
true true true
true false true
false true false
false false false

41. Truth tables for logical expressions (2)

Generalize problem 41 in such a way that the logical expression may contain any number
of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table
for the expression Expr, which contains the logical variables enumerated in List.

The index is started from 1.

Example: table3_p( [A,B,C], A and (B or C) equ A and B or A and C)
 ->
<tt>true true true true
true true false true
true false true true
true fail false true
false true true true
false true false true
false false true true
false false false true

43. Gray code

An n-bit Gray code is a sequence of n-bit strings constructed according to
certain rules. For example,

n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010','110','111','101','100'].

Find out the construction rules and write a predicate with the following specification:

% gray(N,C) :- C is the N-bit Gray code

Can you apply the method of "result caching" in order to make the predicate more
efficient, when it is to be used repeatedly?

44. Huffman code

First of all, study a good book on discrete mathematics or algorithms for a detailed
description of Huffman codes, or consult wikipedia

We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms.
Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to
construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S.
In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'),
hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.].

Example: huffman_p(Fs,Hs)
-> Hs is the Huffman code table for the frequency table Fs

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

, ,

About Author

about author

xathrya

A man who is obsessed to low level technology.

Leave a Reply

Your email address will not be published. Required fields are marked *

Social media & sharing icons powered by UltimatelySocial