0
votes
2answers
39 views

Is my method of computing the running time correct?

Okay, so this is the code for which I need to compute the running time: ...
1
vote
1answer
31 views

How to get the ratio from a function of N?

The exercise gave us a chart which showed the running time as a $N$ increases: \begin{array}{c|c} N & \text{seconds}\\\hline 256 & 0.000\\ 512 & 0.000\\ 1024 ...
0
votes
1answer
45 views

How to calculate running time of code?

I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one: ...
0
votes
1answer
35 views

Calculating running time for C code

The problem is this: How many array accesses does the following code fragment make as a function of $N$? ...
0
votes
0answers
20 views

Find the running time of the following program fragment

The exercise in my book is asking me to calculate the running time of the following for loop: for (int i = 0; i < n; ++i) ++k; This instantly reminds me ...
2
votes
1answer
55 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
0
votes
0answers
35 views

Alternative to Hungarian Algorithm to determine minimum cost?

Is there a graphic calculator (CAS technology) method to solve minimum cost problems/allocations that are normally completed with the Hungarian Algorithm... Hungarian Algorithm is time consuming, ...
0
votes
1answer
32 views

Is there a quick way to obtain $a,b$ in $ax+by = z$ where $x,y,z$ are fixed and $x+1 = y$?

Suppose that all numbers are postive integers. Let $x,y,z$ be fixed/given and $x+1=y$. Then would there be a quick way to find set of solutions $(a,b)$ that satisfy $ax+by=z$? "Quick" would be ...
0
votes
0answers
16 views

Unrolling and rerolling with a different thickness

I have two rolls, the main one with two layers of material and the secondary one with just one of them. As the main one unrolls it loses one layer of thickness, and simultaneously the second one has ...
0
votes
5answers
81 views

Refresh summation formulas

I am trying to refresh on algorithm analysis. I am looking for a refresher on summation formulas. E.g. I can derive the $$\sum_{i = 0}^{N-1}i$$ to be N(N-1)/2 but I am rusty on the and more complex ...
0
votes
0answers
24 views

Reaching a proof

I'm trying to solve this problem: Link. After reading the problem, I realized that to start off, we can imagine the problem only in the positive axis, working only with $|x|$. Then, we want the ...
4
votes
1answer
47 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
1
vote
0answers
61 views

Absolute values nested multiple times

Is there any algorithm to quickly determine "zero points" (i.e. points with undefined derivation) of absolute values functions which are nested multiple times? I do know, that any part of this ...
0
votes
3answers
49 views

How do you solve a equation by converting to logarithm form for the problem$3e^{x-4} +2=83$?

$3e^{x-4} +2=83$ I understand converting logarithms but i dont understand how to convert e into log form and solve. help would be deeply appreciated.
0
votes
1answer
35 views

Reversing $\sum_0^kx\cdot2^i$

I'm trying to write an algorithm, and the easiest way I found for explaining the mathematical problem I'm facing is the following: Assume you have $x$ US dollars and you're gambling on a roulette. ...
0
votes
2answers
26 views

Relating number of iterations to n

n = length of list with more than n > 0. index = 0 step = 1 while index < n: index = index + step step = step + 1 return How many times will the loop ...
0
votes
1answer
44 views

How to come up with formula for this number growth

I have difficulties to come up with a formula to achieve this in my programming challenge : The input number ranges between 100 to 10.000 (all integers), then the output would be 0.1 - 10, so the ...
2
votes
1answer
58 views

What's the most efficient algorithm to determine the relative ordering of an unknown set of values?

This comes from a question on Arqade. The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow ...
1
vote
0answers
79 views

Richardson's theorem for constants

It's known that there is no algorithm for deciding for any elementary function is it identically zero or not (http://en.wikipedia.org/wiki/Richardson%27s_theorem ). But if I consider only constants - ...
0
votes
2answers
313 views

What is the point of the median?

It seems like the purpose of the median is to ignore a specific type of data point. More specifically, it is used to make outliers have a lower weight than other data points on an average. Why not ...
1
vote
1answer
58 views

simple maths problem

N locations are numbered from 0 to N-1. Given a int[] containing N elements. The i-th (0-based index) element of array is the number of persons who live near location i.One car can move to one ...
0
votes
1answer
60 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
2
votes
0answers
80 views

Maximizing an algebraic expression using brackets

It's a riddle of sorts: given a list of numbers $\alpha_1 \dots \alpha_n$ and operators $o_1 \dots o_{n-1}$ which can be only $\times\, \mbox{or}\, + $ if the above is a specific algebraic expression ...
2
votes
0answers
46 views

Is there a known algorithm for approximating all the real and imaginary zeros of any well behaved equation of a single variable?

Does there currently exist a general algorithm (or set of algorithms used together) that will approximate all the zeros of any well behaved non-differential equation of a single variable which has a ...
0
votes
1answer
75 views

What is the Mirror/PingPong clamp mode algorithm?

I do programming as a hobby, and in a dynamic system various numerical values inevitably change. Those values can be greater than or less than the expected range, in which case they need to be ...
1
vote
2answers
135 views

How can I optimise the power series calculation of the exponential function?

In an answer to the question Fastest way to calculate $e^x$ upto arbitrary number of decimals? there is a description of a method by which the number of terms needed to calcluate $e^x$ to a given ...
5
votes
5answers
274 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
0
votes
1answer
27 views

Rounding to the nearest term in a geometric progression

Consider the following progression: where i is ith number within the progression. I would like to devise an equation that will round input value to the nearest number from this progression. For ...
1
vote
1answer
45 views

Smallest value of n for two algoritms with a certain running time

If one algorithm has a running time of $100n^2$ and another of $2^n$; how can I find the smallest value of $n$ such that the former is faster than the latter? I could do: $100n^2 < 2^n$ then ...
1
vote
1answer
113 views

Celsius to Fahrenheit back and forth conversion with rounding.

Recently I've encountered some problem with conversion Celsius and Fahrenheit scales. Let's assume that I have value of 44 degrees in Fahrenheit scale, I convert this to the Celsius which gives me ...
4
votes
2answers
189 views

Accounting for changing radius of a paper roll to always unroll the same amount of paper

So I'm building a Post-Turing Machine that's running a 5-state busy beaver. It has a 300ft roll of receipt paper at each end simulating an infinite tape. Hypothetically the tape is divided into ...
0
votes
1answer
40 views

Algorithm for root function $[2^{n-1}]$

I am attempting to convert this function $[2^{n-1}]$ into a root function to return original value. Thus far all my attempts have ended in abject failure. Base : 1 2 3 4 5 6 7 8 9 Result : ...
-3
votes
1answer
64 views

Maximize $f(p)=(k-p)^2+(p-1)^2$

From a computer algorithms analysis (quicksort), its given that $f(p)=(k-p)^2+(p-1)^2$ is maximized when $p=1, p=k$. But how do they get that?
9
votes
5answers
620 views

Algorithms for “solving” $\sqrt{2}$

The very first words out of my mouth need to be this... "Solving" is the wrong term since I am speaking about irrational numbers. I just don't know which word is the correct word... So that can be ...
0
votes
1answer
90 views

Solving this inequality without trial and error

"What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?" I know the answer is $n = ...
4
votes
1answer
998 views

The trick to proving trigonometric identities

This question is motivated from the following excerpt from Rational Points on Elliptic Curves by Silverman and Tate: $$\cos \theta = \frac{1 - t^2}{1 + t^2}, \sin \theta = \frac{2t}{1+t^2}$$ ...
2
votes
3answers
94 views

Is there any fast way to get the number of a certain day in a week

I'm realy sorry, if this question is a bit stupid... But this is my first time on mathematics stackexchange. Do you guys now for example, how to know the number of monday in a year?
0
votes
2answers
313 views

Universal Formula for Expanding Brackets

I know how to expand brackets such as the following in general, using the foil or crab-claw methods, but my tutor mentioned that there is a universal formula/algorithm for an expansion. E.g Bracket: ...
0
votes
1answer
156 views

Divide N items into M groups with as near equal size as possible

Im trying to split (say) N pink, fluffy balls into M groups as evenly as possible. Eg: ...
-1
votes
1answer
58 views

what is a general algorithm to find a nonempty integer subset that have integers add up to 0?

what is a general algorithm to compute if a set have nonempty integer subset that have integers add up to 0? i would like to know one with the least tries and the proof of it. Example:{−2, −3, 15, ...
0
votes
1answer
75 views

Non-proportional, inverse algorithm

I'm trying to come up with the correct algorithm for a setting on a meter in my app. Basically, I have a value (lets call it 'x') returned from a source which can be in the range of 0 to 30. As x ...
2
votes
2answers
845 views

Take set of values and change scale [duplicate]

I have a large array of variable-integer keypairs. The integer values range from -5 to 5. I'd like to scale that data to a range of 0 to 2. Logically, -5 would become 0, 0 would become 1 and 5 would ...
4
votes
2answers
502 views

Russian Peasant Method for multiplication

What exactly happens with the remainder in this algorithm? I don't understand why it is "dropped". Example: $$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline ...
1
vote
1answer
182 views

Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)…(z-n)$ into a vector

So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ ...
1
vote
1answer
59 views

Trivial question on an algebraic equation

I am too rusty in algebra. I have as input in a program numbers a and b. I am trying to find them using the bellow relation: ...
0
votes
0answers
53 views

How are these operations the same? How to convert a multiplication in a different form?

I am reading on a specific operation, how it should be done in order to avoid overflow during multiplication. The operation is: $$( A * \text{state} ) \% M;$$ This is susceptible to overflow. The ...
4
votes
1answer
172 views

How to find out if two solutions are equivalent or different?

Given 5 different numbers ($\in \mathbb N$) in a specific brackets pattern like: $$\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / x_5 = \text{result}$$ Only the brackets are ...
0
votes
1answer
90 views

Different solutions under distributive and commutative equivalence

Given 5 numbers: $x_1, x_2, x_3, x_4, x_5 \in \mathbb N$ all the 4 operations: $+ - \times /$ a specific brackets pattern: $\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / ...
3
votes
2answers
216 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
4
votes
2answers
598 views

Upper bound for the partial sum $\sum k \lg k$ via summation?

In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound: $$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} ...