Algorithm Definition and 651 Threads

I have a question about HHL algorithm https://arxiv.org/pdf/0811.3171.pdf for solving linear equations of the form: A x = b Where A, x and b are matrices Take for example 4x1 + 2x2 =14 5x1 + 3x2 = 19 HHL apply the momentum operator eiAτto/T on the state, do a Fourier Transform on |b> and...

Following these links: https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf https://www.codeproject.com/Articles/1131573/Grovers-Search-Algorithm-explained I have these questions: The Oracle "knows" the correct bits in the first invocation itself. So why do sqrt(N) invocations where...

Homework Statement Let a, b be natural numbers then there exists a unique pair (q,r) that are elements of the non-negative integers such that b=aq+r and 0 is less than or equal to r which is less than a I have a question regarding the existence part of the proof, now if I assumed a is less...

I need to write a code to calculate the trajectory of the particle under lorentz force.Since the position depended equations are hard to solve I ll use a code, how can I appraoch this problem. I should use veloctiy-verlet algorithm or any suggestions ? You should consider that lorentz force is a...

A theorem states: Any finite set of natural numbers is effectively decidable. I understand the construction of the (brute force) algorithm to check every input for inclusion in the set. However, if the input is not included in the set, the algorithm would not terminate, and we require...

If we define our polygons as a collection of lines, then each polygon has slopes $\vec{m}$ and y-intercepts $\vec{c}$. For a single line in the plane $y = ax + b$ amounts to finding $x = \dfrac{b - \vec{c}}{\vec{m} - a}$, which is fine. But then we need to sift through the solution vector $x$...

1. The problem statement, all variables, and given/known data Create algorithm steps that for a given number (N) is prime or not Homework Equations 3. The Attempt at a Solution I am trying to create an algorithm but I am stuck at some place. Here is my trying. 1-Input a...

What I have is /// <summary> /// Provides a solution to the Common Child string problem /// https://www.hackerrank.com/challenges/common-child/problem /// </summary> public static class CommonChild { public static int Solve(string first, string second)...

Hi! (Not sure which forum to pick for this question. This looked like the best one. I apologies if it is not) I have a number of functions (say m functions) with integer domain. All functions are increasing. (Increasing in the sense not decreasing, $f(n+1) \ge f(n)$.) I want an algorithm to...

Suppose an array of booleans with an even number of true values. I need an algorithm that, given an address containing a true (say, 3), returns the address of another true (say, 25), such that if I call the algorithm for 25, it returns 3. No storage of old choices are allowed since this...

Hi, I was wondering (and I am somewhat non-confident about my time measurement)... if I have an object that has several numbers (associated with each event): A = (A_0, A_1, A_2,...,A_{N-1})... what's the best way to find if there are duplicates in them? At first I thought the simplest piece of...

Homework Statement Let a be an integer and n be a non-negative integer. Without changing the values of a and n, produce an algorithm, of O(log n) complexity, which computes a^n. Homework Equations For integers a, n and i, where n >= 0 and is even, where i >= 1 and where a has no further...

Due to required reversibility, classical function (f(a)=y^a \mod N) in Shor's algorithm needs a lot of auxiliary qubits. I was afraid that their later treatment might influence the computation - and just got confirmation from Peter Shor himself: that we need to "uncompute" these auxiliary...

Hi everybody, I'm writing some algebra classes in C++ , Now I'm implementing the modified sparse row matrix , I wrote all most all of the class, but I didn't find the way saving computing time to perform the product of two Modified sparse row matrix .. if you don't know it you can read in the...

Hello! (Wave) The following algorithm is given: And it says the following: First of all, at the first line do they mean that the content of j is i? About the second line, why don't we subtract the polynomial $f[i] \cdot u \cdot h \cdot X^i $ from $(f[0], \dots, f[d'])$? Is there then...

Homework Statement Give an algorithm for computing the depths of all the nodes of a tree T, where n is the number of nodes of T. a) What is the complexity of your algorithm in terms of Big-O? b) What is the best possible complexity that you believe can be achieved when solving such problem...

In the SPP part of my networks textbook, it refers to Bellman's algorithm but also at times Bellman-Ford's algorithm, is there a difference between the two or is that just the writers of the textbook not being consistent with what they call it?

In this video the solution is: A→B→D→F but the paths A→B→D and A→E→D both have a distance of 9, so when you get to D you can either have [B,9] or [E,9] where the first entry is the predecessor and the second entry is the 'cost' on that path so far, or here the distance. is the solution A→E→D→F...

Homework Statement I found this algorithm online for computing ln(x). I use the babylonians method for computing square root if it is relevant. fun naturalLog(desired: Double): Double { var naturalLog = desired // desired = x for(number in 0..9) { naturalLog =...

Hello to everyone who's reading this. The problem that I'm struggling with, and it's solution, are typed below.: Homework Statement PROBLEM STATEMENT: Assume an array [0, ... n - 1] of int, and assume the following code segment: for (int i = 0; i < n - 1; i++) if(a[i] > a[i+1])...

Hi everyone! This is an application question. I would like to get some advice about how to calculate a score based on a set of individual scores in a way that makes most sense. CONTEXT: I am going over some criteria for judging usability of hypotheses. I came up with a whole bunch about a...

Hello! (Wave) I am looking at the following exercise: Let $b=r_0, r_1, r_2, \dots$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. Show that after every two steps, the remainder is reduced by at least one half. In other words, verify that $$r_{i+2}< \frac{1}{2}...

Homework Statement please see the image Homework Equations I'm not sure if this is relevant: ##r_2 \leq \frac{1}{2}r_1## ... ##r_n \leq (\frac{1}{2})^nr_1## The Attempt at a Solution i have shown that ##r_{i+2} < r_i## by showing the ##r_{i+2} - r_i## is negative, but how do I show that the...

I'm trying to find an algorithm for extending an arm as close as possible to an object. There's two bones the upper arm bone and the lower arm bone, and three points : shoulder , elbow, hand How can I figure out the closest possible configuration towards a fourth point which is the object it's...

Shor's algorithm is rather the most interesting quantum algorithm as it shifts a problem which is believed to need exponential classical time, to polynomial time for quantum computer, additionally endangering asymmetric encryption like RSA and ECC. The real question is if there are other...

Homework Statement I'm just trying to do homework problems involving the Regula Falsi numerical method, and the solutions in my books seem to have a lot of mistakes, so I was hoping I could make a program to generate solutions for myself, so that I could check if I'm doing things correctly when...

Homework Statement Imagine you are playing a game with me, of drawing balls from a box. There are two blue balls and two red balls. They are picked with equal probability, and are drawn without replacement. If you draw a blue ball, I give you $1. If you draw a red ball, you pay me $1.25. What...

Hi We have a family game when we are stuck in traffic similar to https://en.wikipedia.org/wiki/Countdown_(game_show) (I know I am a nerd ) In the game we are looking at license plate of the car in front and trying to get 120 using the 4 arithmetic operators (+-*/) and the numbers in the license...

Homework Statement Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum. sum_pairs([11, 3, 7, 5], 10) # ^--^ 3 + 7 = 10 == [3, 7] sum_pairs([4, 3, 2, 3, 4]...

Hi there. I was trying to solve the time dependent diffusion equation in only one dimension. I derived a explicit scheme using a finite difference in the time variable. The equation I am trying to solve is: ##\displaystyle \frac{1}{c} \frac{\partial \phi(x,t)}{\partial t} -...

I'm trying to solve a problem that amounts to: Given b0, ..., bn-1 where1 <= bi, find the max of |a0 - a1| + |a1 - a2| + ... + |an-2 - an-1| where 1 <= ai <= bi. I'm 100% confident that each ai is either 1 or bi. I'm 90% confident that the elements a0, ..., an-1 are either 1, b0, 1, b1...

Hello! So I'm working to try to understand shor algorithm and I have some doubts. So, after the hadamard gates we apply the unitary gate that construct the function yk mod N. Next we do a measurement in the second register to get some function value. So, when I do this measurement on the...

Long-story short, as part of a larger problem I'm trying to solve, I need all i,j>=0 such that i*j=k2 for all k in [1, ..., n]. What I'm doing currently is iterating through [12, 22, ..., n2] and for each value m I'm using public static IEnumerable<Tuple<int, int>> Multipliers(ulong...

Hello everyone! So I was looking at Shor Algorithm for prime factorization and I have some doubts in the arithmetic part. Let's define a function f that : f(x) = ax mod N. The middle step in shor algorithm is to calculate, simultaneously, all values of f. In some papers and books, I saw some...

Homework Statement Question attached: Homework Equations see below The Attempt at a Solution - The theorem without prove i require needed is that the cut of maximum flow is given by the cut of minimal capacity. My proof would be along the lines of: - using this theorem, obviously 100 is a...

Hi, I'm a Civil Engineering student doing my final project for my BE degree. I have developed a software that uses a genetic algorithm for optimizing reinforced concrete columns. I have tested my program with a 17 stories building, and got some very unusual results in the design but much...

Homework Statement I need to write an Erdos-Renyi random graph, by using the adjacency matrix (or alternatively list) and calculate the fitness of the graph. Definition: G(n, p) is a random graph with n vertices where each possible edge has probability p of existing.Homework Equations The...

How would this operator be implemented physically if we had a quantum computer? In Grover's algorithm this magical operator is often called "phase inversion". Here is the operator from wiki: https://wikimedia.org/api/rest_v1/media/math/render/svg/07fb23bffa787430b084971c6a108a8f6ff6c2b3 It’s...

Homework Statement Consider the ##xyzzy## algorithm below. This algorithm takes a linear collection (e.g., a list or array) of size ##n## as an argument (i.e., as the input to the algorithm) and produces no return value (i.e., has no output, but might alter the linear collection). Note that the...

The problem statements, all variables and given/known data: Question 1 Question 2 Relevant equations: Provided in question snips. The attempt at a solution: Question 1: I think qux is the answer because it properly increments k by 1 in each iteration. j = j * 2 means j is always 0 so its...

What it does is described well in my comments. I'm using decimal, which is more precise than double but has a smaller range of values. https://msdn.microsoft.com/en-us/library/ms228360(v=vs.90).aspx const decimal pi =...

I'm trying to draw a circle and a (possibly rotated) square on a grid. I have the circle part down and it's the square that is giving me trouble. I am originally given 2 points which represent the coordinates containing opposite ends of the square. For example, those 2 points would be (8,14) and...

Homework Statement In a XY - model in two dimensional square lattice. I want to calculate specific heat capacity, <E> and <E^2>. By using the formula: H = -Jsum(<i,j>)Cos(tetha(i)-tetha(j)) The Metropolis algorithm reads: Simulations for Statistical and Thermal PhysicsHomework Equations H =...

So I came up with the following solution which is n*log2(n) since the input is n elements and I use a binary insertion and calculating the median is constant time. This is passes all the test cases in the tests that don't time out. I need to figure out how to make it faster so I beat the...

Homework Statement Say that a "clump" in an array is a series of 2 or more adjacent elements of the same value. Return the number of clumps in the given array. countClumps([1, 2, 2, 3, 4, 4]) → 2 countClumps([1, 1, 2, 1, 1]) → 2 countClumps([1, 1, 1, 1, 1]) → 1 Homework Equations The logic is...

Hey! :o We have the following i <- 0 j <- 0 x <- 1 y <- 1 z <- 1 c <- 1 u <- 1 while i<n do i <- i+1 j <- i x <- x*i z <- x y <- i+1 y <- x*y while j<2*i do j <- j+1 z <- z*j...

Homework Statement In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is made by machine 1,...). Installation order of some parts is not important, but some parts have to be installed before others...

Hi, I am just wondering what you should do in the case that you have a choice between two nodes to include for the next step, i..e both are equal to the minimal value of the set under consideration Do you need to follow through both cases and then see which way is the shortest, or is there a...

Homework Statement This is a problem of the 10-minute test we had today in school. Its written in Pascal and it is asked of us to analyze it and figure out what is the output when it runs without writing it down. Homework Equations 3. The Attempt at a Solution [/B] I wrote it in the editor...

First of all, I have no idea what I'm doing. I need to know how to find someone to create software that will take millions of numbers divided into 3 to 6 digit sets and manipulate the numbers in certain sets to a desired value.