# Questions tagged [algorithms]

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.

11,333 questions
Filter by
Sorted by
Tagged with
37 views

### Find combination of elements, one element from each list, whose average is the closest to a target number

Problem: There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1. The lists have equal length. There is a target number T. Find what is the combination of elements, one element from each ...
123 views

### What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
14 views

### How to choose cells from a table to maximize their sum, with selection constraints?

I have a table of fixed positive integer values of anything up to several dozen. There are six columns and several hundred rows. I must choose exactly two values from each column, and zero or one ...
27 views

### Is minimum interval hitting problem NP-HARD?

Consider this problem: We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
8 views

### The Multi-Room Muddy Forehead Puzzle with Varied Color Perception

Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
38 views

### Which algorithms could be suitable for solving my disjunctive programming problem?

Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
33 views

### Given a population, find the boolean algebra expressions that most closely evaluate to that population

TL;DR I have some ideas but am curious to know if there are existing proofs, research, etc. in this area that I can use to guide my algorithm development. Problem summary We have a population where ...
123 views

### Minimum number of comparisons to find $2$nd smallest element

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.)  I tried but I have no idea how to, e....
25 views

### ir - Using document-term [Boolean] incidence matrix for answering a query

The book "Introduction to Information Retrieval" talks about term-document incidence matrix for retrieving documents that contain/not-contain certain tokens drawn from a query. This ...
41 views

### finding the length of the GCD of two strings

Let's say you have two strings: a and b with GCD c. Why is it that ...
54 views

### Optimizing findMissingNumber algorithm to O(N)

This problem is from Cracking the Code Interview: An array A contains all the integers from Oto n, except for one number which is missing. In this problem, we cannot access an entire integer in A ...
121 views

### How to identify Dominant terms in big-O notation and understand Time Complexity of an algorithm?

I understand that Time Complexity is the measure of how an algorithm scales with respect to the input size. Let us say an algorithm is having a runtime of O($3^n$) + O($n^{20}$) In order to identify ...
49 views

### Algorithm to generate all N-size variations of natural numbers

For a size N>=1 (an input variable) I need an algorithm to generate all variations (no duplicates allowed) of natural numbers greater than zero. For N=1, this is trivial: ...
1 vote
61 views

### Is variable a constant or a parameter

I am working on the $[1,j]$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W-hard for the parameter ...
22 views

27 views

### Minimum set cover problem and dual, the maximum set packing

Just like in This thread that was posted here before, I came upon the same issue where I do not understand how are the relaxed maximum set packing problem and the minimum set cover problem are dual to ...
58 views

### Efficient way of exploiting many symmetries

I have a problem domain that has several kinds of symmetries. I will try to keep this as general as possible. Given an array of strings: ["4533", "1234", ...] The two symmetries ...
40 views

### Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
91 views

### Harder variation of light bulb problem (solvable in O(n log n)?)

Problem originally from: https://train.nzoi.org.nz/problems/1311 Every light-bulb is initially off, and O(N^2) solutions are too slow. Emma is a massive nuisance at school by always meddling around ...