Recent Questions - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2022-05-22T23:58:58Z https://cs.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/151777 0 Proving transitivity in an intuitionistic type theory without the K rule A confused dove https://cs.stackexchange.com/users/150927 2022-05-22T23:45:01Z 2022-05-22T23:45:01Z <p>In Agda, if I disable axiom <span class="math-container">$\mathbb{K}$</span> I'm not able to prove <span class="math-container">$$\forall\{A : \textbf{Set}\}\{a\ b : A\}\{p\ q : a \equiv b\} \to p \equiv q,$$</span> which I guess is normal since the system does not truncate equalities. However, I'm still able to prove transitivity <span class="math-container">$$\forall \{A : \textbf{Set}\}\{a\ b\ c : A\} \to (b \equiv c) \to (a \equiv b) \to (a \equiv c)$$</span> by pattern matching on <span class="math-container">$\textit{refl}$</span>s, i.e. <span class="math-container">$\textit{trans }\textit{refl }\textit{refl} = \textit{refl}$</span>. Am I missing something obvious here? What axiom is the system applying to assume the path is the reflexivity path (is it axiom <span class="math-container">$\mathbb{J}$</span>?)? Thanks in advance.</p> https://cs.stackexchange.com/q/151776 0 Models of computation and cardinality Enk9456 https://cs.stackexchange.com/users/150926 2022-05-22T23:17:48Z 2022-05-22T23:17:48Z <p>In university, I was taught the computational model hierarchy given in the following figure: <a href="https://devopedia.org/images/article/210/7090.1571152901.jpg" rel="nofollow noreferrer">https://devopedia.org/images/article/210/7090.1571152901.jpg</a></p> <p>Essentialy, Pushdown Automata (PA) can solve more problems (i.e. recognize more languages) than Finite State Machines (FSM), Turing machines (TM) can solve more problems than PA etc. To continue, suppose <span class="math-container">$s(FSM), s(PA), s(TM)$</span> denotes the set of problems solved by FSMs, PAs and TMs, respectively. Then, the figure states that: <span class="math-container">$s(FSM) \subset s(PA) \subset s(TM)$</span></p> <p>However, I have a confused argument regarding the cardinality of the above sets.</p> <ol> <li>All sets of computational models (e,g, FSMs, PAs and Tms) are countably infinite. Because all can be represented as computer programs in binary string form, which are also countably infinite.</li> <li>If FSMs are countably infinite, then the problems that can be solved with FSMs, <span class="math-container">$s(FSM)$</span>, cannot be more than countably infinite. The same is true for <span class="math-container">$s(PA)$</span> and <span class="math-container">$s(TM)$</span>.</li> <li>Countably infinite sets have cardinal number <span class="math-container">$\aleph_0$</span> (aleph zero). Thus if <span class="math-container">$C(.)$</span> denotes cardinality, <span class="math-container">$C(s(FSM)) = C(s(PA)) = C(s(TM) = \aleph_0$</span>.</li> </ol> <p>Is the above argument correct? If it is true and the above sets have the same cardinality, in what sense is the figure (which states that <span class="math-container">$s(FSM) \subset s(PA) \subset s(TM)$</span>) true?</p> <p>The only hypothesis I can think of is an argument of &quot;redundancy&quot;. That is that while there is an equal number of TMs and FSMs, the same is not true for the problems that can be solved with these. That would mean that that many FSMs solving the exact same problem is common, while many TMs solving the same problem is less frequent. Thus, more problems can be solved with TMs than can be with FSMs. Stated differently, the set of problems solved by TMs is greater than the problem set solved by FSMs. However, both problem sets are infinite and there is no infinity smaller than <span class="math-container">$\aleph_0$</span>, so the two problems sets should have the same cardinality <span class="math-container">$\aleph_0$</span></p> https://cs.stackexchange.com/q/151775 0 computer has the following opcodes in the instruction set, find out in binary, the instruction that will carry out the calculation : User_New2021 https://cs.stackexchange.com/users/147348 2022-05-22T22:18:09Z 2022-05-22T22:18:09Z <p>A hypothetical simple computer has the following opcodes in the instruction set, each of which takes two operands that are given in the next 2 bytes :</p> <p>00 ADD (OP1 + OP2)</p> <p>01 SUBTRACT (0P1 - OP2)</p> <p>10 MULTIPLY (OP1 × OP2)</p> <p>11 DIVIDE (OP1 ÷ OP2)</p> <p>Write, in binary, the instruction that will carry out the calculation 46×75.</p> <p><strong>My approach :</strong></p> <p>46×75 = 3450 = 110101111010 in Binary.</p> <p>So,</p> <p>110101111010 = (11)(01)(01)(11)(10)(10)</p> <p>= DIVIDE (OP1 ÷ OP2) SUBTRACT (0P1 - OP2) SUBTRACT (0P1 - OP2) DIVIDE (OP1 ÷ OP2) MULTIPLY (OP1 × OP2) MULTIPLY (OP1 × OP2) ---(ANSWER)</p> <p>Did I do correctly? If yes, then please let me know. If I did it wrong then please correct me where did I do wrong or leave some hints.</p> <p>Thank you very much.</p> https://cs.stackexchange.com/q/151769 0 Are all Scott-continuous functions computable? Jozef Mikušinec https://cs.stackexchange.com/users/71063 2022-05-22T18:50:56Z 2022-05-22T18:51:25Z <p>A chain-complete partial order (equivalently, a pointed dcpo) is a set <span class="math-container">$D$</span> with a partial order <span class="math-container">$\leq$</span> such that all chains of <span class="math-container">$D$</span> have a supremum. The least upper bound (<span class="math-container">$\bigsqcup$</span>) of the empty chain is the least element <span class="math-container">$\bot$</span> of the CCPO.</p> <p>A function <span class="math-container">$f\colon M \to N$</span> is monotone if for all <span class="math-container">$a, b \in M$</span>, the following holds: <span class="math-container">$$a \leq b \implies f(a) \leq f(b)$$</span></p> <p>A function <span class="math-container">$f\colon M \to N$</span> between two CCPOs is Scott-continuous if it is monotone and for every chain <span class="math-container">$C$</span> of <span class="math-container">$M$</span>, we have</p> <p><span class="math-container">$$f(\bigsqcup_{c \in C} c) = \bigsqcup_{m \in C} f(c)\,.$$</span></p> <p>Scott-continuous functions play an important part in defining denotational semantics of programs, and as is well-known in computing science, every Turing-computable function is Scott-continuous<span class="math-container">$^0$</span>. Is the converse true? Is every Scott-continuous function computable?</p> <hr /> <ol start="0"> <li>See <a href="https://cs.stackexchange.com/q/80978/71063">this question</a>, from which I took and edited some definitions.</li> </ol> https://cs.stackexchange.com/q/151767 0 How does CPU determine Reserved Exponent cases? uptoyou https://cs.stackexchange.com/users/150920 2022-05-22T15:14:23Z 2022-05-22T20:33:51Z <p>Using IEEE 754 algorithm i assume, that it can be implemented in a branchless way.</p> <p>But how does CPU determine special cases (Reserved Exponent values):</p> <div class="s-table-container"> <table class="s-table"> <thead> <tr> <th>Exponent</th> <th>Significand</th> <th>is</th> </tr> </thead> <tbody> <tr> <td>11111111</td> <td>000000000...</td> <td>Inf</td> </tr> <tr> <td>11111111</td> <td>00000<strong>1</strong>000...</td> <td>NaN</td> </tr> <tr> <td>00000000</td> <td>000000000...</td> <td>0</td> </tr> <tr> <td>00000000</td> <td>00000<strong>1</strong>000...</td> <td>Subnormal</td> </tr> </tbody> </table> </div> <p>Without any tricks which i don't know / understand it should be expensive.</p> <p><strong>EDIT</strong></p> <p>It was too big for comment, so editing source question:</p> <p>I'm currently reading ARM spec/documentation <a href="https://developer.arm.com/documentation/ddi0403/d/Application-Level-Architecture/Application-Level-Programmers--Model/The-optional-Floating-point-extension/Floating-point-data-types-and-arithmetic?lang=en#BEIBFIBJ" rel="nofollow noreferrer">https://developer.arm.com/documentation/ddi0403/d/Application-Level-Architecture/Application-Level-Programmers--Model/The-optional-Floating-point-extension/Floating-point-data-types-and-arithmetic?lang=en#BEIBFIBJ</a> and especially interesting part is <code>FPUnpack()</code> pseudocode. If i understand correctly, CPU doesn't have intrinsics / instructions for special cases, but the compiler, that produce machine code should consider to validate result from registers (FVP for old ones and NEON for new). The example i found from ARM team <a href="https://github.com/ARM-software/ComputeLibrary/blob/8f587de9214dbc3aee4ff4eeb2ede66747769b19/include/CL/cl_half.h#L135" rel="nofollow noreferrer">https://github.com/ARM-software/ComputeLibrary/blob/8f587de9214dbc3aee4ff4eeb2ede66747769b19/include/CL/cl_half.h#L135</a>. Am i right ?</p> <p><strong>EDIT:</strong></p> <p>Nope, i'm not right, according to this answer <a href="https://stackoverflow.com/questions/61646510/how-does-the-cpu-cast-a-floating-point-x87-i-think-value">https://stackoverflow.com/questions/61646510/how-does-the-cpu-cast-a-floating-point-x87-i-think-value</a>.<br /> But it's still the question how does CPU registers handle special cases...</p> https://cs.stackexchange.com/q/151766 1 Is there a pseudopolynomial time algorithm for this subset sum variant? Erel Segal-Halevi https://cs.stackexchange.com/users/1342 2022-05-22T14:15:16Z 2022-05-22T14:15:16Z <p>The subset sum problem is: given a list of <span class="math-container">$n$</span> positive integers, and a positive number <span class="math-container">$T$</span>, find a sub-list with largest sum that is at most <span class="math-container">$T$</span>. The problem can be found in time polynomial in <span class="math-container">$n$</span> and <span class="math-container">$T$</span> by dynamic programming: for each integer between <span class="math-container">$1$</span> and <span class="math-container">$T$</span>, record whether or not there is a subset with this sum.</p> <p>Consider the following variant. There is a function <span class="math-container">$f$</span>, and the goal is to find a sub-list <span class="math-container">$L$</span> for which the sum <span class="math-container">$\sum_{x\in L} f(x)$</span> is largest subject to <span class="math-container">$\sum_{x\in L} f(x) \leq f(T)$</span>. Now, the dynamic programming approach does not work as before, since the partial sums are not integers. They may even be irrational, e.g. if <span class="math-container">$f$</span> is the square-root function. Note that, even with irrational <span class="math-container">$f$</span>, the problem is still finite since there are <span class="math-container">$2^n$</span> sub-lists overall.</p> <p>Is it possible to solve the problem in time <span class="math-container">$O(poly(n,T))$</span>?</p> https://cs.stackexchange.com/q/151764 0 connection between self reducibilty and the hardness of the dicison problem AllForCode https://cs.stackexchange.com/users/149440 2022-05-22T13:15:49Z 2022-05-22T13:15:49Z <p>If given that a search problem R is self-reducible, thus we can solve it in polytime steps by (the optional ability of) asking its corresponding decision problem Sr, can I say something regarding the hardness of Sr?</p> <p>if Sr is in P, there is no need for self-reduction to solve R. So I know Sr is NP, NPC, or CO-NP. I'm trying to think of ways but couldn't think of a connection between the fact of self-reducibility and the hardness of Sr.</p> <p>would love to hear your thoughts regarding this.</p> https://cs.stackexchange.com/q/151763 1 A small issue regarding the proof of Savitch's Theorem Benicio Agüero https://cs.stackexchange.com/users/85646 2022-05-22T11:13:02Z 2022-05-22T13:49:13Z <p><a href="https://en.wikipedia.org/wiki/Savitch%27s_theorem" rel="nofollow noreferrer">Savitch's Theorem</a> states that <span class="math-container">$NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$</span> for any <span class="math-container">$f\left(n \right) \in \Omega \left( \log{n} \right)$</span>.</p> <p>The proof I am familiar with states the following: we are given a non-deterministic turing machine <span class="math-container">$N$</span> for our language <span class="math-container">$A$</span>. It is known that for inputs in <span class="math-container">$A$</span> that <span class="math-container">$N$</span> accepts by using <span class="math-container">$O\left( f \left( n \right)\right)$</span> space. I would like to construct a deterministic turing machine <span class="math-container">$M$</span> that accepts inputs from <span class="math-container">$A$</span> in <span class="math-container">$O\left( \left( f \left( n \right)\right) ^2 \right)$</span> space, and this will prove the correctness of the theorem.</p> <p>Knowing that <span class="math-container">$s,t-Path$</span> is in <span class="math-container">$DSPACE\left( \left(\log{n} \right)^2\right)$</span>, we define the (deterministic) turing machine <span class="math-container">$M$</span> to work the following way (on a given input <span class="math-container">$a$</span>:</p> <ol> <li>Construct the configuration graph for the computation of <span class="math-container">$N$</span> on <span class="math-container">$a$</span>.</li> <li>Run a space-efficient algorithm for <span class="math-container">$s,t-Path$</span>, where <span class="math-container">$s$</span> is the initial configuration and <span class="math-container">$t$</span> is the accepting configuration (assume, w.l.o.g., only one accepting configuration exists. If not, adjust <span class="math-container">$N$</span> accordingly so it will hold).</li> <li>If such a path was found, accept. Else, reject.</li> </ol> <p>Phase (2) takes <span class="math-container">$O\left( \left(\log{n} \right)^2\right)$</span> space. But what about phase (1)? How Am I to construct the configuration graph, which has <span class="math-container">$\Theta \left( 2^{O\left( f \left( n \right) \right)} \right)$</span> vertices, in only <span class="math-container">$O\left( \left(\log{n} \right)^2\right)$</span> space?</p> <p>I read that the graph can be built on the fly, but then - how do we check whether an edge exists? If the graph itself is not fully computed ahead of time, we must always call to <span class="math-container">$N$</span> to check what are the destination configurations from our current configuration. Now, this gets a bit tricky, as <span class="math-container">$N$</span> is not part of the input. Should we assume we can somehow approach it? Without taking time? Where is <span class="math-container">$N$</span> maintained? This takes space as well.</p> <p>I am aware my question is not the main focus of the theorem, but its something that bugs me in this proof. Or are there better proofs? (Also, how can this small issue be better explained, in this proof?)</p> https://cs.stackexchange.com/q/151762 -1 proof that Turing machine L' NOT BELONGS TO RE none https://cs.stackexchange.com/users/150912 2022-05-22T10:34:44Z 2022-05-22T10:34:44Z <p>L = { 〈M1, M2〉 | M1, M2 are Turing machines and L(M1) ∩ L(M2) ≠ ∅ }</p> https://cs.stackexchange.com/q/151761 1 Papadimitriou's pseudopolynomial algorithm for m x n integer program with fixed m Rodrigo https://cs.stackexchange.com/users/40409 2022-05-22T09:59:55Z 2022-05-22T18:00:46Z <p>Consider the following proof from Papadimitriou's &quot;On the Complexity of Integer Programming&quot;:</p> <hr /> <p><strong>Corollary 1.</strong> There is a pseudopolynomial algorithm for solving m x n integer programs, with fixed m.</p> <p><strong>Proof.</strong> We can solve the m x n integer program Ax = b by dynamic programming, proceeding in stages. At the jth stage we compute the set <span class="math-container">$S_j$</span> of all vectors <span class="math-container">$v$</span> that can be written as <span class="math-container">$v = \sum_{i = 1}^J v_ix_i$</span>, with <span class="math-container">$v_i$</span> the ith column of <span class="math-container">$A$</span> and with the <span class="math-container">$x_i$</span> in the range <span class="math-container">$0 \le x_i \le B$</span> where <span class="math-container">$B = n(ma)^{2m+1}$</span>. Since the <span class="math-container">$S_J$</span> cannot become larger than <span class="math-container">$(nB)^m$</span>, the whole algorithm can be carried out in time <span class="math-container">$O((nB)^{m+1}) = O(n^{2m+2} (ma)^{(m+1)(2m+1)})$</span>, a polynomial in <span class="math-container">$n$</span> and <span class="math-container">$a$</span> if <span class="math-container">$m$</span> is fixed.</p> <hr /> <p>I think <span class="math-container">$|S_J| \le (nB)^m$</span> since there are at most <span class="math-container">$nB$</span> vectors of the form <span class="math-container">$v_ix_i$</span>. In the worst case, the sums of <span class="math-container">$m$</span> of them are all distinct. Thus, we would have <span class="math-container">$(nB) \cdot \ldots \cdot (nB) = (nB)^m$</span> possible outcomes.</p> <p>But why does the &quot;dynamic programming&quot; algorithm run in <span class="math-container">$O((nB)^{m+1})$</span>? In particular, should I not count the complexity of each operation (addition, multiplication, etc) involved?</p> <p>It seems that there is missing information since in <a href="https://arxiv.org/pdf/1707.00481.pdf" rel="nofollow noreferrer">later papers</a> citing this work, an explanation is given based on maximum weight path problems, but the obtained bound is not exactly the same (it is equivalent).</p> https://cs.stackexchange.com/q/151759 0 Lower bound union of a unsorted array with sorted array roxot22840 https://cs.stackexchange.com/users/150911 2022-05-22T09:28:52Z 2022-05-22T09:38:32Z <p>I read <a href="https://cs.stackexchange.com/questions/151757/lower-bound-union-of-a-sorted-array-and-unsorted-array">this link</a> and I have similar question.</p> <p>Suppose given two Arrays <span class="math-container">$A$</span> that is sorted array with length <span class="math-container">$n$</span> and <span class="math-container">$B$</span> unsorted array with length <span class="math-container">$n$</span>. We want to find union of two arrays (i.e. we try to compute <span class="math-container">$A\cup B$</span>) with comparison computation model. Can we claim that the lower bound of this problem is <span class="math-container">$\Omega(n\log n)$</span>?</p> https://cs.stackexchange.com/q/151757 0 Lower bound union of a sorted array and unsorted array jhjhb https://cs.stackexchange.com/users/150893 2022-05-22T06:16:40Z 2022-05-22T06:16:40Z <p>Suppose given two arrays <span class="math-container">$A$</span> and <span class="math-container">$B$</span> with length <span class="math-container">$n$</span>. Array <span class="math-container">$A$</span> is sorted and <span class="math-container">$B$</span> is unsorted. Is there any lower bound for computing <span class="math-container">$A\cup B$</span>?</p> https://cs.stackexchange.com/q/151756 0 Modification on Boyer Moore Algorithm jhjhb https://cs.stackexchange.com/users/150893 2022-05-22T05:35:11Z 2022-05-22T06:02:30Z <p>Suppose given array of numbers with length <span class="math-container">$n=3^k$</span>, we try to find an element that occurs more than <span class="math-container">$\frac{n}{3}$</span>. So work as follow:</p> <blockquote> <p>we divide our arrays into <span class="math-container">$\frac{n}{3}$</span> partitions. we find recursively a candidate <span class="math-container">$x$</span> in each partition and we do a scan on array to find number of occurrence of each candidate and then we return maximum of those three candidate.</p> </blockquote> <p>Can we claim that above algorithm work correctly? What is running time of this idea?</p> <p>I think this is a version of <a href="https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm" rel="nofollow noreferrer">Boyer Moore Algorithm</a> that divide our input into three sections. But I can't prove that. Also I think this algorithm runs in <span class="math-container">$O(n\log n)$</span> because <span class="math-container">$T(n)=3T(\frac{n}{3}) +O(n)=O(n\log n)$</span>.</p> https://cs.stackexchange.com/q/151754 0 Optimal greedy algorithm solution for cell tower placement Andrew Kim https://cs.stackexchange.com/users/150905 2022-05-22T00:24:20Z 2022-05-22T04:17:12Z <p>Supose we have <span class="math-container">$n$</span> customers with interval that represent their range. For example, <span class="math-container">$[1,8], [2,5], [4,6], [1,9]$</span> for each customer. For a customer to have range coverage, a tower must be present within their range. For example, for customer <span class="math-container">$[1,8]$</span> to have coverage, a tower must be within range <span class="math-container">$[1,8]$</span>. I need to make a greedy algorithm that will generate a list of tower locations that will cover all customers with the least number of towers. For the example above, the optimal solution will be location 4 or location 5 because only one tower at either location 4 or 5 will cover all customers. The algorithm should have a worst-case runtime of <span class="math-container">$O(n\log n)$</span>.</p> <p>I have tried the following method and failed. First, calcuate the length of each interval and make a tuple of (starting point, length) and add it to a array in assending order in respect to length. So, for the example above the list will look like <span class="math-container">$[(4,2), (2,3), (1,7), (1,8)]$</span>. This will take <span class="math-container">$O(n)$</span> time to process. Second, I picked the customer with the smallest interval and tried to place a tower in the customer's interval. However, a problem rises, because greedy algorithms do not calcuate multiple options and then choose the optimal choice I have trouble of where to place the tower in the customer's interval. I have thought of three choices: at the very left, at the very right, at the middle. The middle, is statistically the most optimal one but not always correct because if the customer's interval is at the boundary and every other customer's interval starts at the very right point of the current customer's interval, the very right point is the right choice for this situation.</p> <p>Any help for finding the optimal solution will be very helpful.</p> https://cs.stackexchange.com/q/151753 0 Heap sort worst case gianluigi https://cs.stackexchange.com/users/135459 2022-05-21T23:57:37Z 2022-05-22T21:38:30Z <p>I am really confused about this. I am trying to prove that the worst case of heap sort is Ω(nlogn) but i don't even know how to start.</p> https://cs.stackexchange.com/q/151751 1 Envyless location using divide and conquer Andrew Kim https://cs.stackexchange.com/users/150905 2022-05-21T23:04:14Z 2022-05-22T13:45:21Z <p>We have a cake of length <span class="math-container">$n$</span> and we have two arrays <span class="math-container">$A$</span> and <span class="math-container">$B$</span> of size <span class="math-container">$n$</span>. The two arrays have order like below. <span class="math-container">$A&lt;A&lt;\dots &lt;A[n]$</span>, <span class="math-container">$B&gt;B&gt;\dots &gt;B[n]$</span>. We define a envyless location as a cut in the cake where it satisfies <span class="math-container">$A[i]=B[i]$</span>. For example, <span class="math-container">$A=[1,2,3,4,5,6,7]$</span> and <span class="math-container">$B=[7,6,5,4,3,2,1]$</span>, <span class="math-container">$A=B=4$</span>, therefore, cutting the cake at length 4 makes the cut envyless. If the algorithm finds an envyless location it returns it's location, and if the envyless location does not exist, it returns null. I am trying to use divide and conquer to solve this problem with worst-case runtime of <span class="math-container">$O(\log n)$</span>.</p> <p>I have tried the following procedure and failed. First, divide the cake in half. Find the mid point of the splitted cake and compare <span class="math-container">$A[mid]$</span> and <span class="math-container">$B[mid]$</span>. If found, terminate and return the location. If not found, keep on dividing and comparing.<br /> I expected this to run on <span class="math-container">$O(\log n)$</span> time but it cannot because for example, if <span class="math-container">$A=[1,2,3,4,5,6]$</span> and <span class="math-container">$B=[20,11,9,8,7,6]$</span>, the envyless location is at location 6, and the algorithm needs to do <span class="math-container">$n$</span> comparison, making the algorithm to run at <span class="math-container">$O(n\log n)$</span>.</p> <p>Any help will be very helpful.</p> https://cs.stackexchange.com/q/151750 0 Universal family of hash functions — dependent on table size? blox2212 https://cs.stackexchange.com/users/150902 2022-05-21T20:38:16Z 2022-05-22T21:38:17Z <blockquote> <p>Given the following family of hash functions:</p> <p><span class="math-container">$$\mathbb{H} = \{h_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \},$$</span> where <span class="math-container">$m$</span> is the key size.</p> <p>Prove that <span class="math-container">$\mathbb{H}$</span> is not a universal family of hash functions.</p> </blockquote> <p>So I got the following idea:</p> <p>If <span class="math-container">$m = 12$</span> then <span class="math-container">$H$</span> is not an universal family of hash functions. But is this enough or have I to prove it for every/random m?</p> <p>This leads to the question: Is a universal family of hash functions dependent on the hash table size?</p> https://cs.stackexchange.com/q/151747 0 Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B user3917631 https://cs.stackexchange.com/users/150898 2022-05-21T16:57:07Z 2022-05-22T09:24:35Z <p>I've been given the question in the title:</p> <p>Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in it that the amount of lexicographic smaller string from A in the structure equals the amount of lexicographic larger string from B, in time complexity O(|Smax|) (the size of longest string in the structure).</p> <p>I should solve it using simple trie trees. My idea was saving in every intersection in the tree the amount of leaves in the sub tree from group A and group B (two different variables).</p> <p>But that doesn't seem to be enough because I wasn't able to build a search algorithm with this data that works within the time complexity, there are certain cases I cannot definitively choose whether to proceed from current intersection with letter x or letter x+1 because the difference between the smaller leaves in A and larger leaves in B is 1 and the string could exist in the sub tree of letter x or x+1 (depends on the inner order in these sub trees).</p> <p>Would really appreciate any help with this.</p> https://cs.stackexchange.com/q/151729 0 What can be the topic of my assignment for presentation about overall computing performance? AHF https://cs.stackexchange.com/users/21507 2022-05-20T22:41:19Z 2022-05-22T23:10:47Z <p>I have received the below question for presentation. It was random assignment, its not my field. What is this specifically in Computer Architecture?</p> <blockquote> <p>how CPU and GPU architecture, memory bandwidth/interfaces, and storage interfaces, all combine to contribute to overall computing performance?</p> </blockquote> <p>How and where can I get the material for its preparation? Any recommendation?</p> <p>I am trying the following material (Chapter 1 &amp; 2) if its right for above topic?</p> <p><a href="https://nap.nationalacademies.org/catalog/12980/the-future-of-computing-performance-game-over-or-next-level" rel="nofollow noreferrer">https://nap.nationalacademies.org/catalog/12980/the-future-of-computing-performance-game-over-or-next-level</a></p> https://cs.stackexchange.com/q/143417 3 Faster way to calculate number of passes needed for bubble sort azazo https://cs.stackexchange.com/users/141728 2021-08-25T01:58:50Z 2022-05-22T19:07:32Z <p>Is there is a faster way to calculate the <strong>number of passes</strong> (<strong>not</strong> the number of swaps) needed to complete the bubble sort than actually doing the sort (as demonstrated in the code)?</p> <p>E.g.</p> <p>1, 2, 3 -&gt; 1 pass</p> <p>1, 3, 2 -&gt; 2 passes</p> <p>3, 2, 1 -&gt; 2 passes</p> <p>3, 1, 2, 4 -&gt; 2 passes</p> <p>0, 4, 2, 6, 1, 5, 3, 7 -&gt; 4 passes</p> <p>Code in Python:</p> <pre><code>def count_passes(A): cont = True i = 0 length = len(A) passes = 0 while cont and i &lt; length - 1: cont = False for j in range(length - i - 1): if A[j] &gt; A[j+1]: A[j], A[j+1] = A[j+1], A[j] cont = True i += 1 passes += 1 return passes </code></pre> https://cs.stackexchange.com/q/139571 1 Induction on recursive formula MathCurious https://cs.stackexchange.com/users/135550 2021-04-27T12:07:43Z 2022-05-22T17:47:56Z <p>I have this recursive formula</p> <p><span class="math-container">$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$</span></p> <p><span class="math-container">$$T\left(n\right) =T\left(1\right)\ +\ c_{2}n\cdot\sum_{k=1}^{⌊\log n⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}(n-1)$$</span></p> <p>I've been trying for a few hours to prove its correctness by induction, I feel like I've tried everything. The closest I got was defining <span class="math-container">$n=2^{x}$</span> and proving the correctness for every <span class="math-container">$x$</span>, but I can't seem to get the right answer. How do you prove something like that?</p> <p>The main question is how do I prove <span class="math-container">$T(n) = T(n/2) + c_{2}n = T(1) + c_{2}(n-1)$</span>.</p> https://cs.stackexchange.com/q/139535 0 IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary? Self_taught CS https://cs.stackexchange.com/users/135749 2021-04-26T21:13:48Z 2022-05-22T20:07:50Z <p>The SUBSET SUM decision problem consists of poitive integers a<sub>1</sub>,...,a<sub>n</sub>; b. <br/> We wish to know if for some subset S of the indices, <span class="math-container">$\sum_{i \in S}a_i = b$</span> <br/><br/> I want to prove that if b is given in unary(and the a<sub>i</sub>'s are gives in binary), that this decision problem is in P</p> https://cs.stackexchange.com/q/134761 0 Why do register machines outperform stack machines? Patrick Coppock https://cs.stackexchange.com/users/131181 2021-01-24T21:18:27Z 2022-05-22T08:37:54Z <p><a href="https://en.m.wikipedia.org/wiki/Stack_machine" rel="nofollow noreferrer">Wikipedia says</a> stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?</p> https://cs.stackexchange.com/q/133909 1 Determine the number of elements that is divisible by a prime number in an array Curious student https://cs.stackexchange.com/users/130298 2021-01-02T15:39:03Z 2022-05-22T10:03:55Z <p>I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers. For each of the prime numbers, I want to know how many numbers in the first array are divisible by this prime number. For example:</p> <blockquote> <p>Array = {5 5 7 10 14 15}</p> <p>Set = {2 3 5 7 11}</p> <p>result:2:2; 3:1; 5:4; 7: 2; 11:0</p> </blockquote> <p>Brute force by using nested loops works, but is there a faster way?</p> https://cs.stackexchange.com/q/133656 0 Algorithmic challenge: generate a list of random non overlapping squares Wouter Vandenputte https://cs.stackexchange.com/users/130005 2020-12-25T13:43:37Z 2022-05-22T15:02:20Z <p>For an undisclosed reason, I need a list of <span class="math-container">$n$</span> squares in a two dimensions space where each square does not overlap.</p> <p>So the challenge is simply: given a two dimensional area <span class="math-container">$a$</span> (<code>topLeft: int, topRight: int, width: int, height:int</code>), a number of squares required <span class="math-container">$n$</span> and a size for each square <span class="math-container">$s$</span>: generate a list <span class="math-container">$L$</span> of <span class="math-container">$|L|=n$</span> squares in <span class="math-container">$a$</span> where the following condition holds. <span class="math-container">$$\forall q,r \in L , q \neq r \implies \textrm{no_overlap}(q,r) \land \textrm{inside}(q,a)$$</span> where <code>no_overlap</code> is a function that checks if square <span class="math-container">$q$</span> and <span class="math-container">$r$</span> do not overlap given the size <span class="math-container">$s$</span> and <code>inside(q,a)</code> checks if square <span class="math-container">$q$</span> is completely inside the area <span class="math-container">$a$</span>.</p> <p>I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to <span class="math-container">$L$</span>. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most <span class="math-container">$\mathcal{O}(n^2)$</span>. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.</p> <p>EDIT: This would be a possible solution graphically illustrated for <span class="math-container">$n=7$</span> <a href="https://i.stack.imgur.com/ZfnXo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZfnXo.png" alt="enter image description here" /></a></p> https://cs.stackexchange.com/q/132690 1 walk / traverse a disjoint set that has union rank and path compression xdavidliu https://cs.stackexchange.com/users/82288 2020-11-26T18:23:15Z 2022-05-22T12:04:55Z <p>I'm studying CLRS section 21.3, which introduces a union rank + path-compressed implementation of disjoint set. The implementations of MAKE-SET, UNION, LINK, and FIND-SET on p 571 of the book all work with nodes themselves, where each node has a <code>parent</code> pointer and <code>rank</code>.</p> <p>Exercise 4 in that section claims that if you wanted to traverse all the nodes in the set (e.g. to print them) you only need <strong>a single extra attribute</strong> for each node, and the book claims that you can implement this <em>without</em> sacrificing the asymptotic complexity of union rank + path compression.</p> <p>The data structure that immediately comes to mind is a circular list with single (not double) links. In this case, the &quot;single extra attribute&quot; the exercise asks for would be the <code>next</code> pointer of each node. We could just maintain that list in parallel with the disjoint-forest + union rank + path-compression.</p> <p>However, the problem is that when trying to merge two sets, you would also need to merge their circular lists, and for a singly linked circular list, I'm pretty sure you <strong>cannot combine them into one without traversing through one of them first</strong>. This traversing would certainly destroy the asymptotic efficiency of union rank + path compression here.</p> <p>Of course, you could slightly augment the circular list by keeping track of both its head <em>and</em> the node <em>before</em> the head, i.e. the tail. However, in order to do this, you can no longer work directly with the nodes, but would need to maintain a <code>circ-list</code> object (one for each set) with <code>head</code> and <code>tail</code> pointers. This would also mean that you can no longer call UNION on two nodes directly, but rather need to maintain a <code>set</code> object that has a pointer to its <code>circ-list</code> object as well as its <code>root</code>. All this seems to be somewhat more than the &quot;exactly one extra attribute for each node`, since you also need O(1) extra attributes for each set.</p> <p>Is what the exercise asking for actually possible, or do I need to make one of the concessions above?</p> https://cs.stackexchange.com/q/129671 1 Title matching against human input Anon Coward https://cs.stackexchange.com/users/125899 2020-08-28T23:04:16Z 2022-05-22T08:06:50Z <p>I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known. Ideally I'd also have some way to suggest the human input of a truly novel title matches no known title as well.</p> <p>As an example, I have a list of titles like this:</p> <pre><code>The Conspirators The Count of Monte Cristo The Three Musketeers The Fencing Master </code></pre> <p>Only, my real list of titles is on the order of tens of millions long, and includes titles in different languages, including non Latin based languages.</p> <p>And, as a human enters titles like these, I am attempt to find the proper name, here are examples of what humans might enter for <code>The Three Musketeers</code>:</p> <pre><code>The Three Musketeers The 3 Musketeers Three Musketeers, The The.Three.Musketeers the-three-musketeers thethreemusketeers The Three Musketeers-1844 Three Musketeers THE THREE MUSKETEERS </code></pre> <p>For lack of a better term, at present, I'm attempting to &quot;normalize&quot; the titles. For instance, that means I:</p> <ul> <li>Convert input to a known case</li> <li>Remove why whitespace (or characters acting like whitespace, like the <code>-</code> and <code>.</code> above)</li> <li>Remove extraneous information (like <code>1844</code> above)</li> <li>Fix up common issues, like replace <code>and</code> with <code>&amp;</code></li> <li>Other domain specific fix-ups</li> </ul> <p>This is done once on the known good titles, and whenever a user enters a title, a simple database lookup is done. In the case of multiple titles matching, domain specific guesses are made (for instance, a book with more reviews wins over other options).</p> <p>This works, but it requires a lot of custom logic in the string normalization, and what's worse, it requires knowledge of multiple languages. And if users suddenly start following a new trend, like as a made up example, use <code>=</code> instead of spaces, then there needs to be a feedback loop where someone reviews common &quot;misses&quot; in the search and updates the string normalization logic.</p> <p>Some other options I've briefly looked into:</p> <ul> <li>Phonetic matching algorithms, like Soundex. These sometimes work, but some of the human input doesn't sound like the target word, and these systems tend to require I know the target language, which I don't always know.</li> <li>Machine Learning. I'm at a loss here, most of the systems I've read about require cleaning of human input, which if I can do, I can match without any ML systems.</li> <li>n-gram based fuzzy matching. Much like the phonetic matching systems, this requires knowing the language, and cleaning up the text to some degree beforehand. Also, most of the systems seem to require a lot of compute power to perform the lookup, which is a concern.</li> </ul> <p>Are there better techniques to apply to this problem to find the real title from the human input?</p> https://cs.stackexchange.com/q/67915 0 Removing epsilon transition from context-free grammar trolkura https://cs.stackexchange.com/users/42673 2016-12-26T17:06:27Z 2022-05-22T23:07:20Z <p>I have the following context-free grammar from which I have to remove epsilon transitions:</p> <p>$S \to 0A0|0$</p> <p>$A \to BC|2| CCC$</p> <p>$B \to 1C | 3D | \epsilon$</p> <p>$C \to AA3 | \epsilon$</p> <p>$D \to AAB | 2$</p> <hr> <p>By algorithm, I create $N_{0}$ that will hold all non-terminals that contain $\epsilon$ and in next steps add non-terminals that have rule that contains only non-terminals from the previous iteration of N e.g.</p> <ol> <li><p>$N_{0} = \{\}$</p></li> <li><p>$N_{1} = \{B,C\}$</p></li> <li><p>$N_{2} = \{B,C,A\}$</p></li> <li><p>$N_{3} = \{B,C,A,D,S\}$</p></li> </ol> <p>Now I have to adjust rules, we can remove non-terminals in $N_{3}$ object from rules, thus we have to create all combinations without it e.g.</p> <p>$S \to 0A0 | 00 | 0$</p> <p>$A \to BC | B | C | CCC | CC$</p> <p>$B \to 1C | 1 | 3D | 3$</p> <p>$C \to AA3| A3 | 3$</p> <p>$D \to AAB | AA | A | AB | B | 2$</p> <p>We see that no non-terminal isn't useless, so is this the final context-free grammar? Or did I make mistake somewhere?</p> <p>Thanks for answers and help.</p> https://cs.stackexchange.com/q/47870 14 What is Least-Constraining-Value? zstewart https://cs.stackexchange.com/users/40603 2015-10-04T22:09:43Z 2022-05-22T05:34:06Z <p>In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:</p> <ul> <li>Minimum-remaining-values (how many values are still valid for this variable)</li> <li>Degree heuristic (how many other variables are affected by this variable)</li> <li>Least-constraining-value (what value will leave the most other values for other variables)</li> </ul> <p>The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.</p> <p>Those are simple, clearly defined, and easy to implement.</p> <p>Least-constraining-value is not clearly defined, anywhere I looked. <em>Artificial Intelligence: A Modern Approach</em> (Russel &amp; Norvig) just says: </p> <blockquote> <p>It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.</p> </blockquote> <p>Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.</p> <p>The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.</p> <p>The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.</p> <p>Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?</p> https://cs.stackexchange.com/q/16367 2 Relational algebra statement for a query Kudayar Pirimbaev https://cs.stackexchange.com/users/7809 2013-10-23T15:48:29Z 2022-05-22T06:04:15Z <p>For the following schema</p> <pre><code>Country ("countryID", cName) CoffeeShop ("shopID", sName, countryID, city) Product ("productID", size) Serves ("shopID", "productID") ProductNames ("productID", "countryID", pName) </code></pre> <p>where attributes in quotation marks are primary keys, I must write a relational algebra statement for the following query:</p> <pre><code>List names of products that have same names in all countries they are served. </code></pre> <p>The thing that made me stuck on this problem is the fact that the product must not necessarily be served in all countries, but rather have the same name in all countries it is served. Without comparing for an initial value, I couldn't get a solution that makes more sense and that is possible to be written as a relational algebra statement.</p>