5 basic intro level cpu science questions.

Q1. Design an algorithm which gets as input a list of k integer values N1, N2, ……,

Nk as well as a special value SUM. Your algorithm must locate a pair of values in

the list N that sum to the value SUM. (10 points)

For example, if your list of values is 3, 8, 13, 2, 17, 18, 10, and the value of SUM is

20, then your algorithm would output either the two values (2, 18) or (3, 17). If

your algorithm cannot find any pair of values that sum to the value SUM, then it

should print out the message ‘Sorry, there is no such pair of values.

Work out your algorithm to verify that it will work correctly for the given list and

SUM in example. (10 points)

Q2. For a shuffle-left algorithm, the best case occurs when the list has no 0 values

and worst case occurs when the list has all 0 values. Prove this by taking a two

lists of your choice where one is for best case and one for worst case. Show all

the comparisons and copies in each step to prove the given statement of best

and worst case. Do not write only the points given by the book. Show the

workout to show the reasons. (15)

Q3. Below is the algorithm for Bubble Sort.

1. Get values for n and the n list items

2. Set the marker U for the unsorted section at the end of the list

3. While the unsorted section has more than one element

do steps 4 through 8

4. Set the current element marker C at the second element of the list

5. While C is has not passed U, do steps 6 and 7

6. If the item at position C is less than the item to its left then

exchange these two items

7. Move C to the right one position

8. Move U left one position

9. Stop

a) Using the bubble-sort algorithm, for each of the following lists, perform

sorting, and show the list after each exchange. (5+5 points)

i) 4, 8, 2, 6 ii)

D, B, G, F, A, C,

E

b) Explain and prove why the bubble sort algorithm above does Θ(n2)

comparisons on an n-element list. (20 points)

Q4) Design a circuit that has three inputs and one output. The circuit outputs a 1

if and only if an even number (0 or 2) of its inputs are a 1. Otherwise, the circuit

outputs a 0. (Odd – parity circuit)

Draw the truth table, Boolean expression for the table and then the Boolean

circuit. (15)

Q5) Draw a circuit containing Row decoder, Column decoder and two

dimensional memory organization as shown in figure below :

MAR should be of 4 bits. In your figure write the values in each part. Label each

lines properly with the correct binary values. All the components must have their

correct values (not general values as N) as shown in figure above. (20 points)

Q6) Write an assembly language program which receives a list of numbers as

input (N) and separately computes and prints the sum of all positive numbers and

all negative numbers and stops when it sees the value 0. For example, given the

input 12, –2, 14, 1, –7, 0 your program should output the two values 27 (the sum

of the three positive values 12, 14, and 1) and –9 (the sum of the two negative

numbers –2 and –7) and then halt. (20 points) (For reference see figure 6.8)