Questions tagged [iteration]
The iteration tag has no usage guidance.
38
questions
2
votes
1
answer
83
views
Iterate over a range randomly without any duplicate or storing the full range in memory
I'm trying to create (or find) an algorithm to iterate over a range (e.g.: 1-100, etc) but randomly, without any duplicate values (similar result to random sort, etc) but without actually storing the ...
- 121
0
votes
0
answers
14
views
Periodicity of substitution system
I’m interested in substitution systems: maps which use a set of rules to transform elements of a sequence into a new sequence.
For simplicity we will consider here only binary 1-D arrays.
Unlike the ...
- 111
0
votes
0
answers
77
views
Iterate through all values of a certain subset of all permutations
Let's say we've got $n$ numbers to multiply together. But the multiplication operation, like in computer floating-point arithmetics, is not associative. Thus the order of multiplication matters.
...
- 201
0
votes
0
answers
30
views
Symmetry group of the acyclic oriented L-cube using the Hyperoctahedral group
I'm trying to figure out all elements of a symmetry group for the acyclic oriented $L$-cube. I do have an algorithm, but its complexity is not suitable for larger $L$. I computed $L=5$ on my old ...
- 31
0
votes
0
answers
143
views
Iterative version of depth-first-search code to detect cycle in a directed graph [duplicate]
I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just ...
2
votes
1
answer
143
views
Iteration Vs Induction Method
I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
1
vote
2
answers
272
views
Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
...
- 495
19
votes
3
answers
7k
views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
- 291
1
vote
1
answer
143
views
How to use Runge–Kutta methods in a second order ODE
Consider a second order equation $F=ma=m\ddot{x}$.
In the language of Euler's method
$\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
$\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
$x(t+dt)=x(t)+\dot x(t)dt$
Basically, ...
0
votes
0
answers
36
views
Is it possible to determine an instance of an NP-hard problem is easy or hard by the optimization?
I have an NP-hard problem and an optimization to deal with the problem.
I want to know that is it possible to distinguish between easy and difficult instances of the problem by the parameters of the ...
- 21
0
votes
1
answer
35
views
What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?
Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.
I have an NP-hard problem and an optimization to deal with the problem. Recently, I ...
- 21
2
votes
2
answers
162
views
How to iterate the Hardy-Ramanujan integers quickly
The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:
$...
- 313
1
vote
1
answer
149
views
Iterate unique sets of integers
I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have ...
- 113
1
vote
1
answer
361
views
Computation of iterated logarithm function
I recently came across the iterated algorithm function denoted as $\lg^* n$.
But I am having a hard time understanding this statement:
$\lg^* n = \min \{i \ge 0: \lg^{(i)} n ≤ 1\}$
I could not ...
1
vote
1
answer
1k
views
Arbitrary depth nested for-loops without recursion
Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.
...
- 143
1
vote
0
answers
278
views
Can every problem that uses recursion be solved using iteration? [duplicate]
We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using ...
- 133
3
votes
0
answers
51
views
What is the name of visiting an array starting at first element, then last element, then second, then last but one, then third, etc
For example if I have an array
[0, 1, 2, 3, 4, ..., n]
and I want to iterate over it in an order like
...
- 161
0
votes
1
answer
38
views
Search Algorithm with two areas of solutions [closed]
I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute ...
- 3
2
votes
2
answers
100
views
Is there a formal definition for iteration?
I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. ...
- 261
0
votes
2
answers
228
views
Iteration vs Recursion question in Lisp method
I am curious if the following method would be called iterative or recursive:
...
0
votes
1
answer
30
views
How does a=2 twice in this code sample? [closed]
I am just starting out learning code.
The output of the following code is OOOXOXOO, but I don't see how X can be printed twice. How does a=2 more than once?
...
- 3
0
votes
0
answers
36
views
Application of iterative algorithm $(\theta_n,w_n)$ converging to $\{(\theta,\theta):\theta \in \Bbb R\}$
I have a iterative algorithm $(\theta_n,w_n)$ which I am showing converges to $\{(\theta,\theta):\theta \in \Bbb R\}$.
The iterative algorithm is of the form :
$\theta_{n+1} = \theta_n + a(n)[h(\...
- 101
0
votes
3
answers
183
views
Which is better ? Iterations or Recursions?
I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa.
But which type of repetition is preferable for minimum amount of computational effort and ...
- 119
1
vote
0
answers
44
views
Nested Function stuck on iteration update
I want to solve the Sparse Extended Information Filter Slam described by Dr. Sebestian Thrun in Probabilistic Robotics.I stuck in some nested function.
The algorithm is described in page 309 in this ...
- 167
0
votes
2
answers
114
views
If it's Possible to Create the If-Statement from Simpler Primitives
This question is about how to create an if statement (one of the control-flow statements) from scratch.
An if-statement is typically a built-in construct in ...
- 2,163
0
votes
0
answers
133
views
Understanding How to Flatten a Nested Function System
There are at least two ways to flatten out a nested function. Both of them need to keep a certain amount of state to accomplish this. The two ways are:
By creating several boolean variables for each ...
- 2,163
4
votes
1
answer
541
views
Prove correctness of the iterative algorithm
Description:
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying ...
- 281
6
votes
0
answers
873
views
Understanding the Polyhedral Model
I am wondering at a high level the mathematics of the Polyhedral Model.
The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
- 2,163
2
votes
1
answer
48
views
Generating all words of length $n$ avoiding $A^2$ and $B^3$
I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing?
I ...
- 1,931
2
votes
1
answer
99
views
Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$
I have a sum:
$$S = \sum_{i=1}^n{\lfloor a/i \rfloor i^2},$$
where $a$ is a constant.
Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in ...
1
vote
1
answer
3k
views
Find Number of even subarrays $O(n)$ [explanation needed]
So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must ...
- 61
0
votes
0
answers
81
views
How is this defined in an iterative style?
This is the so-called recursive style:
And this is the so-called iterative style:
It seems like it is defined recursively to me. The function doesn't hide the next call of the function defined in it ...
- 133
0
votes
1
answer
244
views
How to convert this recursive algorithm to an iterative form?
Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, ...
- 345
5
votes
1
answer
302
views
Finding the largest linear combination that is not possible
Regarding the problem:
What is the largest bet that cannot be made with chips worth $\$7.00 $
and $\$9.00$? Verify that your answer is correct with both forms of
induction.
I need to find an ...
- 187
0
votes
0
answers
309
views
Iteration vs. recursion: what do these terms really mean?
Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by ...
0
votes
2
answers
59
views
Is linked list a preferable underlying basic DS for a collection mutable through an iterator
I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a ...
- 315
1
vote
0
answers
27
views
Basic Determine exact amount of iterations
How exactly do you track the exact amount of iterations? I know its probably basic but can't figure out how so was hoping someone could explain to a complete beginner how you arrive at an answer.
<...
- 11
46
votes
5
answers
12k
views
Iteration can replace Recursion?
I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
- 1,617