Algorithms Answers

Consider the following infix expression

Q: ((A+C)*D)ꜛ(B+F/E)+G use POLISH Algorithm to translate Q into its equivalent postfix expression P.

Let A, B, C, D, E, F, G, H be eight data items with the following assigned weights:

Data item: A B C D E F G H

Weight: 20 7 11 17 5 10 24 6

Construct Binary tree using Huffman Algorithm also find the path length of the tree.

Draw a flowchart that will input values for A and B. Compare two values inputted and print which of the values is higher including the remark “Higher”.

Consider the following infix expression 

Q: ((A+C)*D)ꜛ(B+F/E)+G use POLISH Algorithm to translate Q into its equivalent postfix expression P.

Let A, B, C, D, E, F, G, H be eight data items with the following assigned weights:

Data item: A B C D E F G H

Weight: 20 7 11 17 5 10 24 6

Construct Binary tree using Huffman Algorithm also find the path length of the tree.

Question 3

a) Using C or C++ or a program of your choice, write a program that list the storage size of a float, list the minimum and maximum float values, and the precision of the float. 

​​​​​​​​​​​​[10 marks]

b) Describe the steps of how you will compile the program written in Question a) above in a typical compiler such as gcc or a compiler of your choice. ​​​[10 marks]

c) Show the output (screenshot) of how you have compiled the program written in Question a) above and attach all files (screenshot) generated where applicable. [5 marks]

​​​​​​​​​

b) The IBX company has recently acquired a state-of-the-art

language processing system; and its components work

seamlessly to compile source programs into object codes

for the computer to execute. As a compiler designer and

constructor, you are required to show and educate new users

on its use.

(i). Describe, in your own words, the parts/components of

the language processing system that your company has acquired to users to understand, and explain the role(s)

that each component plays in the compilation process. ​​​​[7 marks]

(ii). Explain how each component accomplishes its role(s)

in the compilation process and the output that it produces

​​​​​​​​​​​​[4 mar

Question 4

a. You were employed as a compiler designer at IBX company, you know that a program may have different types of errors that the compiler can flag during compilation.

i) explain the type of errors that a junior colleague who presented the following code to will have

z = (31 + 1) * 11);

if a > b a =5 ;

while ( s == 7) do f1();

​​​​​​​​​​​​[8 marks]

ii) Describe how the errors above can be debugged. 

​​​​​​​​​​​​[6 marks]

Question 2

Compiler is a translator program that translates a program written in High Level Language, the source

program and translates it into an equivalent program in Machine Level Language, the target program

a) The computing systems have seen novel compilers created over the years. State 5 examples of compilers

​​​​​​​​​​​​[5marks]

b) A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation. By means of a diagram, indicate the phases of compiler

​​​​​​​​​​​​[8 marks ]

c) The position of a projectile is described as ; position = initial + rate * 25. Describe the tokens to be generated by the lexical analyser and draw the syntax tree during the syntax analysis

​​​​​​​​​​​​[12 marks]

​c) Classify each of the following grammar rules according to Noam Chomsky’s classification of ​grammars (in each case give the largest – i.e. most restricted - classification type that applies):

​1. aSb → aAcBb

​2. B → aA

​3. S → aBc

​4. S → aBc

​5. Ab → b

​6. AB → BA

Question 1

A language processing system aims at compiling source programs into codes

for the computer to execute. A language can thus be defined as a set of strings. There are several known ways of specifying a language.

​a) Describe what a grammer is ​​​​​​

​b) Given a language L and grammer denoted as G1 show that aabb is in L(G1) where the the ​grammer G1 is defined as 

​1. S —›ASB

​2. S —›Ɛ

​3. A —›a

​4. B —›b

​where a,b are terminal symbols and Ɛ represents the null string.

​​​​​​​​​​​​​

​​​​​

5(a) Let X denote a uniform random variable model in the interval [α, β] given by

1

𝑓(𝑥) = {

⁄

(𝛽 − 𝛼)

, 𝛼≤𝑥≤𝛽 0, 𝑜𝑡h𝑒𝑟𝑤𝑖𝑠𝑒 .

AP[4]

5

(i) Show that the 𝑆𝐷(𝑋) = (𝛽−𝛼) CR [6] 2√3

(ii)explain your results with respect to the given uniform random variable model, CR [4]

(b) Use Matlab to plot and simulate the function 𝑈 = 2 log10(60𝑥 +

1) 𝑎𝑛𝑑 𝑉 = 3 cos(6𝑥), over the interval 0 ≤ 𝑥 ≤ 2. Properly label

the plot on each curve. The variable 𝑈 𝑎𝑛𝑑 𝑉 represents speed in miles per hour, the variable 𝑥 represent distance in miles. EV [4]

(c) Use Matlab to plot the function 𝑇 = 8𝑙𝑛𝑡 − 5𝑒0.3𝑡, over the interval

1 ≤ 𝑡 ≤ 3 . Put a title on the plot and properly label the axes. The variable T represents temperature in degree Celsius, the variable t represent time in minutes. CR [4]

(d)Suppose 𝑥 takes on the values 𝑥 = 1, 1.2, 1.4, ... ,5. Use matlab to simulate and compute the array Y that result from the function Y=6sin(5x