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.

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
617 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 ...
6
votes
1answer
309 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 ...
5
votes
0answers
128 views

Evaluating sums of subsets

Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$ $$ \begin{align*} s_1&=x_1+x_2+x_3+x_9,\\ s_2&=x_1+x_2+x_4+x_9,\\ s_3&=x_1+x_2+...
5
votes
1answer
1k views

Are there current benchmarks for algorithms solving Travelling Salesman?

I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current ...
4
votes
0answers
63 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 ...
4
votes
0answers
44 views

Element-wise merging and re-sorting lists of sorted elements

Imagine you have a vector of pairs $(id, x)$ where $id \in I$, some set of opaque identifiers (hereafter, ids), and $x \in \mathbb{N}$ some value. Assume that every $id$ value is unique in your list. ...
3
votes
1answer
173 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 ...
3
votes
0answers
2k 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 ...
3
votes
0answers
126 views

Solving systems of boolean equations

So I have a system of equations where varibles range over $\{0,1\}$ and the only operation is logical or ($\lor$). Each equation is of the one of two forms 1) $a = b \lor c$ 2) $1 = a \lor b$ where ...
3
votes
0answers
182 views

Find a sorting procedure for seven elements that minimises the average number of comparisons performed

In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that ...
2
votes
0answers
183 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 "...
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
0answers
381 views

Unique integer priority queue with both $O(1)$ insert and extract-min?

I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do ...
2
votes
0answers
116 views

Max Flow on low depth DAGs

I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG ...
2
votes
0answers
143 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 ...
2
votes
0answers
659 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. ...
1
vote
0answers
60 views

Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
1
vote
0answers
49 views

Convex hull on set of squares

Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible. The following constraints are known: Each of the two to six ...
1
vote
1answer
31 views

Understanding recursion tree for withdrawal formula

$$ T(n) = T(n-a) + T(a) + cn $$ Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$ And I don't understand why. Maybe I didn't understand the ...
1
vote
0answers
19 views

Regex vs line by line read efficiency - general concept question

Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...
1
vote
0answers
33 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 ...
1
vote
0answers
117 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, ...
1
vote
0answers
39 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, ...
1
vote
0answers
309 views

Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
1
vote
0answers
57 views

Efficient method to sort very large set of integer vectors by all coordinates simultaneously

I have a set $E$ which is the set of all possible $d$-tuples ($d$-dimensional vectors) of integers between $1$ and $n$. Typically $d=3$ and $n\approx1000$, but for the sake of making a small example, ...
1
vote
0answers
137 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
0
votes
0answers
48 views

Efficient triangular decomposition of an integer

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right? Its specification is that if I do (q, r) = f(n, d), I get ...
0
votes
1answer
44 views

Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
0
votes
1answer
59 views

How to prove Big-O when $F(N)$ is even or odd

If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
0
votes
0answers
14 views

Parent Node in BST

Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times? ...
0
votes
2answers
35 views

Comparing the efficiecy of 2 run times

I have a heap with $n$ elements. $k$ represent a number that is the height of one of the elements in the tree. I need to compare two run times and prove what i claim. The 2 run times are: $$ (1)O(...
0
votes
0answers
39 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 ...
0
votes
0answers
2k 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 ...
0
votes
0answers
51 views

Multiple Cores vs Single Core Power Efficiency Equations

I was searching for OpenMP tutorials and I came up a video that showed some simple equations that promotes multiple core hierarchies against single core ones. The equations used are Capacitance = ...
0
votes
0answers
48 views

Comparing the efficiency of algorithms with finite input sizes

I'm a non-CS grad student working on an algorithm which would be an alternative to conventional GPS position estimation algorithms. My advisor insists that I must compare the run-time of these ...
0
votes
0answers
71 views

Aliens to the Moon

$N$ Aliens want to reach their Moon ($D$ meters away), but they can only put on each other, making a vertical chain. Every $Alien(i)$ has an height $X(i)$ and a lenght of their arms $Y(i)$. ...
-1
votes
1answer
46 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
-2
votes
2answers
37 views

Calculating efficiency?

A program must construct and then use a set $S$ of 1000 integers. ...