PROJECTENGRAM

MOCK-MIDTERM-EXAM-02

Mock-Midterm-Exam-02

Tags: #◇Computer Science #◇CCDSALG #◇Mock-Midterm-Exam-02 #◇Conceptual

◇Overview

The second mock exam focuses heavily on algorithm analysis (frequency counting, explicit functions, and recurrence relations), determining the appropriate asymptotic notations (Big Oh, Omega, Theta), evaluating sorting algorithms (Bubble Sort, Selection Sort, Insertion Sort, Merge Sort), and converting expressions among infix, postfix, and prefix notations.

◇Important Formulas

Recurrences: Examples include T(n)=T(n−1)+3T(n) = T(n-1) + 3 and T(n)=2T(n/2)+5T(n) = 2T(n/2) + 5.
Logarithmic Time: Merge sort combines two sorted arrays in O(n)O(n) time, yielding an overall time complexity of O(nlog⁡2n)O(n \log_2 n).

◇Worked Examples

  1. Expression Conversion: Converting 9−2∗(5−4)/(−7∗(3−10))+89 - 2 * (5 - 4) / (-7 * (3 - 10)) + 8 to postfix and prefix.
  2. Queue and Stack Methods: Writing a function to copy a queue to a stack while retaining the queue's original contents.
  3. Code Behavior: Analyzing the effect of changing the condition from > to < in a Selection Sort implementation.

◇References & Navigation

CONFIRMATION // 理解度の確認

ACTIVE RECALL VERIFICATION

Select an answer to verify conceptual comprehension and reveal the technical rationale.

Q1

What is a key focus of Mock Midterm Exam 02 that differentiates it slightly from the first exam?

Q2

Which algorithmic notation is used to describe a tight bound on running time?

Q3

What time complexity does Merge Sort achieve by combining two sorted arrays in O(n)O(n) time?

Q4

What worked example is mentioned regarding expression conversion?