CSI 3120, Fall 2016, Assignment 1 Handed out Sep. 16, due Sep. 30 at 6:00pm.
Ensure your student name and number are provided. Submit your answers in a text document. For coding questions, outline the additional files submitted and do not forget to include them. Assignment should be done individually.
Note: In the programming questions, ensure that your code is compilable / interpretable as only code that executes will be considered for marking purposes. In the written questions, express but more importantly explain your opinion.
Problem 1 [2 marks] Scheme
Implement (using Scheme) the heapsort algorithm based on the pseudo-code provided below. The
algorithm includes two main sub routines, heapify and siftDown, which are also shown below. Note: Only use the core Scheme functions discussed in class.
// Sort the provided “a” array of integers using the heapsort algorithm procedure heapsort(a) is
count = length(a) // calculate the length of the array heapify(a, count)
endIndex = count – 1
while endIndex > 0 do
swap(a[endIndex], a[0]) // swap the values in the array endIndex -= 1
siftDown(a, 0, endIndex)
// Create an in-place heap of the provided “a” array procedure heapify(a, count) is
endIndex = count – 1
startIndex = parentIndex(endIndex) while startIndex >= 0 do
siftDown(a, startIndex, endIndex) startIndex -= 1
// Repair a “broken” heap
procedure siftDown(a, startIndex, endIndex) is
rootIndex = startIndex
while leftChildIndex(rootIndex) <= endIndex do child = leftChildIndex(rootIndex)
swapIndex = rootIndex
if a[swapIndex] < a[child] swapIndex = child
if child+1 <= endIndex and a[swapIndex] < a[child+1] swapIndex = child + 1
if swapIndex = rootIndex break
else
swap(a[rootIndex], a[swapIndex]) // swap the values in the array rootIndex = swapIndex
Here are the calculations for accessing the parentIndex, leftChildIndex and rightChildIndex positions.
// Calculate the parent index of a heap based on the end index "i" parentIndex(i) = floor((i-1) / 2)
// Calculate the left / right children indexes based on the root index "i" leftChildIndex(i) = 2*i + 1
rightChildIndex(i) = 2*i + 2
Your function `heapsort` takes a single argument, l, a simple list (i.e., containing no sublists), and returns a sorted list of all atoms contained in l.
(define (heapsort l) ; your code here )
Here are a few test cases to consider. Please try others.
(heapsort '()) => ‘()
(heapsort ‘(1)) => ‘(1)
(heapsort ‘(1 2 3)) => ‘(1 2 3) (heapsort ‘(4 3 2 1)) => ‘(1 2 3 4) (heapsort ‘(5 3 4 1 2)) => ‘(1 2 3 4 5)
Submit your code in a file named heapsort.scm with the following header:
; CSI 3120 Assignment 1 Question 1
; Student Name:
; Student Number:
Problem 2 [2 marks] Prolog
In computer architecture lingo, a one-bit full adder is a circuit that takes three bits as inputs and produces two bits as outputs. The first two inputs are the two bits to be added and the third input is a carry bit. The first output is the sum and the second output is a carry bit for the next adder. The circuit contains two XOR gates (X1 and X2), two AND gates (A1 and A2) and one OR gate (O1). Figure 1 illustrates this concept.
Let us develop a Knowledge Base using first-order predicate logic to represent the operation of a one- bit full adder.
The relevant concepts in this domain are:
circuit
wires
gates (type: XOR, AND, OR, NOT)
signals
terminals
inputs
outputs
connectivity between terminals
Let us decide on a vocabulary (using predicate logic) to model each domain concept as follows:
gates
o gate(x1)
o gate_type(x1) = xor
circuits
o circuit(c1)
terminals (input and output) o terminal(t1)
o in(2, x1) = terminal(t3) o out(1, x1) = terminal(t4)
number of input and output terminals
o arity(c1, 3, 2) o arity(x2, 2, 1)
connectivity
o connected(terminal1, terminal5) o connected(out(1,x1), in(1, x2))
signals
o on(terminal1)not good for inferences
o signal(terminal1)=0, signal(terminal2)=1
The next step is to encode general domain knowledge to describe the behavior of this circuit. This is done through a set of predicates as shown below:
1. If two terminals are connected, they have the same signal
T1T2 [(terminal(T1) terminal(T2) connected(T1, T2)) signal(T1) = signal(T2)]
2. The signal at every terminal is either 1 or 0
T [terminal(T) (signal(T) = 1 signal(T) = 0)] 3. Connected is commutative
T1T2 [connected(T1,T2) connected(T2,T1)] 4. There are four types of gates
G [(gate(G) k = gate_type(G)) (k = AND k = NOT)]
5. An AND gate’s output is 0 if and only if any of its inputs is 0
k = OR
k = XOR
G [(gate(G) gate_type(G) = AND) (signal(out(1,G))=0 N signal(in(N,G))=0)]
6. An OR gate’s output is 1 if and only if any of its inputs is 1
G [(gate(G) gate_type(G) = OR) (signal(out(1,G))=1 N signal(in(N,G))=1)]
7. An XOR gate’s output is 1 if and only if its inputs are different
G [(gate(G) gate_type(G) = XOR) (signal(out(1,G))=1 signal(in(1,G)) ≠ signal(in(2,G)))]
8. A NOT gate’s output is different from its input
G [(gate(G) gate_type(G) = NOT) (signal(out(1,G)) ≠ signal(in(1,G)))]
9. The gates (except for NOT) have two inputs and one output
G [(gate(G) gate_type(G) = NOT) arity(G,1,1)]
G [(gate(G) k = gate_type(G) (k = AND k = OR k = XOR))
arity(G,2,1)]
10. A circuit has terminals, up to its input and output arity, and nothing beyond its arity.
CIJ [circuit(C) arity(C, I, J)
[N ((N ≤ I terminal(in(N, C)) (N > I in(N,C) = Nothing) )
N ((N ≤ J terminal(out(N,C)) N > J out(N,C) = Nothing) )]]
11. Gates, terminals, signals, gate types and Nothing are all distinct.
GT[(gate(G) terminal(T)) G≠T≠1≠0≠OR≠AND≠XOR≠ NOT ≠ Nothing]
12. Gates are circuits.
G [gate(G) circuit(G)]
After defining the rules that govern the functioning of our one-bit full adder C1, the last step is to create
the set of predicate terms (entities) it is composed of.
circuit(c1) arity(c1, 3, 2) gate(x1) gate_type(x1) = XOR gate(x2) gate_type(x2) = XOR gate(a1) gate_type(a1) = AND gate(a2) gate_type(a2) = AND
gate(o1) gate_type(o1) = OR connected(out(1, x1), in(1, x2)) connected(out(1, x1), in(2, a2)) connected(out(1, a2), in(1, o1)) connected(out(1, a1), in(2, o1)) connected(out(1, x2), out(1, c1)) connected(out(1, o1), out(2, c1)) connected(in(1, c1), in(1, x1)) connected(in(1, c1), in(1, a1)) connected(in(2, c1), in(2, x1))
connected(in(2, c1), in(2, a1))
connected(in(3, c1), in(2, x2))
connected(in(3, c1), in(1, a2))
Your job is to translate the above Knowledge Base (expressed in first-order predicate logic) to a meaningful SWI Prolog program.
Important: Make sure the set of facts and rules you will create in Prolog conform to the predicate and function names above as much as possible.
Now create another SWI Prolog file where you will write the following queries (in Prolog syntax): a) What combinations of inputs would cause the sum bit to be 0 and the carry bit to be 1?
b) What combinations of inputs would cause the outputs of gates X1 and A1 to be identical? c) What gate(s) is/are neither directly nor indirectly connected to O1?
The answers returned by the SWI Prolog interpreter should be placed in a .txt file.
Finally, run your program in the Prolog interpreter and share your session output (i.e., the queries returned). If more than one answer is provided by the interpreter, include them all in your .txt file.
Your knowledge base file should be called onebitadder.pl
And the query file should be called onebitadderqueries.pl
And the answers from the queries should be in a file called onebitadderqueries.txt
Start each SWI Prolog file with the following header:
% CSI 3120 Assignment 1 Question 2
% Student Name:
% Student Number:
Problem 3 [1.75 marks] History of Programing Languages
What languages (list the main ones along with their general purposes and characteristics) existed at the
time when Lisp was created? Next consider the same question but replace “Lisp” with “Prolog”.
a. Give a general discussion of why researchers felt it was necessary to create these new “odd” languages (Lisp and Prolog).
b. Discuss how Lisp and Prolog have influenced two more modern general-purpose languages.
Problem 4 [1.75 marks] Evaluation of Programing Languages
Think (carefully) about how you would implement the programs for Problem 1 and 2 using Java.
In the context of each of these problems, what would be the pros and cons of using Lisp (Scheme), Prolog and Java?
Please make sure you answer this question using the language evaluation criteria discussed in class (and referenced from the course textbook / material).
Submission Guidelines
Please submit your solution through BlackBoard Learn before the specified deadline. Late submissions are allowed at a penalty of 10% of the marks per day late.
Your solution is a ZIP file with your student number (e.g., 1234567.zip) and containing the following files:
Your answer to question 1 (heapsort.scm)
Your answer to question 2 (onebitadder.pl, onebitadderqueries.pl and onebitadderqueries.txt)
Your answer to question 3 (A1Q3. doc or A1Q3.pdf)
Your answer to question 4 (A1Q4. doc or A1Q4.pdf)