Computer Science

Questions tagged [algorithms]

Ask Question

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

9,271 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
1answer
19 views

Assign few binary variables to make all polynomials identically zero

I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$ for any $i \in [1,50]$. I want to assign few variables so that all $f_i$ will be identically zero. ...
6
votes
1answer
5k views

What is an optimal algorithm?

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
0
votes
0answers
21 views

How much faster are out machines (generally) than Arthur C. Clarke's machine in 1953's “The 9 Billion Names of God”?

In Arthur C. Clarke's short story, "The 9 Billion Names of God", two software/hardware engineers are contracted by a monastery to generate 9 billion string permutations from a 13-character ...
1
vote
1answer
42 views

Cashier Scanning Algorithm Problem

I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below. A cashier only has x time to scan a person's goods. The ...
-3
votes
0answers
27 views

parameterized complexity

Given a SAT formula $φ$ where no variable appears negated, decide if there exists a satisfying assignment which sets at most $k$ variables to value 1. Show that this problem can be solved in roughly $...
1
vote
1answer
34 views

Find the recurrence relation for the following algorithm

The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation. \begin{align} &\text{SORT}(A[0\dots n-1])\colon\\ &\quad \text{...
0
votes
1answer
48 views

Efficient way to implement periodic events

I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple ...
2
votes
1answer
46 views

Find a list of actions that result in desired state

I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem. In the system we have a list of actions that a ...
1
vote
2answers
77 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
2answers
95 views

Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$ ...
1
vote
0answers
32 views

Group same objects using multiple stacks

I am trying to write an algorithm to solve the following problem. Let's say we have $n$ (6<=n<=14) buckets each with capacity 4. There would be exactly $n-2$ type of objects. The initial state ...
1
vote
1answer
24 views

Way to solve 5-dimentional Linear assignment problem [closed]

I faced a problem that looks very hard, the problem is this: We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person)...
0
votes
1answer
45 views

Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations. What I'm trying to calculate: I have number of items. Lets call items a1, ...
-3
votes
1answer
19 views

How to simulate two counters using one (FIFO) queue?

How to simulate two counters using one (FIFO) queue? (In terms of algorithms, unary stack.)
1
vote
0answers
14 views

Better version of heavy-light decomposition: always draw path to largest subtree

Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ). The problem: given any tree of size N, find a way to split it into ...
0
votes
0answers
9 views

How to implement the synchronous part of the paper “Concurrent Cycle Collection in Reference Counted Systems”

I have been looking at how to implement this paper, which I've outlined the main algorithm below. This paper is about how to implement reference counting in a way that handles cycles. What I'm ...
1
vote
1answer
46 views

Issue triangulating a font glyph for a specific scenario

I am trying to triangulate TTF glyphs for drawing in opengl. The below image shows an example glyph (Taken fron FontForge application). The X represent control points of a bezier spline, circular and ...
1
vote
0answers
13 views

Measure divergence in Particle Swarm Optimization

I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging. This would be used as one metric to be ...
1
vote
1answer
53 views

Perfect matching problem

Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*...
2
votes
0answers
23 views

Optimal Item Locations given Traversal Paths

I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations. Additionally, I have a ...
2
votes
2answers
112 views

How to find an array of probabilities that give equal products

I'm trying to figure out if there is an algorithm which can solve the following: Given an array of randomly generated values, for example: $$[54.6, 1.96, 5.0, 31.31]$$ Find an array of equal length, ...
1
vote
1answer
86 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
2
votes
3answers
15k 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 ...
0
votes
0answers
22 views

How to known which algorithm is the best for what situation, when sorting numbers?

Is there some kind of "universal list" of performance of different algorithms in different situations? I have different databases that save user input (numbers). However some of these sets ...
4
votes
1answer
48 views

Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
28
votes
7answers
11k views

Generating Combinations from a set of pairs without repetition of elements

I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n). So, if the n is 4, then I have the following pairs: <...
0
votes
1answer
64 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
2
votes
1answer
93 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
0
votes
0answers
29 views

Minimum cost bin assignment

I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
1
vote
1answer
27 views

Number of substrings with exactly k distinct characters

Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
-1
votes
0answers
26 views

W(n) = W(n/2) + W(n/4) + 0.999n

how can you solve W(n) = W(n/2) + W(n/4) + 0.999n using the brick method and get the asymptotic bound? I have no idea where to start.
0
votes
2answers
75 views

Average case running time of quick sort

How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ? Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
1
vote
4answers
105 views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

Suppose there is a polynomial time reduction from problem $A$ to $B$. Why is the following false? If $B$ is NP-hard then $A$ is NP-hard. Can some explain this intuitively?
0
votes
2answers
50 views

Given a sorted array with n integers, how to find the element that has no duplicates?

I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-...
1
vote
0answers
32 views

Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?

The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation. The author then argues that this is ...
0
votes
1answer
26 views

How to work out the odd case?

I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
1
vote
3answers
41 views

Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method. I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
3
votes
0answers
36 views

Hardness of an instance of a problem independent of algorithms?

The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
-2
votes
0answers
80 views

Why do delta x is multiplied in bresenhem line drawing algorithm

In derivation of bresenhem line generation algorithm( https://getsetcg.blogspot.com/2018/10/bresenham-line-drawing-derivation.html?m=1 ) why do they multiplied delta x or in some they use dx to ...
-2
votes
0answers
67 views

Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case runningtime of O(nlogn)

Suppose we have an array A[1 :n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank (A[i]), as the number of elements in A that are strictly smaller than A[i] ...
0
votes
2answers
18 views

Sorting an interval

Given that array has $k$ elements (all distributed uniformly). Its length is exactly $3$ somewhere in $[0, k)$. For example, if $k=100$ then, we have $100$ numbers and they can be in $[10,13)$, but ...
3
votes
1answer
56 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
-1
votes
0answers
32 views

Assignment of Nodes to Multiple Queues

You are given $n$ customers at $n$ nodes and each node is at a variable distance away from all queues. Also each customer is processed in a constant amount of time $c$ when it is in a queue. Assuming ...
23
votes
1answer
967 views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
1
vote
0answers
168 views

Total running time expressed in O notation of a word ladder program all words same length

I am trying to figure out a big O expression for the running time given $V,E,F$ for a word ladder or word chain program that I have written in Java. I am using undirected graphs with BFS. What is ...
1
vote
1answer
68 views

In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?

See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
0
votes
0answers
68 views

$O(n)$ algorithm to find a sequence of 3 or n tennis players with ratings in decreasing/increasing order

This problem is a follow up from this. At a certain (unrealistic) event, we have infinitely many tennis players lined up who are conveniently numbered $(P_1,P_2, \cdots)$. Each player has a certain ...
1
vote
1answer
28 views

Determine saving moves for a checked king

In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and ...

1
2 3 4 5
…
186