Skip to main content

Semester Exam: Mathematical Foundations

Required Output Classification​

Required outputClassificationPublic/private guidance
Timed written answers, diagrams, code snippets, and design responsesCheckpoint evidenceKeep raw exam work private so it remains useful for assessment and retake calibration.
Post-exam review notes, missed-answer repairs, and Feynman explanationsPractice artifactUse for spaced review; publish only rewritten explanations that no longer reveal exam solutions wholesale.
Capstone-defense or architecture-defense packets created from exam promptsPortfolio candidatePolish publicly only when they are original to your project, sanitized, and framed as engineering rationale rather than exam answers.

Duration: 3 hours
Format: Comprehensive written exam with computational and proof components
Materials: Allowed: Calculator, one handwritten reference sheet (both sides)
Assessment: Tests understanding and application across all five modules

Exam Philosophy

This exam tests mathematical reasoning and problem-solving ability, not memorization. Problems are designed to require synthesis across modules and application of concepts to new situations. Focus on clear reasoning and systematic approaches rather than speed.

Exam Structure​

SectionQuestionsTimeWeightFocus
Part A: Foundations10 multiple choice30 min20%Core concepts and terminology
Part B: Computational8 problems90 min40%Calculations and algorithms
Part C: Proofs4 proofs60 min30%Mathematical reasoning
Part D: Integration1 synthesis problem30 min10%Cross-module connections

Part A: Foundations (Multiple Choice)​

Select the best answer for each question.

Question A1: Logical Reasoning​

Which statement is logically equivalent to "If it rains, then I carry an umbrella"?

a) If I carry an umbrella, then it rains
b) If I don't carry an umbrella, then it doesn't rain
c) If it doesn't rain, then I don't carry an umbrella
d) It rains if and only if I carry an umbrella

Answer: (b) - This is the contrapositive, which is logically equivalent to the original implication.

Question A2: Combinatorics​

How many ways can you arrange the letters in the word BANANA?

a) 720
b) 360
c) 60
d) 30

Answer: (c) - 6!/(3!×2!) = 720/12 = 60, accounting for repeated letters.

Question A3: Probability​

In a standard deck of cards, what is P(King | Face card)?

a) 4/52
b) 4/12
c) 1/3
d) 1/4

Answer: (c) - Given it's a face card, there are 12 face cards total, 4 of which are kings: 4/12 = 1/3.

Question A4: Linear Algebra​

If A is a 3×3 matrix with det(A) = 5, what is det(2A)?

a) 10
b) 25
c) 40
d) 125

Answer: (c) - det(kA) = k^n × det(A) for n×n matrix, so det(2A) = 2³ × 5 = 40.

Question A5: Graph Theory​

A tree with n vertices has exactly how many edges?

a) n
b) n-1
c) n+1
d) 2n-2

Answer: (b) - Trees are connected and acyclic, requiring exactly n-1 edges.

Question A6: Set Theory​

If |A| = 15, |B| = 20, and |A ∩ B| = 8, what is |A ∪ B|?

a) 35
b) 27
c) 23
d) 43

Answer: (b) - |A ∪ B| = |A| + |B| - |A ∩ B| = 15 + 20 - 8 = 27.

Question A7: Functions​

Which function f: ℝ -> ℝ is bijective?

a) f(x) = x²
b) f(x) = eˣ
c) f(x) = 2x + 3
d) f(x) = sin(x)

Answer: (c) - Linear functions f(x) = ax + b with a ≠ 0 are bijective on ℝ.

Question A8: Induction​

In a proof by strong induction, the inductive hypothesis assumes:

a) P(k) is true
b) P(1), P(2), ..., P(k) are all true
c) P(k+1) is true
d) P(k) implies P(k+1)

Answer: (b) - Strong induction assumes all previous cases up to k are true.

Question A9: Random Variables​

If X ~ Binomial(10, 0.3), what is E[X]?

a) 3
b) 2.1
c) 7
d) 1.8

Answer: (a) - E[X] = np = 10 × 0.3 = 3 for binomial distribution.

Question A10: Matrix Operations​

What is the rank of the matrix [[1,2,3],[2,4,6],[1,1,1]]?

a) 3
b) 2
c) 1
d) 0

Answer: (b) - Row 2 is twice row 1, so only 2 linearly independent rows.

Part B: Computational Problems​

Show all work. Partial credit given for correct methods.

Problem B1: Advanced Counting (Module 2)​

A computer science department has 12 faculty members and needs to form a curriculum committee of 4 people. Additionally, they need to select a chair and vice-chair from among these 4 committee members.

a) In how many ways can this be done?
b) What if the chair and vice-chair cannot be from the same research area, and there are 3 research areas with 4 faculty each?

Solution:
a) Choose 4 from 12, then arrange 2 of those 4: C(12,4) × P(4,2) = 495 × 12 = 5,940
b) More complex case analysis required based on research area constraints...

Problem B2: Probability Applications (Module 3)​

A hash table uses a hash function that distributes keys uniformly across 100 slots. If 20 keys are inserted:

a) What is the probability that slot #1 remains empty?
b) What is the expected number of empty slots?
c) Use normal approximation to estimate the probability that fewer than 15 slots remain empty.

Solution:
a) P(slot 1 empty) = (99/100)²⁰ ≈ 0.818
b) E[empty slots] = 100 × (99/100)²⁰ ≈ 81.8
c) Apply normal approximation to binomial...

Problem B3: Linear System Analysis (Module 4)​

Consider the system of equations:

x + 2y + 3z = 6
2x + 4y + az = b  
x + 2y + 2z = c

a) For what values of a and b does this system have infinitely many solutions?
b) For what values of a and b does this system have no solution?
c) When the system has a unique solution, express z in terms of the parameters.

Solution:
Requires row reduction and analysis of coefficient matrix augmented with constants...

Problem B4: Graph Theory Application (Module 2)​

A computer network has 8 nodes where each node must be connected to exactly 3 others for redundancy.

a) Is such a network possible? Explain using graph theory.
b) If possible, what is the minimum number of edges needed?
c) Design a specific network topology that satisfies these constraints.

Solution:
a) Check if 8 nodes with degree 3 each satisfies handshaking lemma...
b) Total edges = (8 × 3)/2 = 12
c) Construct specific 3-regular graph on 8 vertices...

Problem B5: Proof Strategy Selection (Module 1)​

For each statement, identify the most appropriate proof method and justify your choice:

a) "If n² is divisible by 4, then n is even"
b) "There are infinitely many prime numbers"
c) "For all positive integers n, 1 + 2 + ... + n = n(n+1)/2"
d) "√3 is irrational"

Solution:
Requires analysis of statement structure and strategic thinking about proof approaches...

Problem B6: Probabilistic Algorithm Analysis (Modules 1&3)​

Consider this randomized algorithm for finding the maximum element in an array:

  1. Randomly select k elements from the array of size n
  2. Return the maximum of these k elements

a) What is the probability that this algorithm returns the true maximum?
b) How should k be chosen to guarantee 95% success probability?
c) What is the expected number of comparisons made by this algorithm?

Solution:
Requires probability analysis of sampling without replacement...

Problem B7: Matrix Applications (Module 4)​

A Markov chain has transition matrix P = [[0.7, 0.3], [0.4, 0.6]].

a) Find the steady-state distribution (eigenvector with eigenvalue 1).
b) Starting from state [1, 0], what is the distribution after 3 steps?
c) How many steps are needed to get within 0.01 of the steady-state?

Solution:
Requires eigenvalue computation and matrix exponentiation...

Problem B8: Generating Functions (Module 2)​

Find the number of ways to distribute 10 identical balls into 4 distinct boxes such that each box contains at least 1 ball.

a) Set up the generating function equation.
b) Solve using stars and bars or inclusion-exclusion.
c) Verify your answer using a different counting method.

Solution:
Apply stars and bars with constraint handling...

Part C: Proof Problems​

Write complete, rigorous proofs. Focus on clarity and logical flow.

Problem C1: Set Theory Proof (Module 1)​

Statement: For any sets A, B, and C: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Proof Requirements:

  • Use element-chasing method (not Venn diagrams)
  • Show both subset directions
  • Justify each logical step clearly

Grading Rubric:

  • Set up and structure (5 points)
  • Logical reasoning (10 points)
  • Mathematical communication (5 points)

Problem C2: Induction Proof (Module 1)​

Statement: For all positive integers n ≥ 4: 2ⁿ > n²

Proof Requirements:

  • Clearly identify base case(s)
  • State inductive hypothesis precisely
  • Execute inductive step with complete algebraic reasoning
  • Address why the base case starts at n = 4

Grading Rubric:

  • Base case verification (5 points)
  • Inductive hypothesis statement (3 points)
  • Inductive step execution (10 points)
  • Overall structure and clarity (2 points)

Problem C3: Graph Theory Proof (Module 2)​

Statement: In any graph with n ≥ 2 vertices, if every vertex has degree at least n/2, then the graph is connected.

Proof Requirements:

  • Use proof by contradiction
  • Apply pigeonhole principle or counting arguments appropriately
  • Handle both even and odd n cases if necessary

Grading Rubric:

  • Contradiction setup (5 points)
  • Counting/pigeonhole application (10 points)
  • Logical conclusion (3 points)
  • Case analysis if needed (2 points)

Problem C4: Probability Theory Proof (Module 3)​

Statement: If X and Y are independent random variables, then Var(X + Y) = Var(X) + Var(Y).

Proof Requirements:

  • Start from definition of variance
  • Use linearity of expectation
  • Apply independence assumption clearly
  • Show all algebraic steps

Grading Rubric:

  • Definition application (5 points)
  • Independence usage (8 points)
  • Algebraic manipulation (5 points)
  • Final conclusion (2 points)

Part D: Integration Problem​

This problem requires synthesis across multiple modules.

Problem D1: Algorithm Design and Analysis​

You are designing a randomized algorithm to approximate the number of triangles in a large graph G with n vertices and m edges.

Algorithm Outline:

  1. Randomly sample k edges from the graph
  2. For each sampled edge (u,v), count common neighbors of u and v
  3. Use this to estimate total triangles in G

Requirements:
Your solution must address all of the following:

a) Combinatorial Analysis (Module 2):

  • How many possible triangles can exist in a graph with n vertices?
  • Given an edge (u,v), how do you count triangles containing this edge?
  • What is the relationship between edge sampling and triangle estimation?

b) Probability Theory (Module 3):

  • Model the sampling process: what is the probability that a specific triangle is detected?
  • Derive the expected value of your triangle count estimator
  • What is the variance of your estimator and how does it depend on k?

c) Linear Algebra (Module 4):

  • Express triangle counting using matrix operations on the adjacency matrix
  • How does the trace of A³ (where A is the adjacency matrix) relate to triangle counting?
  • Compare computational complexity of matrix-based vs. sampling-based approaches

d) Proof Techniques (Module 1):

  • Prove that your sampling estimator is unbiased
  • Under what conditions can you guarantee the approximation is within ε of the true count?
  • Prove a lower bound on the required sample size for given accuracy

e) Problem-Solving Integration (Module 5):

  • If your initial algorithm performs poorly, what modifications would you try?
  • How would you validate your algorithm's performance empirically?
  • What are the trade-offs between accuracy, runtime, and memory usage?

Grading Criteria:

  • Demonstrates understanding across all five modules (20 points)
  • Shows clear connections between mathematical concepts and algorithmic thinking (15 points)
  • Provides rigorous mathematical analysis where required (10 points)
  • Exhibits systematic problem-solving approach (5 points)

Answer Key Summary​

Part A: Multiple Choice​

  1. (b) 2. (c) 3. (c) 4. (c) 5. (b) 6. (b) 7. (c) 8. (b) 9. (a) 10. (b)

Part B: Computational​

Detailed solutions require multiple steps and proper mathematical reasoning. Key concepts tested include advanced counting, conditional probability, linear system analysis, graph properties, proof method selection, algorithm analysis, eigenvalue computation, and generating functions.

Part C: Proofs​

Each proof is graded on mathematical rigor, logical flow, and clear communication. Students must demonstrate mastery of proof techniques while explaining their reasoning clearly.

Part D: Integration​

The synthesis problem requires demonstrating connections between all five modules while maintaining mathematical rigor and showing practical algorithmic thinking.

Exam Preparation Guidelines​

Study Strategy​

  1. Review concept connections rather than isolated topics
  2. Practice explaining reasoning clearly in writing
  3. Work through integrated problems that span multiple modules
  4. Time management: Allocate time proportionally to point values
  5. Reference sheet: Include formulas, key theorems, and problem-solving strategies

Success Criteria​

  • Mathematical reasoning: Clear, logical, systematic approaches
  • Technical accuracy: Correct calculations and proper notation
  • Integration: Demonstrates connections between different mathematical areas
  • Communication: Explanations are clear and complete for intended audience

This exam validates readiness for advanced computer science coursework requiring mathematical maturity and systematic reasoning across multiple domains.

Added Written-Justification Prompts​

Use these as replacement or supplemental exam prompts when formula-only answers are too easy.

  1. Translate a requirement about users, roles, and permissions into predicate logic. State the domain, negate the requirement, and give one counterexample dataset that violates it.
  2. Prove or disprove: for all sets A, B, and C, A - (B union C) = (A - B) intersect (A - C).
  3. Count all 7-character codes made from uppercase letters and digits that contain at least one digit. Explain the complement you are counting.
  4. Use the pigeonhole principle to prove that in any group of 13 people, at least two were born in the same month. Then write one similar CS example involving hash buckets.
  5. Choose one problem-solving heuristic and apply it to a new algorithmic problem. Your answer must show the first failed or incomplete representation and the improved representation.

Mastery Rubric​

LevelEvidence
Beginner passCan answer direct questions and complete familiar exercises with light notes.
Solid passCan solve new variants, explain choices, and connect the work to Semester 0 Orientation.
Strong passCan defend tradeoffs, identify failure modes, and produce clean evidence in the portfolio artifact.
Not readyRelies on copied solutions, cannot explain mistakes, or lacks durable artifacts.

Retake and Repair Rule​

If a section is weak, do not only reread. Repair it by producing new evidence: a corrected solution, a fresh implementation, a rewritten proof, a benchmark, a diagram, a runbook, or a short teaching note.

Answer-Quality Examples​

Use these examples when grading written answers or spoken explanations.

QualityExample pattern
WeakNames a concept but gives no example, constraint, or failure case.
AcceptableDefines the concept and applies it to a familiar exercise.
StrongApplies the concept to a new variant and explains why an alternative would fail.
Portfolio-readyConnects the concept to Semester 0 Orientation, current project evidence, and a future capstone decision.

Interleaving Prompt​

For any missed answer, add one sentence starting with: This depends on an earlier skill because...​

Calibration Materials​

Use these learner-visible calibration materials before self-grading or requesting review: