All Questions
46,332
questions
0
votes
0
answers
2
views
Valid Arguments
Is the following argument valid? If Helen gets the supervisor’s position, then she’ll buy a new car. She has purchased a new car. Therefore, Helen did get the supervisor’s position.
Consider the ...
- 1
0
votes
0
answers
2
views
Simplifying expressions with justifications (L.M*)*
Try to simplify the following expressions and justify your simplification.
$$
(iii) (L+M^*)^*
$$
$$
(iv) (L.M^*)^*
$$
I think the first one can be simplified as (L+M)* but couldn't figure out the ...
- 55
0
votes
0
answers
6
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 1
0
votes
1
answer
16
views
Is it better to arrange datatypes in a computer programme using arrays or linked lists?
How should datatypes be organised in a computer programme? Is it better to utilise arrays or linked lists? I'm not sure what the difference is, but I seem to recall hearing that arrays are quicker. Or ...
- 11
0
votes
0
answers
4
views
Is there a sorting program or formula to sort and place individuals in classes based on preferences
I am looking for a formula or program to help place people in classes based on their preferences.
The elements of the problem are:
There are 30 class choices a student can pick from.
There are 400 ...
- 1
0
votes
0
answers
7
views
Computational complexity of some optimization problem?
I wonder if there are some methods I can borrow from computational complexity theory to analyze the optimization problem such as a convex optimization problem. An example of this is to find the ...
- 51
0
votes
0
answers
12
views
Complexity of generating all subsets of size $k$ using recursion
What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set?
...
- 123
0
votes
0
answers
8
views
What are the forms of the terms that are in $\twoheadrightarrow^i$ but not $\twoheadrightarrow^i_{||}$ in Lambda Calculus
Let $\rightarrow^{i}$ be the relation of internal reduction of $\lambda$-terms, and $\twoheadrightarrow^i$ its reflexive-and-transitive closure.
And define relations $\rightarrow^{b}_{||}$ and $\...
0
votes
0
answers
13
views
Problems in $DTIME(n\log n)$
Let $DTIME(t(n))$ denote the complexity class of languages solvable in time $O(t(n))$ by a deteministic Turing machine with one tape. By the result of Kobayashi, we know that $DTIME(o(n\log n))=REG$. ...
- 101
0
votes
0
answers
10
views
Finding a ArrayList Connection (representing Subway Lines) with Recursion
I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station):
...
0
votes
0
answers
14
views
Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
- 55
-2
votes
2
answers
31
views
Where do I report a Security Risk if the Corporation Doesn’t Want to Hear It?
How do I communicate a security risk to a social media web site that doesn’t want to hear it?
The web site allows any person to create any number of unverified profiles.
Those unverified profiles ...
-1
votes
0
answers
8
views
design circuit by proteus
Design a circuit by which 3 4-bit numbers B, A and C are added together according to the control signal S and in
If the calculation result exceeds 15, the LED will be turned on as an output (it is ...
1
vote
1
answer
24
views
Counting ways to choose m subarrays which covers whole array
Suppose there is a sorted array of numbers from $1$ to $n$. We have to choose ordered $m$ nonempty subarrays in such a way that every number from $1$ to $n$ belongs to at least $1$ subarray. How many ...
- 11
0
votes
0
answers
4
views
How should one interpret the minhash error rate?
On Wikipedia the error rate for the minhash algorithm vs baseline jaccard similarity is stated as 1/sqrt(1/hashes).
But, how should one interpret this number in a ...
- 101
1
vote
2
answers
46
views
Prove a language created by applying a function on a regular language is regular
Let $L$ be a language over $\Sigma=$ {$a,b,c$}
We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.
Let $T(L)=${$ T(w) : ...
- 304
0
votes
1
answer
18
views
Threads and its priority in Java
I was experimenting with the concept of threading in java, we have a method setPriority, using which we can set thread priority. In official documentation it is given as below,
But while seeing in ...
0
votes
2
answers
37
views
Proving $L=\{wvw|v\in \{0,1\}^*, w\in \{0,1\}^+\}$ is not regular using the myhill-nerode and pumping lemma
Firstly, I've tried assuming $L$ is regular and find a contradiction with help of the pumping lemma's 3 conditions, I was not able to get to a contradiction.
I've tried thinking of a word $z\in \{0,1\}...
- 304
0
votes
0
answers
20
views
What can I read about permutations in 3D space?
I'm interested in the theory of calculating the position of an element when the face of a cube is moved - like in a Rubik's Cup. That is, for example, I rotate the face of the cube - how can I ...
- 111
0
votes
0
answers
18
views
Minimum k-cut with equally weighted sets
I've got a weighted graph $G$, where additionally each vertex has a weight too. For a fixed, given $k$ I am looking for an algorithm to partition $G$ into $k$ disjoint sets of vertices, so that:
The ...
- 1
0
votes
0
answers
12
views
Bellmann Error with Time Step
I define the return $G$ as the discrete time integral of the reward $G = \Delta t \sum_{t = 0, ..., T}r_t$. In supposing $\Delta t = 1$ throughout, my instructor wrote the following formula for the ...
1
vote
0
answers
6
views
Can a CAM-style abstract machine fold a tree? What if it has a second stack?
The title's a little provocative, sorry. In the categorical abstract machines (CAMs), technically there are no "right folds"; the only way to consume a list is from the "left" or &...
- 221
0
votes
0
answers
51
views
Does there exist an FPTAS for bin packing problem?
We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
0
votes
0
answers
8
views
Python | Normalized Vector Based Player Controller
I recently started writing a 3D Engine using the Math Library, and PyGame for Graphics. I've made a simple demo scene, but I would like to make a "First-Person" like Camera Controller.
I've ...
0
votes
0
answers
8
views
How to load an image dataset for deep learning in Python? [closed]
I'm still fairly new to deep learning and I find myself asking a lot of questions in a single day, which can make me feel a bit silly.
I'm encountering an issue while using glob to load images.
I had ...
- 11
0
votes
1
answer
15
views
CDCL SAT solvers and don't cares
Modern CDCL SAT solvers often can return partial assignments where missing literals mean that the value of that variable is not important for the satisfaction of the formula (i.e. it is a don't care).
...
- 448
2
votes
4
answers
52
views
Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?
The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and ...
- 257
-1
votes
0
answers
10
views
Rewriting with http queries and path with caddy server [closed]
1. The problem I'm having:
I want to rewrite an URL who contain http query to another URL who replace the query by a directory.
I have a URL like this:
...
-4
votes
0
answers
19
views
puzzle of breakfast meals in permutation
A computer manager stays at a hostel for three days. The menu for breakfast each day is a choice of one of three types of egg dish, or one of any two types of fish or one type of meat. In how many ...
- 1
1
vote
0
answers
18
views
Finding the shortest path with Bellman-Ford [duplicate]
I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
- 257
0
votes
1
answer
26
views
Let A, B two languages such that A=B does that implies that coA=coB
I'm getting to a problem while studying my computability and complexity exam.
If two languages A and B, such that A=B does that implies that coA=coB?
And in general if two language are describe by ...
- 1
0
votes
0
answers
17
views
What is the space complexity of deterministic real-time context-free languages?
The linear context-free languages are included in NL, and there exist linear languages that are NL-complete. On the other hand, the set of linear deterministic context-free languages is included in L. ...
- 1
0
votes
0
answers
19
views
How to calculate transition areas of biomes in an image
I'm generating biomes for my game and I would like to store them in a single RGB image like the one below. A color hue can then be mapped to an ID through a table lookup. The problem I face is that I ...
- 101
0
votes
0
answers
13
views
Creating a partial order from a total order with a concurrency oracle
My goal is to turn a strict total order of labeled elements into its strict partial order representation, given a concurrency oracle, that tells me, which pairs of labels are concurrent. Auto-...
- 121
0
votes
0
answers
20
views
Does a problem remain tractable If a single discrete variable becomes continuous?
Let $\mathcal{A}$ be a family of integer matrices, $\mathcal{B}$ a family of integer vectors, and $k$ an integer. Define $L(\mathcal{A}, \mathcal{B}, k)$ to be the following family of decision ...
- 5,798
2
votes
0
answers
23
views
Map-like data structure with subsets as keys
I am looking for a map-like data structure with the following properties:
it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime
the ...
- 121
1
vote
2
answers
34
views
If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?
It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).
Someone suggested that this question answers mine, which it doesn't. ...
- 23
2
votes
1
answer
16
views
Partition a family of sets to maximize cumulative overlap and cardinality
My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S_1,\dots,S_m$ which may overlap. The objective is to find a partition of ...
1
vote
0
answers
27
views
Are there any Indicators that this specific Integer Linear Program is solvable in polynomial time
I have a pretty complex problem and I am using a rather complex ILP to solve it. In a special case of the problem the ILP is reduced to the following "simple" ILP. Additionally, I know that ...
- 225
-2
votes
0
answers
37
views
Stuck in problem about DP on trees
Given a tree T where every vertex is assigned a label which is a positive integer, describe an algorithm to find the largest rooted minor that is a minimum heap. A rooted minor of a rooted tree T is ...
0
votes
3
answers
42
views
How is a direct address table different from an array?
I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)
- 159
0
votes
1
answer
66
views
Ackermann Decision Problem
I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version.
With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem"
...
- 143
1
vote
1
answer
42
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
0
votes
1
answer
53
views
Possible reduction from SUBSET-SUM
Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$.
Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
1
vote
0
answers
40
views
Reconstructing a string from two its partitions into substrings of varying size
Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice.
Under an ...
- 151
0
votes
1
answer
30
views
Does a non-deterministic Turingmachine reach every possible result?
I have problems to imagine a non-deterministic Turingmachine.
Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether ...
1
vote
0
answers
21
views
SMT solver gives up on seemingly trivial problem
I expected CVC5 to produce a proof given the following problem in TPTP format.
Why does CVC5 give up on the TPTP problem, but works just fine on the same problem given in SMT-LIB2?
In human words, the ...
- 11
-1
votes
0
answers
18
views
Learning Parities via Gradient Descent
[Disclaimer: Crossposted in cstheory --> Link]
In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [...
0
votes
0
answers
9
views
Is there a way to modify the DK Test for DCFGs to test for ambiguity of CFGs?
I am currently reading Sipser's book on the Theory of Computation, and was wondering about the the question in the title.
Here is my current understanding of the concepts:
A deterministic context free ...
- 1
0
votes
3
answers
69
views
Details of sqrt.c library source code
Have seen library code for finding square-root, using the Newton Raphson method.
It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity ...
- 155