Exercise 3. Consider the following algorithms A and B for the problem of computing 2n (mod 317) (This is the modular exponentiation problem that we have discussed in class. Algorithm A is the one that we have seen in class, and algorithm B is a variant of it. Algorithm A. mod_exp_A (n) { }} if (n== 0) return 1; else { }} t = mod_exp_A (n/2); if (n is even) return t*t (mod 317); if (n is odd) return t*t*2 (mod 317); Algorithm B. mod_exp_B (n) { if (n== 0) return 1; else { if (n is even) return mod_exp_B (n/2) * mod_exp_B (n/2) (mod 317); if (n is odd) return mod_exp_B (n/2) * mod_exp_B (n/2) *2 (mod 317); 2

Exercise 3. Consider the following algorithms A and B for the problem of computing 2n (mod 317) (This is the modular exponentiation problem that we have discussed in class. Algorithm A is the one that we have seen in class, and algorithm B is a variant of it. Algorithm A. mod_exp_A (n) { }} if (n== 0) return 1; else { }} t = mod_exp_A (n/2); if (n is even) return tt (mod 317); if (n is odd) return tt2 (mod 317); Algorithm B. mod_exp_B (n) { if (n== 0) return 1; else { if (n is even) return mod_exp_B (n/2) mod_exp_B (n/2) (mod 317); if (n is odd) return mod_exp_B (n/2) * mod_exp_B (n/2) *2 (mod 317); 2

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Write a program that performs the following functionalities: 1. Fibonacci: a recursive function that…

A: Note: Due to company policies I am compelled to solve only one question and that is the first…

Q: a. What is the recurrence relation? b. Solve the recurrence relation from (a) in terms of n and show…

A: 1. Recurrence Relation can be defined as "an equation that recursively defines a progression or…

Q: Use java programming lanuage to explain if needed thanks

A: Given: Set S of n integer and another integer x. To find Two elements in S whose sum is exactly x.

Q: Given three sequences of length m, n, and p each, you are to design and analyze an algorithm to find…

A: Objective- Find the Longest Common Subsequence between three sequences(arrays or string) of given…

Q: Problem 4. We want to give our dog a collection of treats with total satisfaction value exactly…

A: Answer: We have done answer based on the given problem description. so from details we will see more…

Q: Match each of the following sequence with a corresponding recursive definition. ? ✓1. an = 6n for n…

A: Solution:

Q: Alert dont submit AI generated answer. Consider the following implementation of function…

A: a) The given implementation is not tail-recursive because the recursive call to `multiply` is…

Q: Reversing an Array 1. Describe the definition of recursive function. oBase case(s) oRecursive…

A: Given,Reversing an Array1. Describe the definition of recursive function.oBase case(s)oRecursive…

Q: Computer Science Provide a recursive definition for the following set S. ?={2k3m5n ∈ ? | ?, ?, ? ∈…

A: Given :- Provide a recursive definition for thefollowing set S.S={2k3m5n E N | k, m, n E Z+}Z+ is…

Q: Let A[1...n,1...n] be a 2D array of positive integers with n rows and n columns. Let…

A: Answer :

Q: What is the time complexity of a recursive program whose recurrence relation is as given below?…

A: Master’s Theorem is a popular method for solving the recurrence relations. Master’s theorem solves…

Q: explain l

A: The question is asking to determine the time complexity of a given function that uses both iteration…

Q: 1: |R|←|P| Reserve space for |P| = 13 values. 2: x ← n 3: for i ← 0 ...(|P| − 1) do 4: c ← x div…

A: A Java programmer could implement Algorithm by first modelling the primitive numbers with the…

Q: 3. Linear time algorithm for selection problem, given n numbers, find the k'th largest in linear…

A: (Using Quick Sort partitioning algorithm): Choose a pivot number. if K is lesser than the…

Q: #include using namespace std; int genFibonacci(int n) { int fibo[n+2]; fibo [0] = 0; fibo[1] = 1;…

A: - We need to explain the question provided regarding dynamic programming.

Q: 1. depends on pseudo code described algorithm below find primes up to N in java rogramming language.

A: Code: import java.util.Arrays;public class FindPrimes { public static void printPrimeUpto(int N){…

Q: Python Lee has discovered what he thinks is a clever recursive strategy for printing the elements…

A: def printAll(seq): print ('printAll(%s)' % seq) #for tracing arguments if seq: print(seq[0])…

Q: For this computer algorithms problem, you are given an N amount of cents, Then you are being asked…

A: Pseudocode: A pseudocode is a plain language description of the steps in an algorithm or another…

Q: The Lucas numbers are a series of numbers where the first two Lucas numbers (i.e., at indices 0 and…

A: The Lucas numbers are a series of numbers where the first two Lucas numbers (i.e., at indices 0 and…

Q: Given a sorted array of integers, write a program to implement the Binary Search Algorithm and find…

A: An effective searching algorithm that use sorted arrays is the binary search algorithm. In each…

Q: 8- Determine if each of the following recursive definition is a valid recursive definition of a…

A: Recursive Function: In mathematics and computer science, a recursive function is one that defines…

Q: This is a MATLAB Coding problem: Implement a recursive function, called count, that takes two…

A: Code: function index=count(A,b) %defining the function n=numel(A); %determining the size of array…

Q: Write a recursive function to determine if an array of integers contains any even numbers: bool…

A: A function is defined as a block of code that is will execute the code statements when the name of…

Q: Let recursive algorithm F be defined as follows: F(int n): if n=1 then return 1 else return…

A: - According to the guidelines we are allowed to answer only the first question. - The given…

Concept explainers

Computational Systems

The computation systems can be defined as the systems that are capable of solving a problem that includes calculations either mathematical or logical, and are able to produce the result as an output. For example, a simple calculator that is given a set of numbers and operators as input and produces the result as an output can be defined as a computational system. The above example is a simple illustration only, the computational systems range from simple devices to complex devices such as the systems that control the SpaceX companies, Starlink satellites which are being quite recently seen in the skies at many places globally.

Question

**Exercise 3.**

Consider the following algorithms A and B for the problem of computing \(2^n \mod 317\). (This is the modular exponentiation problem that we have discussed in class. Algorithm A is the one that we have seen in class, and algorithm B is a variant of it.)

**Algorithm A.**

```plaintext
mod_exp_A(n) {
if (n == 0) return 1;
else {
t = mod_exp_A(n/2);
if (n is even) return t * t (mod 317);
if (n is odd) return t * t * 2 (mod 317);
}
}
```

**Algorithm B.**

```plaintext
mod_exp_B(n) {
if (n == 0) return 1;
else {
if (n is even) return mod_exp_B(n/2) * mod_exp_B(n/2) (mod 317);
if (n is odd) return mod_exp_B(n/2) * mod_exp_B(n/2) * 2 (mod 317);
}
}
```

1. Write the recurrence for the runtime \( T_A(n) \) of algorithm A, and solve the recurrence to find a \(\Theta(\cdot)\) estimation of \( T_A(n) \).

2. Write the recurrence for the runtime \( T_B(n) \) of algorithm B, and solve the recurrence to find a \(\Theta(\cdot)\) estimation of \( T_B(n) \).

3. Which algorithm is faster? (Note: There is a huge difference between \( T_A \) and \( T_B \).)

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Step 3

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Using recursion, write a Python function def before(k,A) which takes an integer k and an array A of integers as inputs and returns a new array consisting of all the integers in A which come before the last occurrence of k in A, in the same order they are in A. For example, if A is [1,2,3,6,7,2,3,4] then before(3,A) will return [1,2,3,6,7,2]. If k does not occur in A, the function should return None.
Consider a recursive function, called f, that computes powers of 3 using only the + operator. Assume n > = 0. int f(int n) { if (n == 0) return 1; return f(n-1) + f(n-1) + f(n-1); } Give an optimized version of f, called g, where we save the result of the recursive call to a temporary variable t, then return t+t+t. i got int g(int n) { if (n == 0) return 1; int t = g(n - 1); return t+t+t; } so now Write a recurrence relation for T(n), the number addition operations performed by g(n) in terms of n.
Give a recursive definition for the set of all strings of a’s and b’s that begins with an a and ends in a b. Say, S = { ab, aab, abb, aaab, aabb, abbb, abab..} Let S be the set of all strings of a’s and b’s that begins with a and ends in a b. The recursive definition is as follows – Base:... Recursion: If u ∈ S, then... Restriction: There are no elements of S other than those obtained from the base and recursion of S.
Question 4
write java codes to do the following: Write a recursive function to check if an integer array is negative symmetric, for example, an array of 10, 20, 30, 90, -30, -20, -10 is considered as negative symmetric, while an array of 10, 20, 30, 90, 30, 20, 10 is not considered as negative symmetric. public static boolean checkArraySym(int [ ] A, int first, int last) that receives an array A, first index, last index and checks if the array is negative symmetric