All Matches

Solution Library

Expert Answer

Textbooks

Search Textbook questions, tutors and Books

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Tutors
Study Help
Ask a Question

Search
Sign In
Register

study help
computer science
introduction to algorithms

Questions and Answers of Introduction to Algorithms

Modify the PredatoryCreditCard class so that a customer is assigned a minimum monthly payment, as a percentage of the balance, and so that a late fee is assessed if the customer does not subsequently
Most modern Java compilers have optimizers that can detect simple cases when it is logically impossible for certain statements in a program to ever be executed. In such cases, the compiler warns the
Suppose you are on the design team for a new e-book reader. What are the primary classes and methods that the Java software for your reader will need? You should include an inheritance diagram for
Draw a class inheritance diagram for the following set of classes:• Class Goat extends Object and adds an instance variable tail and methods milk( ) and jump( ).• Class Pig extends Object and
Can two interfaces mutually extend each other? Why or why not?
Describe a component from a text-editor GUI and the methods that it encapsulates.
Give an example of a software application in which adaptability can mean the difference between a prolonged lifetime of sales and bankruptcy.
The birthday paradox says that the probability that two people in a room will have the same birthday is more than half, provided n, the number of people in the room, is more than 23. This property is
A common punishment for school children is to write out a sentence multiple times. Write a Java stand-alone program that will write out the following sentence one hundred times: “I will never spam
Write a Java programthat can simulate a simple calculator, using the Java console as the exclusive input and output device. That is, each input to the calculator, be it a number, like 12.34 or 1034,
Write a short Java program that takes all the lines input to standard input and writes them to standard output in reverse order. That is, each line is output in the correct order, but the ordering of
Write a Java method that takes an array containing the set of all integers in the range 1 to 52 and shuffles it into random order. Your method should output each possible order with equal probability.
Write a Java program that can take a positive integer greater than 2 as input and write out the number of times onemust repeatedly divide this number by 2 before getting a value less than 2.
Write a short program that takes as input three integers, a, b, and c, from the Java console and determines if they can be used in a correct arithmetic formula (in the given order), like “a+b =
Write a pseudocode description of a method for finding the smallest and largest numbers in an array of integers and compare that to a Java method that would do the same thing.
Write a Java class, Flower, that has three instance variables of type String, int, and float, which respectively represent the name of the flower, its number of petals, and price. Your class must
Write a short Java method that uses a StringBuilder instance to remove all the punctuation from a string s storing a sentence, for example, transforming the string "Let’s try, Mike!" to "Lets try
Write a short Java method, inputAllBaseTypes, that inputs a different value of each base type from the standard input device and prints it back to the standard output device.
A perfect matching is a matching in which every vertex is matched (Let G = (V, E) be an undirected bipartite graph with vertex partition V = L ? R, where |L| = |R|. For any X ? V, define the
Convert the following linear program into slack form: What are the basic and nonbasic variables? maximize 2x1 6x 3 subject to X1 + X2 X3 < 7 3x1 X2 8 -X1 + 2x2 + 2x3 X1, X2, X3 > 0. VI AL AL I | |
Solve the following linear program using SIMPLEX: maximize 18x1 + 12.5x2 subject to X1 + X2 < 20 X1 < 12 X2 < 16 X1, X2 0 .
Solve the following linear program using SIMPLEX: maximize X1 + 3x2 subject to X1 X2 8 -X1 X2 -X1 + 4x2 s 2 X1, X2 0 . 3. VI VI VI AI
Show that the following linear program is infeasible: maximize 3x1 2x2 subject to X1 + X2 2 -2x1 2x2 -10 X1, X2 VI VI AL
Write a linear program that, given a bipartite graph G = (V, E), solves the maximum-bipartite-matching problem.
Solve the following linear program using SIMPLEX: maximize 5x 3x2 subject to X1 X2 < 1 X2 < 2 > 0. 2x1 + X1, X2 |
Solve the following linear program using SIMPLEX: maximize X1 2x2 subject to 4 X1 + 2x2 -2x1 бх2 < -12 X2 1 0 . X1, X2 VI VI VI AI |
Show that the following linear program is unbounded: maximize X1 X2 subject to -2x1 + X2 < -1 -X1 2x2 < -2 X1, X2 0 .
In the minimum-cost multi-commodity-flow problem, we are given directed graph G = (V, E) in which each edge (u, ν) ∈ E has a nonnegative
Solve the following linear program using SIMPLEX: minimize subject to X1 + X2 + X3 2х1 + 7.5х2 + 3x3 > > 10000 20х1 + 5x2 + + 10хз > 30000 X1, X2, X3 0 .
Solve the following linear program using SIMPLEX: maximize X1 + 3x2 subject to -X1 + X2 < -1 -x1 X2 -3 -x1 + 4x2 X1, X2 VI VI VI I
Suppose that we have a general linear program with n variables and m constraints, and suppose that we convert it into standard form. Give an upper bound on the number of variables and constraints in
Give an example of a linear program for which the feasible region is not bounded, but the optimal objective value is finite.
Consider the following 1-variable linear program, which we call P: where r, s, and t are arbitrary real numbers. Let D be the dual of P. State for which values of r, s, and t you can assert that 1.
a. Show how to multiply two linear polynomials ax + b and cx + d using only three multiplications. One of the multiplications is (a + b) · (c + d).b. Give two divide-and-conquer algorithms for
Show how ITERATIVE-FFT computes the DFT of the input vector (0, 2, 3,−1, 4, 5, 7, 9).
Another way to evaluate a polynomial A(x) of degree-bound n at a given point x0 is to divide A(x) by the polynomial (x − x0), obtaining a quotient polynomial q(x) of
A Toeplitz matrix is an n × n matrix A = (aij) such that aij = ai-1.j-1 for i = 2, 3, . . . , n and j = 2, 3 , . . . , n.a. Is the sum of two
Compute the DFT of the vector (0, 1, 2, 3).
Show how to implement an FFT algorithm with the bit-reversal permutation occurring at the end, rather than at the beginning, of the computation.
Derive a point-value representation for Arev(x) = ∑n − 1j=0 an-1 j xj from a point value representation for A(x) = A
We can generalize the 1-dimensional discrete Fourier transform defined by equation (30.8) to d dimensions. The input is a d-dimensional array A = (aj1,j2,...,jd)?whose dimensions are?n1, n2, . . .
How many times does ITERATIVE-FFT compute twiddle factors in each stage? Rewrite ITERATIVE-FFT to compute twiddle factors only 2s-1 times in stage s.
Given a polynomial A(x) of degree-bound n, we define its t th derivative by From the coefficient representation (a0, a1, . . . , an-1) of A(x) and a given point x0, we wish to determine A(t)(x0)
Write pseudocode to compute DFT-1n in Θ(n lg n) time.
Suppose that the adders within the butterfly operations of the FFT circuit sometimes fail in such a manner that they always produce a zero output, independent of their inputs. Suppose that exactly
Describe the generalization of the FFT procedure to the case in which n is a power of 3. Give a recurrence for the running time, and solve the recurrence.
We have seen how to evaluate a polynomial of degree-bound n at a single point in O(n) time using Horner's rule. We have also discovered how to evaluate such a polynomial at all n complex roots of
Explain what is wrong with the “obvious” approach to polynomial division using a point-value representation, i.e., dividing the corresponding y values. Discuss separately the case in which the
Suppose that instead of performing an n-element FFT over the field of complex numbers (where n is even), we use the ring ℤm of integers modulo m, where m = 2tn/2
As defined, the discrete Fourier transform requires us to compute with complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to
Consider two sets A and B, each having n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B, defined by That the integers in C are in the range from 0 to 20n. We
Given a list of values z0, z1, . . . ,zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has
The chirp transform of a vector a = (a0, a1, . . . ,an-1) is the vector y= (y0, y1, . . . ,yn-1), where yk = Σn-1j=0?aj zkj and z is any complex number. The DFT is therefore a special case of the
Draw the group operation tables for the groups (ℤ4, + 4) and (ℤ*5, ·5). Show that these groups are isomorphic by exhibiting a one-to-one correspondence α between their elements such that a + b
Find all solutions to the equations x ≡ 4 (mod 5) and x ≡ 5 (mod 11).
Draw a table showing the order of every element in ℤ*11. Pick the smallest primitive root g and compute a table giving ind11.g (x) for all x ∈ ℤ*11.
Consider an RSA key set with p = 11, q = 29, n = 319, and e = 3. What value of d should be used in the secret key? What is the encryption of the message M = 100?
Prove that if an odd integer n > 1 is not a prime or a prime power, then there exists a nontrivial square root of 1 modulo n.
Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving more quickly than computing remainders. This problem investigates the
Prove that if a > b > 0 and c = a + b, then c mod a = b.
List all subgroups of ℤ9 and of ℤ*13.
Prove that the equation ax ≡ ay (mod n) implies x ≡ y (mod n) whenever gcd (a, n) = 1. Show that the condition gcd (a, n) = 1 is necessary by supplying a counterexample with gcd (a, n) > 1.
Find all integers x that leave remainders 1, 2, 3 when divided by 9, 8, 7 respectively.
Give a modular exponentiation algorithm that examines the bits of b from right to left instead of left to right.
It is possible to strengthen Euler's theorem slightly to the form λ(n) Icm (φ (p]), , φ(p")) . (31.42)
Suppose that we are given a function f . ℤn → ℤn and an initial value x0 ∈ ℤn. Define xi = f (xi-1) for i = 1, 2, ....
a. Consider the ordinary "paper and pencil" algorithm for long division: dividing a by b, which yields a quotient q and remainder r. Show that this method requires O((1 + lg q) lg b) bit
Prove that there are infinitely many primes. Show that none of the primes p1, p2, . . . ,pk divide (p1p2 ··· pk) + 1.
Prove that for all integers a, k, and n, gcd (a, n) = gcd (a + kn, n).
Assuming that you know Φ(n), explain how to compute a− 1 mod n for any a ∈ ℤ*n using the procedure MODULAR-EXPONENTIATION.
Prove that RSA is multiplicative in the sense that PA(M1) PA (M2) ≡ PA (M1M2) (mod n).Use this fact to prove that if an adversary had a procedure that could efficiently decrypt
Prove that if x is a nontrivial square root of 1, modulo n, then gcd (x –1, n) and gcd (x + 1, n) are both nontrivial divisors of n.
How many steps would you expect POLLARD-RHO to require to discover a factor of the form pe, where p is prime and e > 1?
Prove that if a | b and b | c, then a | c.
Rewrite EUCLID in an iterative form that uses only a constant amount of memory (that is, stores only a constant number of integer values).
Show that if p is prime and e is a positive integer, then Φ(pe) = pe – 1 (p – 1).
Let p be prime and f (x) ≡ f0 + f1x + ··· + ftxt (mod p) be a polynomial of degree t, with coefficients fi drawn from ℤp. We say
One disadvantage of POLLARD-RHO as written is that it requires one gcd computation for each step of the recurrence. Instead, we could batch the gcd computations by accumulating the product of
Let p be an odd prime. A number a ? Z*p is a?quadratic residue?if the equation?x2 =?a (mod?p)?has a solution for the unknown?x. a.?Show that there are exactly?(p???1)/2?quadratic residues,
Prove that if p is prime and 0 < k < p, then gcd(k, p) = 1.
If a > b ≥ 0, show that the call EUCLID (a, b) makes at most 1 + logΦ b recursive calls. Improve this bound to 1 + logΦ(b/ gcd(a, b)).
Show that for any integer n > 1 and for any a ∈ ℤ*n, the function fa : ℤ*n → ℤ*n defined by fa(x) = ax mod n is a permutation of ℤ*n.
Prove that if p is prime and 0 Conclude that for all integers a and b and all primes p, (a + b)' = a" + bP (mod p).
Define the gcd function for more than two arguments by the recursive equation gcd (a0, a1, . . . ,an) = gcd (a0, gcd (a1, a2, . . . ,an). Show that the gcd function
Define lcm (a1, a2, . . . ,an) to be the least common multiple of the n integers a1, a2, . . . ,an, that is, the smallest nonnegative integer that is a multiple of
For any integer k > 0, an integer n is a kth power if there exists an integer a such that ak = n. Furthermore, n > 1 is a nontrivial power if it is a kth power for some integer k > 1. Show
Prove that n1, n2, n3, and n4 are pairwise relatively prime if and only if gcd(n1n2, n3n4) = gcd (n1n3, n2n4) = 1. More generally, show that n1, n2, . . . ,nk are
Show that the gcd operator is associative. That is, prove that for all integers a, b, and c, gcd (a, gcd (b, c)) = gcd (gcd (a, b), c),
Give efficient algorithms for the operations of dividing a β-bit integer by a shorter integer and of taking the remainder of a β-bit integer when divided by a shorter integer. Your algorithms
Give an efficient algorithm to convert a given β-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most β takes time M(β),
Let yi denote the concatenation of string?y?with itself?i?times. For example,?(ab)3 =?ababab. We say that a string?x????* has?repetition factor?r?if?x?=?yr for some string?y????* and some?r > 0.
Show the comparisons the naive string matcher makes for the pattern P = 0001 in the text T = 000010001010001.
Working modulo q = 11, how many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when looking for the pattern P = 26?
How would you extend the Rabin-Karp method to the problem of searching a text string for an occurrence of any one of a given set of k patterns? Start by assuming that all k patterns have the same
Give an upper bound on the size of π*[q] as a function of q. Give an example to show that your bound is tight.
Suppose that pattern P and text T are randomly chosen strings of length m and n, respectively, from the d-ary alphabet ?d = {0, 1, . . . , d ? 1}, where d ? 2. Show that the expected number of
Show how to extend the Rabin-Karp method to handle the problem of looking for a given m × m pattern in an n × n array of characters. (The pattern may be shifted vertically and horizontally, but it
We call a pattern P nonoverlappable if Pk ⊐ Pq implies k = 0 or k = q. Describe the state-transition diagram of the string-matching automaton for a nonover lappable pattern.
Explain how to determine the occurrences of pattern P in the text T by examining the π function for the string PT (the string of length m + n that is the concatenation of P and T).
Suppose we allow the pattern P to contain occurrences of a gap character???that can match an arbitrary string of characters (even one of zero length). For example, the pattern ab???ba???c occurs in

Showing 400 - 500 of 1549

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Last

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Campus Ambassador

Company Info

Security
Copyrights
Privacy Policy
Terms & Condition
SolutionInn Fee
Scholarship

Services

Sitemap
Fun
Definitions
Become Tutor
Study Help Categories
Recent Questions
Expert Questions

Copyright © 2024 SolutionInn All Rights Reserved.

Get the SolutionInn - Study Help App