Using as few resources (e.g. time, space) as possible while solving a problem. Use this tag if your question is specifically about resource usage, not for generic algorithm questions that happen to mention running times.
2
votes
0answers
29 views
Why does Shellsort work well on Sorted and Reverse ordered lists?
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
4
votes
3answers
115 views
Explaining why FFT is faster than DFT for the general public?
How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
4
votes
0answers
30 views
Relaxed Bin Packing Problem
The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.
Is there an ...
1
vote
1answer
39 views
Optimized algorithm to compare templates of two websites
My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer.
Here, "template" means the way any page presents its contents.
...
1
vote
2answers
92 views
How do we determine how much time a multi-tape DTM saves over a one-tape DTM?
Note: This is a part of a homework question
Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}
Then it says "Discuss how much time your machines saves ...
1
vote
1answer
55 views
Are genetic algorithms special instances of random search done in an unexpectedly short run-time? [closed]
I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?
Ever since I finished my ...
1
vote
1answer
25 views
Random file access in a block based file format
I am writing a program to store, retrieve and delete "blocks" of data of varying sizes.
The way it currently works is by keeping a database storing the locations of the blocks and the locations of ...
1
vote
1answer
84 views
Complexity of algorithm inserting an element in a circular linked list at the front end
In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here)
But in a book currently, I have, it is ...
5
votes
1answer
68 views
A vector-like data structure with allocation table; O(1) indexing time required
I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new ...
2
votes
3answers
88 views
Speeding up a program solving Icosoku
I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and ...
1
vote
1answer
39 views
Modeling timing characterists of an architecture
I am building a system and I have a couple of architectures in mind. I want to have an idea of which architecture is likely to be most performant (quickest).
I can make different decisions like
1) ...
3
votes
4answers
126 views
Are there real lexers that use NFAs directly instead of first transforming them to DFAs?
I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
6
votes
3answers
286 views
Is there an algorithm for checking if a string is a catenation of palindromes?
Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution:
...
7
votes
6answers
295 views
Can we say DFA is more efficient than NFA?
I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
0
votes
2answers
66 views
Which is more computationally efficient: multiplication or 0 padding?
On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of ...
1
vote
2answers
40 views
Cache strategies, what reference article could I study?
So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often.
When playing with the idea, I imagined something like the ...
1
vote
1answer
83 views
Regular vs LALR(1): what is faster
Supposing we have two grammars which define the same languge: regular one and LALR(1) one.
Both regular and LALR(1) algorithms are O(n) where n is input length.
Regexps are usually preferred for ...
3
votes
1answer
67 views
What sort of algorithm/communication model/data structure do collaborative real time editors use?
I am researching collaborative editing systems for some work, but so far my search is turning up blank.
Collaborative real-time editing systems almost all have features like:
Many users can edit ...
6
votes
3answers
330 views
Retrieving the shortest path of a dynamic graph
I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
4
votes
1answer
63 views
What are the effects of the alphabet size on construct algorithms for suffix trees?
For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on ...
7
votes
0answers
350 views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
2
votes
1answer
118 views
Implementing addition for a binary counter
A binary counter is represented by an infinite array of 0 and 1.
I need to implement the action $\text{add}(k)$ which adds $k$ to the value represented in the array.
The obvious way is to add 1, k ...
3
votes
2answers
112 views
Algorithm to pack any small boxes into a big box
I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
3
votes
1answer
201 views
Maximum Schedulable Set Zero-Lateness Deadline Scheduling
This is a homework problem for my introduction to algorithms course.
Recall the scheduling problem from Section 4.2 in which we sought to
minimize the maximum lateness. There are $n$ jobs, each ...
5
votes
1answer
147 views
Radon transform for advanced 3d graphics and games?
The Radon transform is used to take 2d projections of an object and create a 3d representation.
It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
2
votes
0answers
40 views
Time - Complexity Convex Optimization and Eigen Decomposition
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
2
votes
1answer
132 views
Calculate storage requirements for a data set
I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading.
I'm writing a bunch of integers to disk. Lot's of them.
Starting ...
6
votes
2answers
471 views
Dynamic programming with large number of subproblems
Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street:
Grid Walking (Score 50 points)
You are situated in an $N$-dimensional grid at ...
8
votes
3answers
227 views
Applying algorithms on large data
Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how ...
3
votes
1answer
150 views
How to compute linear recurrence using matrix with fraction coefficients?
What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for ...
3
votes
1answer
80 views
Running time of CDCL compared to DPLL
What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy ...
5
votes
2answers
173 views
What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?
I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced ...
1
vote
0answers
118 views
Queue that can sort by multiple priorities?
I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure ...
1
vote
1answer
84 views
Algorithm to check the 2∀-connectness property of a graph
A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...
3
votes
2answers
236 views
Generating number of possibilites of popping two stacks to two other stacks
Context: I'm working on this problem:
There are two stacks here:
A: 1,2,3,4 <- Stack Top
B: 5,6,7,8
A and B will pop out to other two stacks: C and ...
11
votes
2answers
459 views
Efficient map data structure supporting approximate lookup
I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
9
votes
2answers
457 views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
4
votes
1answer
742 views
Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:
Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ ...
10
votes
1answer
835 views
What is the most efficient way to compute factorials modulo a prime?
Do you know any algorithm that calculates the factorial after modulus efficiently?
For example, I want to program:
...
16
votes
6answers
404 views
Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
6
votes
3answers
734 views
What is most efficient for GCD?
I know that Euclid's algorithm is the best algorithm for get the GCD (great common divisor) for a list the positive integer numbers.
But, in the practice, you can write two codes por evaluate the gcd ...
13
votes
5answers
3k views
Adding elements to a sorted array
What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?
I was thinking something along the following lines.
I could add to the end of an array ...
8
votes
3answers
289 views
Notions of efficient computation
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing ...
7
votes
1answer
711 views
Are all context-free and regular languages efficiently decidable?
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
23
votes
3answers
503 views
Why polynomial time is called “efficient”?
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
