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

1
vote
1answer
25 views

Efficient algorithm for finding weakly connected components

We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to ...
0
votes
0answers
19 views

RMQ with single index update in array

Range Minimum Query (RMQ) can be solved in (O(n), O(1)) if the array is known to be static by dividing it into blocks and then using Cartesian tree numbers to detect "similar" blocks. Link: ...
0
votes
1answer
42 views

Checking whether a node is expandable

I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be expandable ...
0
votes
1answer
43 views

Searching through all program of a stack-based language with little memory

I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output. Given a program fragment, I can ...
6
votes
1answer
86 views

How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
5
votes
3answers
221 views

Building static hash table with particular collisions

Is there efficient algorithm to encode keys in hash function with provided collisions? By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time ...
0
votes
1answer
24 views

Can any algorithm efficiently be implemented as a SIMT problem?

Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions. Excluding overhead due to hardware limitations (specifically, memory copy ...
1
vote
1answer
56 views

What is more efficient: gcd(x,y) or brute force, when x and y are a very big numbers

I implemented the quadratic sieve algorithm as it's described in wiki. Most of the work of the algorithm is to determine if some big integer $Y$ belongs to the vector $b[b_1,b_2,b_3,\ldots]$. So far ...
5
votes
1answer
257 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
2
votes
1answer
41 views

Efficient formulation for binary integer linear programming

Problem: There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either: nothing, or 1 S, or 1 B, or 2 S, or 2 B, or 1 B and 2 S We are given the ...
0
votes
1answer
19 views

In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]

It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...
3
votes
2answers
80 views

Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

The protocol is defined here, but I'll give a summary here. Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, ...
4
votes
1answer
40 views

Efficient algorithm to compute the minimum of multiple piecewise linear functions

Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define $$g(x) = \min_{1\leq i\leq n} f_i(x).$$ Clearly, $g(x)$ is also a piecewise linear function. What would be ...
0
votes
4answers
82 views

Is it feasible to generate every possible RGB image?

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
1
vote
2answers
55 views

Does having one large L1 cache instead of L1 and L2 cache makes computation faster?

Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?
1
vote
1answer
79 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of ...
10
votes
3answers
1k views

Is there any proof that quantum computers are more efficient than classical computers?

Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also ...
1
vote
1answer
44 views

Can computation models be categorized in terms of efficiency?

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
2
votes
2answers
94 views

Hash table versus binary search lookup for unchanging data

Let's say I have some static, unchanging data (no adds, modifies or deletes) which is looked up by a string value, and that I'm looking to minimize size in memory while also trying to minimize lookup ...
0
votes
1answer
135 views

How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
1
vote
1answer
40 views

How can I compare two different neural networks, from a theorical point of view?

Let's say I have a problem (i.e. Given f(x), find x) and two neural networks(i.e. feedforward and recurrent). I would like to know if one works better than the other one. I could run the twos on a ...
3
votes
1answer
52 views

Constant Shaving on known algorithms

Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving ...
4
votes
2answers
110 views

Practical exponential time algorithms for polynomial-time solvable problems

Inspired by this quote attributed to Alan Perlis: For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run. How I interpret this statement is that ...
2
votes
1answer
148 views

Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input

Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input ...
3
votes
1answer
75 views

Does proving a problem is in P typically mean it will eventually be practically solvable?

I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P ...
5
votes
1answer
73 views

Would you ever use a skip list over a treap?

Skip lists are taught as a standard of the undergrad CS curriculum at many major universities. However, from my reading* I can't find any practical situation where you would use a skip list over a ...
1
vote
1answer
104 views

How to improve the binomial algorithm?

Good evening! I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form: $$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose ...
3
votes
1answer
101 views

Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?

Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?
1
vote
0answers
42 views

Efficiently comparing total values of two unsorted arrays [closed]

The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater? Would be as simple as prefix sum ($O(n)$) for ...
1
vote
0answers
47 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, ...
5
votes
2answers
89 views

Finding the k-th smallest rational number efficiently

Consider the following set: $S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$ $S$ is the set of all rational numbers that can be represented by two integers $a$ ...
0
votes
0answers
11 views

how to calculate the average case efficiency of the improved bubble sort? [duplicate]

I already know that the average case efficiency for this algorithm is: $\Theta(n^2)$. But I want to know how to obtain this result. This is the algorithm that I have: ...
120
votes
10answers
39k views

How can a language whose compiler is written in C ever be faster than C?

Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, ...
2
votes
1answer
88 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also ...
0
votes
0answers
61 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)$. ...
6
votes
2answers
123 views

Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with ...
0
votes
1answer
67 views

Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched ...
0
votes
2answers
392 views

Data structure with constant time operations

I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value ...
4
votes
2answers
144 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will ...
0
votes
1answer
102 views

Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural ...
1
vote
1answer
168 views

Efficient algorithm for conversion of hexadecimal fraction to decimal fraction

Let's say I have some very long hex fraction like this: 0.3F30A21306AEFCBADE3230A593EFAEB395A39E What are some algorithms with an acceptable complexity to ...
5
votes
3answers
433 views

How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem: Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, ...
5
votes
3answers
276 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
0
votes
1answer
240 views

Why is O(n log n) the best runtime there is?

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good. However, there are faster runtimes such as (from now on just assume it ...
2
votes
1answer
67 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
6
votes
3answers
200 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
3
votes
0answers
78 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 ...
5
votes
1answer
121 views

Is it possible to implement a dictionary with efficient access according to insertion order?

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a ...
1
vote
1answer
45 views

Determining most efficient algorithm for a problem [duplicate]

This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some ...
1
vote
1answer
93 views

Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following: Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$. The algorithm I can think of is to remove an ...