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
1answer
98 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 ...
1
vote
1answer
50 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
145 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
57 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
93 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
33 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
48 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 ...
4
votes
2answers
56 views

Limiting memory usage while keeping score

For an assignment we are asked the following(simplified) : A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is ...
1
vote
1answer
58 views

What sorting algorithm should be used for this array?

I am given an array {1, 2, 3, 5, 4, 6} and I am asked What sorting algorithm might you want to use to sort the given list, and why? Initially I think using ...
3
votes
0answers
52 views

Can someone help me make this branch and bound algorithm more efficient for a large input?

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the coursera discrete optimisation course) I tried implementing dynamic programming first, and that worked ...
1
vote
1answer
29 views

Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$

Let $n > 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by $$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod ...
1
vote
0answers
33 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 ...
5
votes
5answers
2k views

What is the best solution to find whether the sum of an array is even or odd

I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really ...
6
votes
4answers
168 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...
-1
votes
1answer
44 views

Why do computers use binary, instead of ternary, or some other logic system? [duplicate]

In binary a unit (bit), can store 2 separate values. if you have ternary, then a unit can store 3 separate values. why then don't computers use higher bases, for example in ternary you could have 3 ...
3
votes
1answer
78 views

Efficient way to calculate sum in sliding window?

Assume you have a grid as below: The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the ...
4
votes
3answers
896 views

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

I fail to understand why cut off value would be system dependent, and not a constant. From Princeton University website Cutoff to insertion sort. As with mergesort, it pays to switch to ...
5
votes
1answer
184 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
7
votes
3answers
580 views

Can a Minimum Possible Efficiency be proven?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be? For example, lets take the problem of sorting an array. Many of the ...
4
votes
4answers
169 views

How again do certain sorting methods use $o(n \log n)$ time?

I hope this question isn't too 'soft' for here. It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this ...
1
vote
0answers
29 views

Efficient flood filling (seed filling)

I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) ...
1
vote
2answers
1k views

Brute force method to solve the 0-1 knapsack problem

I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following: If the brute force ...
7
votes
1answer
240 views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
1
vote
1answer
30 views

Efficient Array Normalization

I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this? The runtime I ...
1
vote
1answer
133 views

RMQ with $O(\sqrt{n})$ space?

I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that ...
2
votes
1answer
83 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
2
votes
0answers
47 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 ...
5
votes
1answer
167 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 ...
1
vote
2answers
93 views

Can you explain this improvement to this frequency distribution algorithm?

I came across the following in a text book: Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from ...
1
vote
1answer
95 views

Example algorithms for first class in programming for EE students [closed]

I am professor of Electrical Engineering who will teach, for my first time, a class to first-year EE students about programming. This will be their first contact in an academic setting with ...
0
votes
2answers
57 views

Greedily Schedule Events based on value/hours

Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts ...
1
vote
2answers
119 views

directed graph data structure with fast in/out neighbor query

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all ...
2
votes
2answers
115 views

How to filter a very, very large file

I have a very large unsorted file, 1000GB, of ID pairs ID:ABC123 ID:ABC124 ID:ABC123 ID:ABC124 ID:ABC123 ID:ABA122 ID:ABC124 ID:ABC123 ID:ABC124 ID:ABC126 I would like to filter the file for ...
2
votes
1answer
273 views

Can we create binomial heaps in linear time?

I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take ...
9
votes
3answers
2k 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 ...
2
votes
1answer
302 views

What is a suitable data structure in this scenario?

I need an efficient data structure for maintaining a set of values. Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches ...
-1
votes
1answer
75 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
136 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
353 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
237 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
396 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
441 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
198 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
2k 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
62 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
1k 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 of a sub-array is to XOR all the numbers of that sub-array. An array ...
3
votes
2answers
199 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
192 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 ...
25
votes
8answers
3k 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 ...
14
votes
3answers
11k 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 ...