100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
CSC 349 Algorithms & Definitions Questions and Answers $12.49   Add to cart

Exam (elaborations)

CSC 349 Algorithms & Definitions Questions and Answers

 7 views  0 purchase
  • Course
  • CSC - Cyber Secure Coder
  • Institution
  • CSC - Cyber Secure Coder

CSC 349 Algorithms & Definitions Questions and Answers Big O Notation An analysis / upper bound on the running time of an algorithm. slowest to fastest: O(1) O(log n) O(n^c) (where 0<c<1) O(n) O (n * log n) O(n^2) O(n^c) (where c > 1) O(c ^ n) O(n!) O(n^n) Rank the fo...

[Show more]

Preview 3 out of 22  pages

  • September 22, 2024
  • 22
  • 2024/2025
  • Exam (elaborations)
  • Questions & answers
  • CSC - Cyber Secure Coder
  • CSC - Cyber Secure Coder
avatar-seller
Pogba119
CSC 349 Algorithms & Definitions
Questions and Answers
Big O Notation - answer An analysis / upper bound on the running time of an
algorithm.

slowest to fastest:
O(1)
O(log n)
O(n^c) (where 0<c<1)
O(n)
O (n * log n)
O(n^2)
O(n^c) (where c > 1)
O(c ^ n)
O(n!)
O(n^n)

Rank the following running times in order from fastest to slowest:

17n, n^3, 2^n, n!, 36, log b (n), 48 n log b (n), 367 n^2 log b (n), n^n - answer 36, log
b (n), 17n, 48 n log b (n), 367 n^2 log b (n), n^3, 2^n, n!, n^n

T(n) = T(n/2) + O(n) - answer O(n)

n + n/2 + n/4 + ... +n/n
n * (1 + 1/2 + 1/4 + ... + 1/n)
<= O(2n)
= O(n)

T(n) = T(n/2) + O(n^2) - answer O(n^2)

n^2 + (n/2)^2 + (n/4)^2 + ... + (n^2 / n ^ 2)
n^2 * ( 1 + 1/4 + 1/16 + ... + 1/n^2)
<= O(4/3 * n^2)
= O(n^2)

T(n) = 3T(n/3) + O(1) - answer O(n)

1 + 3 + 9 + ... + n/3 + n
n/n + n/(n/3) + n/(n/9) + ... + n/3 + n
n * (1/n + 1/(n/3) + ... + 1/3 + 1)
<= O(3 * n)

,= O (n)

T(n) = T(n/3) + O(n) - answer O(n)

n + n/3 + n/6 + ... + 1
n + n/3 + n/6 + ... + n/n
n * (1 + 1/3 + 1/6 + ... + 1/n)
<= O(3 * n)
= O(n)

If X and Y are n x n matrices and
X = [ A B, C D]
Y = [ E F, G H]

Prove the product property that XY can be expressed as - answer Subdivide X into a
(1, 1) - (n/2, n/2) elements in the top right, b (1, n/2 + 1) -(n/2, n) elements in the top left,
c (n/2 + 1, 1) - (n, n/2) elements in the bottom left, and d (n/2 + 1, n/2 + 1) -(n, n) in the
bottom right, and do the same for Y with e, f, g, and h respectively. Then combine the
two using the dot product and show each subdivision = its product (i.e. top left = AE +
BG but with elements)

Design and analyze a divide and conquer algorithm for an index search whether there
exists an index i such that ai = i in a sorted list - answer --IndexSearch--
Input: A sorted list of distinct integers A {a1, a2, a3, ..., an}, and integers min and max.
(min = 0 and max = n - 1)
Output: A truth value depending on whether there exists an index i such that ai = i

1: i = floor((max + min) / 2)
2: if i = max and i = min and i != ai:
return False
3: else:
4: if i = ai:
return True
5: else if i < ai:
return IndexSearch(A, min, i - 1)
6: else:
return IndexSearch(A, i + 1, max)

Lemma: If there is no such i then IndexSearch returns false.

Proof by contradiction: Suppose there is no such i and that IndexSearch returns
something other than -1. Only way to return something that is not -1 is if there exists
such an i. Thus, our contradiction.

Lemma: If there exists such an i and max - min = n, then IndexSearch returns true.

, Proof by induction:

Base Case: Suppose that there exists such an i and max - min = 0. Then max = min = i
= floor((max + min) / 2). Line 4 of IndexSearch returns True

Inductive Hypothesis: If there exists an i and max - min <= k, then IndexSearch returns
True

Inductive Step: Suppose that there exists an i and max - min = k + 1
1. i < A[midpoint]
2. i > A[midpoint]
3. i = A[midpoint]

Case 1: There exists such an i in A(min, midpoint - 1) since the list is sorted and
(midpoint - 1) - min <= k, so the inductive hypothesis is met and Line 5 of IndexSearch
returns True

Case 2: Symmetrical to Case 1

Case 3: On Line 6, IndexSearch returns True if i = A[midpoint]

Design and analyze a divide and conquer algorithm that finds the heavy marble out of
3^n marbles using the balancing scale at most n times - answer --MarbleSearch--
Input: A set of marbles M that weigh identically except for one heavier marble and a
balancing scale function BalancingScale() that compares weights
Output: The heavy marble

1. if set = one marble:
return marble
2: Let the set of marbles be divided equally into 3 subsets named first, second and third.
3: if BalancingScale(first) > BalancingScale(second) and BalancingScale(first) >
BalancingScale(third):
MarbleSearch(first)
4: else if BalancingScale(second) > BalancingScale(first) and BalancingScale(second) >
BalancingScale(third):
MarbleSearch(second)
5: else:
MarbleSearch(third)

Design and analyze a divide and conquer algorithm that counts the number of
occurrences of x in a sorted list - answer --IntegerCount--
Input: An integer x, and a sorted list of integers A {a1, a2, ... an}
Output: The number of occurrences of x in the list

1: midpoint = floor((max + min) / 2)
2: if x = A[min] and x = A[max]:

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Pogba119. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $12.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

81531 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$12.49
  • (0)
  Add to cart