CS 191 Tue Thu Fall 2018 HW 2 Due November 12

Cs 191 Tue Thr Fall 2018 Hw 2due Monday November 12 2018 By 1

Analyze and solve a series of theoretical and computational problems related to functions, number theory, algorithms, and data structures as specified below. Include proofs, algorithm descriptions, and calculations where appropriate.

Paper For Above instruction

The assignment comprises multiple questions that explore fundamental concepts in computer science, including properties of functions, number theory, algorithm analysis, and data manipulation. The questions require a mixture of theoretical proofs, algorithm design, and computational calculations, demanding both conceptual understanding and practical application skills.

Question 1: Sequence Analysis

Given the sequence \(a = 2n + 3^{n-1}\) for \(n \geq 3\), express the sum and product notations corresponding to this sequence. Clarify how the sum and product operate over the sequence elements.

Question 2: Function Properties and Inverse Computation

a) Determine whether the following functions are one-to-one (injective), onto (surjective), bijective, or none. Provide explanations for each:

  • i) \(f: \mathbb{R} \to \mathbb{R}\), with \(f(x) = 2x + 3\)
  • ii) \(g: \mathbb{N} \to \mathbb{N}\), with \(g(n) = 3n + 4\)
  • iii) \(h: \mathbb{Z} \to \mathbb{Z}\), with \(h(x) = x^3\)
  • iv) \(k: \mathbb{R} \to \mathbb{R}\), with \(k(x) = \sin x\)

b) For function ii), identify its domain, codomain, and range.

c) For \(f(x) = 4x^3 - 5\), with \(x \in \mathbb{R}\), find its inverse function \(f^{-1}(y)\).

Question 3: Composition of Functions

Given functions \(f(n) = 2n + 1\) and \(g(n) = 3n - 1\) from the positive integers to the positive integers, compute the compositions \(f \circ g\) and \(g \circ f\).

Question 4: Number Theory Proof (Proof by Cases)

Prove that if an integer \(n\) is not divisible by 3, then \(n^2 - 1\) is divisible by 3. Use proof by cases based on the possible remainders of \(n\) modulo 3.

Question 5: Logical Proof (Proof by Equivalence)

Prove that for any integer \(n\), \(n\) is odd if and only if \(n + 2\) is odd, employing a proof by logical equivalence.

Question 6: Mathematical Induction

a) Prove that \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\) for all \(n \geq 1\) using mathematical induction.

b) Prove that the sum of odd numbers \(3 + 5 + 7 + \dots + (2n + 1)\) equals \(n(n+2)\) for \(n \geq 1\).

Question 7: Algorithm Design and Analysis

a) Write the insertion sort algorithm and trace its execution on a provided input array, explaining each step.

b) Write a string search algorithm to find the word "amazing" in the text "Thisisanamazingassignment" and specify the output.

c) Write an algorithm to find the largest and second-largest values in a sequence \(a_1, a_2, \dots, a_n\), assuming \(n > 1\), and describe its logic.

Question 8: Algorithm Complexity and Asymptotic Analysis

a) Prove that \(n^3 + 2n + 5 = \Theta(n^3)\).

b) Prove that \(\sum_{k=1}^{n} k = \Theta(n^2)\).

Question 9: Function Growth Rate Analysis

Determine the asymptotic class (\(\Omega\), \(O\), \(\Theta\)) for each of the following functions, showing your reasoning:

  • a) \(T(n) = 12n^3 + 3n^2 + 4n\)
  • b) \(T(n) = 15 \log n + 4n + 6 n \log n\)
  • c) \(T(n) = 1 + 2 + 3 + \dots + n^3\)

Question 10: Loop Analysis in Algorithms

Analyze the number of executions of \(x = x + 1\) in the following code snippets, expressing the complexity in big-O notation:

  • a) i=1; x=0; while(i
  • b) x=0; for i=1 to n; for j=1 to n; x=x+1; for k=1 to n; x=x+1;

Question 11: Prime Factorization

Express the following integers as a product of primes:

  • i) 145
  • ii) 625

Question 12: GCD and LCM Calculation

Using prime factorization, find the GCD and LCM of the following pairs of numbers:

  • i) (65, 98)
  • ii) (789, 456)

Question 13 and 14: Number Base Conversions

Convert the following numbers to binary:

  • i) 756 in decimal
  • ii) AEF in hexadecimal

Convert the following numbers to hexadecimal:

  • i) 843 in decimal

Convert the following binary and hexadecimal numbers to decimal:

  • i) AE45 in hexadecimal

Perform binary and hexadecimal addition operations:

  • i) 6CB (hex) + ACD (hex)
  • ii) 3EA (hex) + B4FE (hex)
  • iii) 1011 (binary) + ETHC (hex)

References

  • Knuth, D. E. (1998). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
  • Ross, K. (2014). Discrete Mathematics and Its Applications. McGraw-Hill Education.
  • Rosen, K. H. (2012). Discrete Mathematics and Applications. McGraw Hill.
  • Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley.
  • Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach. Morgan Kaufmann.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-Wesley.
  • Levitin, A. (2012). Introduction to the Design & Analysis of Algorithms. Pearson.
  • Holzmann, G. J. (1997). The Verification and Validation of Computer-Modelled Systems. Springer.
  • Chapters and papers from ACM Digital Library and IEEE Xplore related to algorithm analysis and number theory.

Related Assignments