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