Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [efficiency]

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.

1
vote
1answer
43 views

How much does C# gain from its value types

C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
0
votes
1answer
44 views

In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
3
votes
2answers
137 views

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows: insert(num): insert num into the data structure. find(sum): return a pair(a, b) ...
1
vote
1answer
52 views

MergeSort k arbitrary words in linear time

Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to ...
3
votes
1answer
67 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
1
vote
1answer
34 views

Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
1
vote
1answer
57 views

“Ways to make change for a dollar”: How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
3
votes
1answer
176 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
0
votes
1answer
37 views

Finding duplicates in a stream of numbers

This is an interview question. Say you have a function foo() which returns some integer. You need to write an algorithm that does the following: (...
1
vote
1answer
44 views

Number of steps in worst Case

we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or ...
0
votes
2answers
97 views

Data structure for finding max, inserting and deleting in O(1) and O(n) space

This is an interview question. I need to implement a data structure that supports the following operations: Insertion of an integer in $O(1)$ Deletion of an integer (for example, if we call delete(7),...
12
votes
2answers
213 views

Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
2
votes
1answer
45 views

Why does parallelising slow down this simple problem against looping through all the data?

I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
1
vote
2answers
36 views

Efficiently find elements which are out of place in an otherwise sorted list

I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the ...
2
votes
1answer
90 views

Linked List in Maximal Scoring Subsequences Algorithm

For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, ...
-1
votes
2answers
119 views

Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?

I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot)...
0
votes
1answer
279 views

Is there a more efficient stability index algorithm?

I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a[0]...
1
vote
2answers
132 views

How would the use of an external lookup table affect file compression?

It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My ...
1
vote
0answers
501 views

What are efficient data-structures for insert/delete by index?

First of all, a definition of the operations: Insert by index: insert element e at index n, increasing the index of all ...
2
votes
1answer
37 views

Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$ I have a problem which requires to compute $n$-th $k$-...
1
vote
1answer
36 views

Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
0
votes
1answer
97 views

Efficient bucketing of numbers

Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a ...
0
votes
0answers
34 views

Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
1
vote
1answer
49 views

Is this graph algorithm more efficient?

Suppose we are given a digraph A. We need to calculate its connectivity digraph B. I conceived two algorithms: 1. Set X = A. Loop Set Y = X*A united with identity Stop the loop if Y = X Set X = Y ...
2
votes
3answers
778 views

Efficient point grouping algorithm

I'm trying to find a good solution to the following problem: Given a set of 3d real number coordinates inside a cube, I want to group them into containers. The containers should contain all elements ...
2
votes
0answers
114 views

Most efficient unification algorithm?

I've been trying to find the most efficient unification algorithm by following reference chains on the Wikipedia article on unification. As far as I can tell, the fastest one is the one presented in "...
1
vote
2answers
34 views

Are their problems that we can not even approximate efficiently?

Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is ...
0
votes
2answers
40 views

Is closed form of summation less costly?

I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does. Here's the original sum <...
2
votes
1answer
160 views

Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

Is there any efficient algorithm to find shortest distance between all pairs of vertices? The graph is: Cyclic Sparse (each vertex has either 2 or 3 edge) undirected(bidirectional) weighted non-...
2
votes
1answer
297 views

What is more effective, a do while or a while?

I mean, with the same code, if I modify a do while into a while in this way: do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change in the code? B = condition S; = instructions
1
vote
1answer
88 views

How to compare the efficiency of two encoding schemes or hypothesis languages?

My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
0
votes
1answer
189 views

Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?

I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively ...
2
votes
1answer
46 views

find number in array divided into k parts

I was wondering what is the most efficient way to find the a number in an array with the following conditions: Array $A$ of size $n$ divided into even parts in the size of $k$ every element ...
4
votes
1answer
60 views

Christmas Light Route Efficiency

This is a real situation (I hope it's ok that I post this here. If not, please suggest a better home). I have little knowledge of algorithms, but I know I can use one to solve this problem. I'm ...
13
votes
2answers
2k views

Can the “divide” step in a merge sort be avoided?

So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps. If you iterated over the ...
0
votes
0answers
810 views

stack vs queue efficiency

Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the ...
1
vote
2answers
138 views

Optimal generalized bisection method

Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions: $x$ is unique. Given any $t \in [a,b]$ I can check, at some fixed computational cost, ...
1
vote
0answers
84 views

Advantage of bulkloading in a B-Tree

https://en.wikipedia.org/wiki/B-tree#Initial_construction Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key. In the wiki example the keys are sorted, ...
2
votes
0answers
33 views

Efficiently find the next item in a sequence to exceed some bounds

I have a bounded sequence of integers, and for each element, I want to know if the sequence next goes some distance above that element, below that element, or neither. This is straightforward in ...
2
votes
1answer
61 views

What problems are believed to have an efficient algorithm?

Just out of curiosity, What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them? This question came up to my mind after reading about PRIMES ...
0
votes
1answer
244 views

Efficiency of 0-1 linear programming w.r.t. number of binary variables

I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0. Lets say I have a fixed number of $n$ ...
1
vote
2answers
260 views

Is it possible to implement a WeakMap with primitive keys and weak values?

Theory Basically, I have a use-case where I would like to use primitives to store weak references to non-primitive values. If the value is no longer referenced anywhere else, then the entry should be ...
1
vote
1answer
75 views

Calculating the information density of an encoding system

How do I calculate the information density of an encoding system? This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
1
vote
1answer
81 views

Best combination of values pulled from a matrix

What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized? For example, given the ...
1
vote
0answers
33 views

Decode Reed Muller codes efficiently given only a syndrome

So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector? The approach I took naively was to build the syndrome table, ...
3
votes
2answers
139 views

GOTO vs. including line in loop - will it affect efficiency?

Let's say I have an algorithm something like as follows: ...
1
vote
2answers
145 views

Efficient Algorithm to determine highly composited numbers [closed]

Im writing an algorithm to determine highly composited numbers. But it's very unefficient with $\Omega(f(n)) = n³$. Does someone know how i can make my code more efficient. Is my approach ok? Here is ...
5
votes
2answers
776 views

Data structure for A*'s “open” set

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet ...
6
votes
2answers
945 views

Why is it most efficient to resize a dynamic array to 2 * array.length()?

By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array. I read in a textbook that doubling the size of the array is ...
1
vote
1answer
104 views

Parallel or efficient computation of value with momentum

I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that: $$ A'_{i,j} = \alpha A'_{i,j-1} + (1 - \alpha) A_{i,j} \\ 1 \leq i \leq M, 1 \leq j \leq N, \alpha \in [0, 1] $$ ...