Questions tagged [sets]

Question 1

This problem is based on https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/description/ : Given an array arr of positive integers, consider all binary trees such that: Each node has ...

Question 2

Imagine I know a vocabulary of 10 words in any language. I also have a large corpus of sample sentences that are broken into words. I’d like to efficiently look up all sentences in my corpus that only ...

Question 3

Consider the following four strings of text: Alabama Alaska Arizona Arkansas These strings of text represent four names for four different states within the United States of America. Suppose that we ...

Question 4

I was tasked to discuss Reflexive Closure, in relation to computer science. In Discrete Mathematics context, its basically a set that relates to an element itself. But I just can't find any ...

Question 5

I'm rather stuck with the example of proof by coinduction, as generally known the principle is written as: $$ P\subseteq F(P)\implies P\subseteq \nu F $$ in an old problem When can the coinduction ...

Question 6

We are currently learning derandomization, which aims to transfer a probabilistic proof into a deterministic algorithm. My problem is as follows. Given $n$, constructs in time polynomial in $n$, a ...

Question 7

Given many sets, what algorithm finds the minimum set(s) of members present in all those sets? For example, given these sets: {1,2} {1,2,44} {2,5,6} {5,6} The ...

Question 8

I studied a definition for time complexity: Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be: for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural ...

Question 9

Say I have an array that goes like [ a, c, b, d ] and I want it rearranged as [ d, c, a, b ]. The only type of change I'm allowed to make is plucking an element from one place and inserting it into ...

Question 10

Let there be "N" bits. We want to rank and unrank a specific subset of bit combinations based on the following criteria - ...

Question 11

Question: I have a proof which overwhelmingly feels like it's a proof "by coinduction." Unfortunately I can't coinduct my way out of a paper bag, so I don't know if this actually works. I ...

Question 12

Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...

Question 13

Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N. Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n? I read somewhere (without ...

Question 14

If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two ...

Question 15

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...

Stack Exchange Network

Questions tagged [sets]

Unordered Variant of "Minimum Cost Tree From Leaf Values"

Efficient “sentence” lookup by set of “words”

Intersections of Sets of Strings (Alabama, Alaska, Arizona, Arkansas)

What's the real life uses of Reflexive Closure in computer science?

Question regarding coinduction

Construction of a polynomial time algorithm

How to find the minimum set of members of many sets

Definition feels contradictory (Computational Complexity Theory)

Is there an algorithm for rearranging a set in a specific way while optimizing for minimum amount of moves?

Binary subset rank and unrank

Can you make the following "coinductive" proof precise?

Is this intersection set problem NP-Hard?

Decide whether this Problem NPC or P?

Given two sets of integers find an integer in the first set furthest away from all members of the second set

Cardinalities in set coverings

Hot Network Questions