Finalcs202 (1)

CS202 Final Exam Overview

Course: CS202 Discrete Mathematics
University: New Jersey City University, William J. Maxwell College of Arts and Sciences
Instructor: Dr. Samia Alblwi
Date: December 18, 2023
Exam Structure: 10 pages, 11 questions

Truth Tables

Question 1

(a) Construct truth table for: (p ∨ q) ⇒ (p ⊕ q)
- p
  q
  p ∨ q
  p ⊕ q
  (p ∨ q) → (p ⊕ q)
  T
  T
  T
  F
  F
  T
  F
  T
  T
  T
  F
  T
  T
  T
  T
  F
  F
  F
  F
  T
(b) Construct truth table for: (p ∨ q) ⇒ (p ∧ q)
- p
  q
  p ∨ q
  p ∧ q
  (p ∨ q) → (p ∧ q)
  T
  T
  T
  T
  T
  T
  F
  T
  F
  F
  F
  T
  T
  F
  F
  F
  F
  F
  F
  T

Multiple Choice - Number Conversions

Question 2

Decimal for (1000000001)₂: (b) 513
Decimal for (11111)₂: (a) 31
Decimal for (701₈): (a) 359
Decimal for (2AE0B)₁₆: (c) 176511
Decimal for (E5)₁₆: (b) 229
Decimal for (11011)₂: (b) 27

Binary Operations

Question 3

7: Sum of (1000111)₂ and (1110111)₂: (a) 10111110
8: Product of (1000111)₂ and (1110111)₂: (b) 100001000001
9: Sum of (1010)₂ and (1001)₂: (a) 10011
10: Product of (1001)₂ and (101)₂: (b) 110101

Propositions and Negations

Question 4

Identify propositions and their truth values:
- (a) Not a proposition
- (b) Proposition: True if x + 2 = 11
- (c) Proposition: Truth depends on values of x and y
- (d) Not a proposition
- (e) Proposition: True (Washington, D.C. is the capital)
Negation Examples:
- (a) Vandana’s smartphone does not have at least 32 GB of memory.
- (b) Abby is not richer than Ricardo.
- (c) The summer in Maine is not hot and sunny.

Combinatorial Circuits

Question 5

5(a) Construct circuit for: (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r))
5(b) Construct circuit for: ((p ∧ ¬q) ∨ ¬r)

Mathematical Properties

Question 6

Summation Examples:
- (a) ( \sum_{j=0}^8 3 imes 2^j )
- (b) ( \sum_{j=2}^8 (-3)^j )
- (c) ( \sum_{k=1}^5 (k + 1) )
- (d) ( \sum_{j=1}^8 2^j )
Recurrence Relations:
- (a) ( a_n = 3a_{n-1}, a_0 = 2 )
- (b) ( a_n = a_{n-1} + 2, a_0 = 3 )

Advanced Questions

Question 7

Halt Problem: The question of determining whether a given program will finish running or continue indefinitely.
Time Complexity (arranged): 1, ( ext{lgn} ), n, ( n^2 ), ( 2^n ), ( n! )
Recursive Function: A function that calls itself in order to solve a problem.
GCD of (16, 32): 16
LCM of (12, 15, 20): 60
Algorithm for Maximum Integer: Iterate through the list and keep track of the largest number encountered.

Function Analysis

Question 8

Function Analysis Questions:
- (a) What type of function is this?
- (b) What is the image of a?
- (c) What is the image of d?
- (d) What is the preimage of 1?
- (e) What is the range of the function?

Mathematical Induction

Question 9

Prove that: ( 1 + 3 + 5 + ext{...} + (2n - 1) = n^2 )
- (a) Basic step
- (b) Inductive step
- (c) Complete proof

Extra Bonus Questions

Question 10

(a) Truth table for: p ↔ q
(b) Definition of palindrome and algorithm to determine if a string is a palindrome.
(c) Find product of matrices A and B given.
(d) Determine if BA = AB.