Algorithms Answers

Bob employs a painting company that wants to use your services to help create an

invoice generating system. The painters submit an invoice weekly. They charge $30 per

hour worked. They also charge tax – 15%. Bob likes to see an invoice that displays all the

information – number of hours, the charge per hour, the total BEFORE tax and the total

AFTER tax. Since this is an invoice, we also need to display the name of the company

(Painting Xperts) at the top of the invoice. Display all of the information on the screen.

Using Pseudocode, develop an algorithm for this problem.

Using the hardware given to the right, show the addition of two numbers in steps as it would take 

place. 

A= 0.000125 

B= 0.0125 

Show the steps in detail. Also show the contents of different registers (R1, .. R6) and control bits (C1, 

.. C5). It is noted that Control bits (C1, .. C5) could be either 1 or 0 and you can assign the logic levels 

for particular operations. 

You can present your answer preferably in a table

a. Perform binary addition on given numbers:  20 1/16 and 71/4 .  

b. Convert the following binary number into ASCII code and then into its equivalent decimal representation. 01001001010000010100110101011100 

Differentiate between the followings with the help of examples:

(a) Deterministic and Stochastic Algorithms

(b) Local and Global optima.

Q1. Solve the following question to find best courses/payment using dynamic programming:

A graduate student may take any number of courses as a Teaching Assistant. There are five

courses and each associated with a payment. Each course has a number of hours needed and

the student is allowed to spend a maximum of 6 hours on TA duties. Find the best choice for

the grad student to maximize his/her income based on the following five courses specified as

(hours needed, payment received). -- (1,2, (4,5), (5,6) ), (2,3), (3,4)

Implement the following circuits using:

i. A decoder

ii. A multiplexer

(a) F(A, B, C, D) = ∑m (0, 1, 2, 3, 6, 10, 11, 14)

(b) A full subtractor

(c) A combinational circuit with 2 inputs: x, y, z; and 3 outputs A, B, C. When the binary input is 0, 

1, 2 and 3, the binary output is one greater than the input. When the binary input is 4, 5, 6, and 

7, the binary output is two less than the input.

NB: You may use a decoder or multiplexer of your choice, however, justify your choice clearly 

and in writing

Implement a combinational circuit for a Gray-to-Binary converter using 4-to-1 multiplexers and 

external gates

Calculate the time complexity of the following program fragments.

(a) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 ∗ = 2)

{

𝑥 = 𝑥 + 1

}

(b) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 + +)

𝑓𝑜𝑟 (𝑗 = 1; 𝑗 ≤ 𝑛; 𝑗 = 𝑗 ∗ 2)

{

… .

… .

}

1. Allow the user to input integers representing test scores until they enter -1. Store the values as an ArrayList of Integer values. Do not store the -1. Test score values may range between 0 and 100, inclusive. Your program should ignore any value that is outside of the range, and not add it to the ArrayList.
2. Output the list of values entered.
3. Sort the values, lowest to highest and output the sorted list.
4. Find and output the following:
5. average score
6. median score (For an ArrayList with an even number of cells, your program should output the average of the middle two elements. For an ArrayList with an odd number of cells, your program should output the element in the middle.)
7. range of scores (Find the minimum and maximum values in the list.  The range is calculated as: maximum value minus minimum value.)
8. Remove the minimum and maximum values. Output the resulting list.
9. Find and output the following (again):
10. average score
11. median score
12. range of scores

PRINT-OPTIMAL-PARENS(s, i, j){

if (i=j) then

print “A”i else{

print “(”

PRINT-OPTIMAL-PARENS(s,i,s[i, j])

PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)

print “)”} }

a- Test your algorithm for the following cases:

1. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<5,10,3, X,12,5,50, Y,6>.

2. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<5,10,50,6, X,15,40,18, Y,30,15, Z,3,12,5>.1

3. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<50,6, X,15,40,18, Y,5,10,3,12,5, Z,40,10,30,5>.

b- Find the complexity of your program

c- Show that the parenthesization algorithm is loop invariant.

X=10, Y=20, Z=30