Algorithms Answers

1.

Derive the best and worst-case time complexity for the following algorithm and express it in O notation. (Here max and min functions assume their usual meaning.)

1.

myFunction(A[ ]) {

2.

n = A.length

3.

v = n

4.

for i = 1 to n {

5.

v = min(A[i], v)

}

6.

v = max(1, n)

7.

for j = 1 to 100 {

8.

sum = 0

9.

k = 1

10.

while k <= v {

11.

sum = sum + A[k]

12.

k = k*2

}

}

}

Hints: Find out the greatest and smallest possible value for v, and use it in your analysis.

In a microcomputer, the addresses of memory locations are binary numbers that identify each memory circuit where a byte is stored. The number of bits that make up an address depends on how many memory locations there are. Since the number of bits can be very large, the addresses are often specified in hex instead of binary. i. If a microcomputer uses a 20-bit address, how many different memory locations are there? ii. How many hex digits are needed to represent the address of a memory location there? iii. What is the hex address of the 255th memory location? (Note: The first address is always 0) iv. The computer program is stored in the lowest 2kbyte block of memory. Give the start and end address of this block.

 A 8 Megapixel digital camera stores an eight-bit number for the brightness of each of the primary colours (red, green, blue) found in each picture element (pixel). If every bit is stored (no data compression), how many pictures can be stored on a 256 Megabyte memory card. 

 A computer uses a memory unit with 256k words of 32 bits each. A binary instruction code is stored in one word of memory. The instruction has four parts, an indirect bit, an operation code, a register code part to specify one of 64 registers, and an address part i. How many bits are there in the operation code, the register code part, and the address ii. Draw the instruction word format and indicate the number of bits in each part. iii. How many bits are there in the data and address inputs of the memory? 

For a car ignition to be turned on: (i) the driver must be in the car having all the doors locked having the gear in parking or neutral state, or (ii) the car can be put on using a remote starter from outside without the driver in the car, but all the car doors must be locked with hand brake on and gear in parking state or neutral. Any deviations from these two conditions will set the car security alarm on. i. What are the variables to be used in representing the states? ii. Design a logic circuit for the scenario iii. Modify the design to set the car alarm on for a second after the ignition must have been on for five minutes provided the doors, gear and handbrake are at the initial state and then off the ignition if the states remain the same after the last second. 

2.Find the regular expression defining each of the following language over E=[a,b].

i. All strings that do not end in a double letters.

ii. all strings in which letter never triples

iii. All strings in which 'a' is triple or 'b' is triple.

consider the following quadratic equation: 2x^2-40x+150=0. a trusted mathematician tells us that the roots for this equation are 15 and 75. however, when you try to solve it, the roots turns out to be 15 and 5. explain why 75 could be a solution while 5 is not

int main()

{

double disc;

double item1 = 201.99;

double item2 = 20.56;

string message;

disc = calcDisc(item1, item2);

message = calcDisc();

return 0;

}

The two function calls will ... ?

By using single layer perceptron algorithm classify the following patterns. Where X1 and X2

are inputs Y is the output. Learning rate is 0.5 , output is 1 if weighted sum >=0.5 otherwise

0 and weights w1 =0.2 and w2 = 0.3 [5]

X1 X2 Y

0 0 0

0 1 1

1 0 1

1 1 1

1. There are huge secondary or standard datasets published in the internet for such case studies:

·        Case 1: Texts categorization in any dominoes.

·        Case 2: Images (detection/or recognition) in any dominoes.

·        Case 3: Signals classification in any dominoes.

Find ONE (1) of the secondary datasets from the internet. Name the secondary dataset that you have found.