In mathematics and computer science, an algorithm ( (listen)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. In contrast, a heuristic is a technique used in problem solving that uses practical methods and/or various estimates in order to produce solutions that may not be optimal but are sufficient given the circumstances. As an effective method, an algorithm can be expressed within a finite amount of space and time, and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.The concept of algorithm has existed since antiquity. Arithmetic algorithms, such as a division algorithm, were used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC. Greek mathematicians later used algorithms in 240 BC in the sieve of Eratosthenes for finding prime numbers, and the Euclidean algorithm for finding the greatest common divisor of two numbers. Arabic mathematicians such as al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.The word algorithm itself is derived from the name of the 9th-century mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose nisba (identifying him as from Khwarazm) was Latinized as Algoritmi. A partial formalization of the modern concept of algorithm began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert in 1928. Later formalizations were framed as attempts to define "effective calculability" or "effective method". Those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's Formulation 1 of 1936, and Alan Turing's Turing machines of 1936–37 and 1939.
Homework Statement
Hi, I'm doing a problem by solving congruences but my question is simply trying to find the inverse of 2 \enspace (mod\enspace 17) from 2x \equiv 7(mod \enspace 17).
Homework Equations
It's hard to find a definition that makes sense but if you check my upload images you...
Hi,
I have a random array which represents method calls. For instance: [3, 4, 7, 40, 39, ...] meaning that method 0 is called 3 times, method 1 is called 4 times, method 2 is called 7 times, method 3 is called 40 times, method 4 is called 39 times and so on upto n. Now consider a module as a...
The roulette prediction algorithm is described here: http://pingless.co.il/roulette.pdf
And I have a problem with the formula attached
Where teta θ is position, velocity and acceleration of the ball. g is garvity force. r is the ball radius from center of the roulette. a is stator incline...
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...
In a scientific paper (Neural Networks: A Systematic Introduction, page 86) about the Perceptron Algorithm I found:
A good initial heuristic is to start with the average of the positive input vectors minus the average of the negative input vectors. In many cases this yields an initial vector...
Homework Statement
For some reason, my book's solution for this problem is given in a very wordy way, rather than in (Pascal-style) pseudo-code (which is what this book usually gives its solutions in).
Here is the problem's statement and solution.:
PROBLEM STATEMENT:
PROBLEM SOLUTION...
Homework Statement
PROBLEM STATEMENT:
http://dpaste.com/0GN9MQ2
BOOK'S SOLUTION:
http://dpaste.com/0ZQ0YQM
Homework Equations
m ⋅ u + n ⋅ v = 2ab
GCD(a,b) ⋅ LCM(a,b) = ab
z = 2 * LCM(a,b)
z ?=? (m ⋅ u + n ⋅ v) / GCD(a,b)
The Attempt at a Solution
How does the author go from m ⋅ u + n ⋅ v =...
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...
Homework Statement
The number of busy lines in a trunk group (Erlang system) is given by a truncated Poisson distribution. I am asked to generate values from this distribution by applying the Metropolis-Hastings algorithm.
Homework Equations
The distribution is given in the attached picture...
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 =...