Key Concepts in Computer Science -Midterm 1

[Basic Mathematics]
1. [5 marks] Find the tightest integer upper bound and lower bound for x if 𝒙= 𝐋𝐨𝐠𝟐(𝟓𝟐). Justify your answer.
𝟑𝟐<𝟓𝟐< 𝟔𝟒 ⟹ 𝟐𝟓< 𝟓𝟐< 𝟐𝟔 ⟹ 𝐋𝐨𝐠𝟐(𝟐𝟓)< 𝐋𝐨𝐠𝟐(𝟓𝟐)< 𝐋𝐨𝐠𝟐(𝟐𝟔) ⟹
𝟓< 𝐋𝐨𝐠𝟐(𝟓𝟐)< 6 ⟹ 𝟓<𝒙 < 6
2. [5 marks] Simplify these expressions using the rules for logarithms. Your answer will be a simpler formula. You do not need to calculate a numeric answer:
a. 𝐋𝐨𝐠𝟑(𝟏𝟐𝟏𝟕) = 𝐋𝐨𝐠𝟑𝟏𝟐 − 𝐋𝐨𝐠𝟑𝟏𝟕
b. 𝐋𝐨𝐠𝟓(𝟑𝟒)=𝟒×𝐋𝐨𝐠𝟓(𝟑)
3. [5 marks] Solve this inequality 5 ≥ -10x + 20 and write it using interval notations for x.
5 ≥ -10x + 20 ⟹ -15 ≥ -10x ⟹ 𝟏𝟓𝟏𝟎 ≤ x ⟹ 𝟑𝟐 ≤ x ⟹ 1.5 ≤ x
x ∈ (-∞, 1.5)
4. [5 marks] Plot the two functions y=2x, y=2x + 2 on the same X-Y graph for {x | -2 ≤ x ≤ 2}.

[Pseudocode]
5. [10 marks] Write pseudocode for an algorithm to compute the sum of a list of integers but only for integers that are even.
Example: input: L = [4,2,1,3,6,8,7,9] output = 4 + 2 + 6 + 8 = 20
procedure sumOfEvenInt(L: list of integers)
n := sizeOf(L)
result := 0
for i := 1 to n
if L[i] is even then
result := result + L[i]
return result
Note: we are not picky about the syntax. Also, they might write the if line (to see whether L[i] is even or not) in different ways. As long as their intention is clear, they should get the mark.
[Propositional Logic]
6. [10 marks] Construct a truth table for the following compound proposition: ¬p ¬q

7. [10 marks] Let p be the proposition “You have a car”, q be the proposition “You miss the game” and r be the proposition “You play golf”. Express the following as an English sentence:
(p –> ¬r)  (q –> ¬r)
Answer: If you have a car, then you don’t play golf or if you miss the game, then you don’t play golf.
[Propositional Equivalences]
8. [10 marks] Use truth table to verify the following: p ^ (p v q)  p

Since the values of the last column are all TRUE, then the proposition is a tautology.
10. [10 marks] Give a proof that p ¬p  q) and p  q are logically equivalent.
Note: you cannot use truth table.
p ¬p  q) ≡
(p¬p)  (pq) ≡ Distributive laws (DIS)
T  (pq) ≡ Negation laws (NEG)
p q Identity laws (ID)

12. [10 marks] Consider the following propositional functions:
 Sheep(x): x is a sheep
 Gorilla(x): x is a gorilla
 Fed(x): x is fed after sunset
 Moon(x): x is exposed to moonlight
 Dies(x): x dies
write the following statements in predicate logic using the above propositional functions, connectives, negation, and any needed quantifiers.