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.

Filter by
Sorted by
Tagged with
2
votes
1answer
59 views

Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
0
votes
1answer
37 views

Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?
1
vote
0answers
31 views

Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
3
votes
2answers
182 views

Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
4
votes
0answers
60 views

Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
0
votes
2answers
55 views

Figuring out when one algorithm will be slower than another algorithm [closed]

I'm studying for a computing exam and came past the following question on a past paper and need help with it. When would algorithm A be slower than algorithm B? Demonstrate your answer with the help ...
1
vote
1answer
114 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
-3
votes
2answers
133 views

BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
4
votes
1answer
67 views

Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$ \times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$. We're ...
1
vote
1answer
48 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
80 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
155 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
56 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
113 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
2answers
56 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
66 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
194 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
144 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
51 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
137 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
240 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 ...
3
votes
1answer
55 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
40 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
133 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
309 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]...
2
votes
2answers
261 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
802 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
40 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$-...
2
votes
1answer
54 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
160 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
35 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
51 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
2k 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
143 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
35 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
214 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
629 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
98 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
257 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
47 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
68 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
1k 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
152 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
108 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
34 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
66 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
322 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$ ...