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.

learn more… | top users | synonyms

0
votes
0answers
36 views

Writing programs with a block programming environment vs. Writing programs using high level prgramming language

I'm a GCSE Computing student and I've been asked to compare writing programs in a block programming environment (I think this means using programs such as Scratch or App Inventor but I'm not entirely ...
8
votes
3answers
255 views

When is the AKS primality test actually faster than other tests?

I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality ...
-1
votes
1answer
21 views

ARQ Protocols and sequence numbers [closed]

What will happen if sequence number is not used in an ARQ protocol (e.g, Go-back-N, selective repeat)?
6
votes
1answer
113 views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
3
votes
2answers
135 views

A heuristic for finding a maximum disjoint set

Background I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares. This problem is NP-complete. Many papers suggest approximation ...
6
votes
2answers
153 views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with ...
1
vote
1answer
109 views

Efficiently pick a largest set of non-intersecting line segments

Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting? Brute force we would get $2^n$ sets to check where $n$ is the ...
2
votes
0answers
107 views

Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

This is a popular question: What is the most efficient (in time complexity) way to sort 1 million 32-bit integers? Most answers seem to agree that one of the best ways would be to use radix ...
0
votes
1answer
38 views

How do context switches factor into CPU utilization?

When studying operation systems, is context switch time included in CPU utilization time? For example, if 5 percent of CPU time is wasted to context switching, is CPU utilization 95 percent?
-1
votes
3answers
184 views

Which data structure to use for accessing min/max in constant-time?

I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.
2
votes
0answers
38 views

Calculating the classification threshold efficiently

I have a multi-label classification problem, in which each input sample has a set of zero or more output labels. I have a multi-class classifier which, for every input sample, returns a certain score ...
0
votes
1answer
360 views

Algorithm to add sum of every possible xor-sum sub-array

I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here. Problem Statement XOR-sum array is to XOR all the numbers of that sub-array. An array is given ...
3
votes
2answers
85 views

Enumerating weighted permutations in sorted order problem

Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem. Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ ...
1
vote
2answers
146 views

What do I need to know about algorithms?

Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their ...
23
votes
8answers
2k views

Are algorithms (and efficiency in general) getting less important?

Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite ...
9
votes
3answers
2k views

Factorial algorithm more efficient than naive multiplication

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
2
votes
1answer
25 views

Finding users covering a set x by x

I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where $S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$. Every time I add a new entry to $c$, i.e. ...
0
votes
0answers
18 views

Fast energy function substitute for Hopfield network?

The energy function in a Hopfield network to determine whether it has converged seems to be the major sink of computational time and makes the Hopfield network run very slowly. Is there a fast ...
2
votes
1answer
67 views

Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
6
votes
3answers
390 views

What data structure would efficiently store integer ranges?

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following: Insert a new integer Insert a range of contiguous integers Remove an integer Remove all ...
0
votes
2answers
115 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
2
votes
2answers
231 views

What are efficient data structures for inserting and accessing elements?

Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time? When I say "reasonable time", ...
2
votes
3answers
620 views

What is the most power/energy efficient sorting algorithm?

I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. ...
7
votes
3answers
5k views

Why is selection sort faster than bubble sort?

It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort ...
6
votes
1answer
137 views

Largest reported speedup for a parallel computation?

A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel ...
1
vote
3answers
162 views

Priority queue with ubounded number of elements (i.e., with dynamic storage)

I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for ...
1
vote
4answers
702 views

What are flops and how are they benchmarked?

Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked ...
2
votes
0answers
156 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
935 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?
5
votes
0answers
53 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
101 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
196 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
106 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
43 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
449 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
95 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
4answers
218 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
42 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) ...
4
votes
4answers
198 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
1k 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: ...
8
votes
6answers
1k 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
91 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
49 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
120 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 ...
4
votes
1answer
115 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 ...
12
votes
3answers
869 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
87 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
419 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
210 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
213 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 ...