You've completed the last class of this course! The finals contest is on Saturday so here is some material to help review. Do as much as you think you need.

If you have forgotten anything, this website can help you review: http://www.categories.acsl.org/wiki/index.php?title=Main_Page.

Boolean Algebra:

Bit-String Flicking:

Let X = abcde. Solve the following bit string equation for X:

(LCIRC-3 (RSHIFT-1 X) OR 11010 AND NOT (RCIRC-2 10001)) = ((LSHIFT-2 10101) XOR 01110)

Solve for X (5-bits) in the following equation:

NOT X AND (LSHIFT-1(RCIRC-2 01011)) = 10000

What is the final value of X?

X = 11010011010

FOR k = 1 TO 71

X = (RCIRC-k X)

NEXT k

Recursive Functions:

Digital Electronics:

Prefix-Infix-Postfix:

Given the following operations: % means MOD (integer remainder) such

that 5%2 = 1 and \ means DIV (integer quotient) such that 5\3 = 1, evaluate

the following prefix expressions if A=5, B=12, C=8, and D=20. Note that all

numbers in the original expression are single digits.

/ - ^ \ * C - - D A B A \ ^ % + A C - D B 2 7 1 - B % B A

The trinary operator diff takes 3 arguments a, b, and c and returns the

maximum of abs(a-b), abs(b-c), and abs(a-c), where abs(x) is the absolute

value of x.

Evaluate the following prefix expression:

diff / 8 2 diff + 2 1 – 4 3 ↑ 2 3 * 2 3

Define the following unary operators as:

# = largest prime number less than a

& = smallest prime number greater than a

Evaluate the following prefix expression:

− / * + # 3 & 6 # 12 # 4 / / * 4 + / 6 # 3 & 2 # 3 & 2

Computer Number Systems:

Tickets for a concert were numbered from 1 16 to AA 16 . If when the ticket

number is converted to binary it contains the string “10101”, then the lucky

ticket holders will receive a Back Stage Pass for after the concert. How

many (one pass per winning ticket) passes were given out if the concert was

sold out?

The ACSL hardware engineers have recently developed a 5-bit memory

chip using radical new biotechnology. Unfortunately, the chip melts

whenever a value containing the pattern "101" appears within the 5 bits. Of

the 32 possible values that the chip can hold, how many will cause the chip

to melt?

How many of the binary representations of the numbers from 2

to 2047, inclusive, are palindromes? (Lead digit cannot be 0.)

What Does This Program Do?:

Data Structures:

Given the binary search tree for LOSANGELESCA, delete the root node.

List the nodes at depth 3 from left to right.

Using the ACSL definition, build a heap from the keys

N E W H A M P S H I R E (in that order).

List the nodes at depth 2, from left to right.

Given an initially empty stack and the string DISNEYWORLDORLANDOFLORIDA, perform the following: pop if it is a vowel and push if it is a consonant. If the next string added is a vowel, what item would be popped? Vowels are A, E, I, O, U.

Graph Theory:

In a directed graph, the paths represent streets from one intersection to

another. The intersections are: {A, B, C, D, E, F, G}. The streets are:

{AB, BF, EF, CD, ED, DC, EB, FA, GF, FE, BE, CE, GA, FG, AG, FB}.

A new one-way street was added from B to C and the two-way street

between F and G was closed due to non-use. What was the change in the

number of cycles from A between the first directed graph and the second one?

Answers:

Boolean Algebra:

ABC

(0, 0, 1), (1, 0, 0)

Bit-String Flicking:

*0*1* 0*1**

10101101001

Recursive Functions:

11

15

-15

Digital Electronics:

1

4

12

Prefix-Infix-Postfix:

6.3

3

29

Computer Number Systems:

15

11

93

What Does This Program Do?:

90

40

II,III,V

Data Structures:

E,O

H, H, M, P

F

Graph Theory:

2 fewer

0

11