Recent Questions - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2023-10-04T11:08:27Z https://cs.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/162321 0 Convolution Theorem Practical Example Asif Iqbal https://cs.stackexchange.com/users/153557 2023-10-04T04:09:17Z 2023-10-04T04:09:17Z <p>I am trying to implement a practical example of Convolution theorem that states that any convolution can be achieved with Fourier Transform much easily with these steps:</p> <ol> <li>Apply Fourier Transform on the image,</li> <li>Apply Fourier Transform on the filter,</li> <li>Multiply the transformed image with the transformed filter (padding needed wherever applicable),</li> <li>Apply Inverse Fourier Transformation on the result and you should receive the same result as applying the filter on the image.</li> </ol> <p>I tried implementing these steps in <code>scipy</code> module of Python. My code is the following:</p> <pre class="lang-python prettyprint-override"><code>import numpy as np from scipy.fft import fft2, ifft2, fftshift, ifftshift from scipy.ndimage import gaussian_filter def apply_fast_fourier(img: np.array): # Apply Fast Fourier Transformation return fftshift(fft2(img)) def apply_inverse_fast_fourier(img: np.array): # Apply Inverse Fast Fourier Transformation return ifft2(ifftshift(img)) def zero_pad_images(original_img: np.array, filter_image: np.array): # Get the shape of image and filter h, w = original_img.shape kh, kw = filter_image.shape # Pad with zero according to the calculations padded_img = np.pad(original_img, ((0, kh), (0, kw)), mode=&quot;constant&quot;, constant_values=0) padded_filter = np.pad( filter_image, ((h // 2 - kh // 2, h // 2 + kh // 2), (w // 2 - kw // 2, w // 2 + kw // 2)), mode=&quot;constant&quot;, constant_values=0, ) return padded_img, padded_filter original_img = # Load Image Here (I am using a grayscale image) gaussian_filter = gaussian_filter(np.zeros((49, 49)), sigma=2) padded_img, padded_filter = zero_pad_images(original_img, gaussian_filter) ft_img = apply_fast_fourier(padded_img) ft_filter = apply_fast_fourier(padded_filter) filtered_img = np.multiply(ft_img, ft_filter) filtered_img = np.real(apply_inverse_fast_fourier(filtered_img)) </code></pre> <p>The problem is that my result looks like it has been split into four parts and flipped.</p> <p>For example:</p> <p><a href="https://i.stack.imgur.com/Asbbq.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Asbbq.png" alt="Comparison" /></a></p> <p>I am not sure why this is happening. Can anyone help?</p> <p>Thank you in advance!</p> https://cs.stackexchange.com/q/162320 0 Matching points on a plane with maximum total weight Grigori https://cs.stackexchange.com/users/133233 2023-10-03T22:42:58Z 2023-10-04T09:26:01Z <p>I have a set of points <span class="math-container">$P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$</span> on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative y-coordinate (y-coordinate can be non-integer). In addition, each point has a weight <span class="math-container">$w \in \mathbb{R}^+$</span>.</p> <p>I can match two points <strong>only of different colors</strong> <span class="math-container">$p_1 = (x_1, y_1, w_1)$</span> and <span class="math-container">$p_2 = (x_2, y_2, w_2)$</span> with a vector <span class="math-container">$v = \vec{p_1 p_2}$</span> of any weight <span class="math-container">$0 \le w \le min(w_1, w_2)$</span>, if <span class="math-container">$x_1 &lt; x_2$</span>. This vector will be assigned with a value</p> <p><span class="math-container">$$f_v = w \frac{y_1 - y_2}{y_1}$$</span>, if <span class="math-container">$p_1$</span> is green, and <span class="math-container">$-f_v$</span> vice versa.</p> <p><strong>Problem:</strong></p> <p>What is an algorithm to find a set of vectors <span class="math-container">$V = \{ v_1, \dots, v_s \}$</span> (described above) with proper weights <span class="math-container">$w_1, \dots, w_s$</span>, that will maximize total value of <span class="math-container">$F = \prod_{v \in V} (1 + f_v)$</span>?</p> <p><strong>Constraints:</strong></p> <ol> <li><p>Sum of weights of outgoing and incoming vectors (together) for each point should be less or equal than the weight of this point.</p> </li> <li><p>For each horizontal line <span class="math-container">$x=val$</span>, total weight of vectors that are intersected by this line is <span class="math-container">$\le 1$</span>.</p> </li> </ol> <p><strong>Methods:</strong></p> <ol> <li>I was thinking about dynamic programming approach, where I will calculate the max value of <span class="math-container">$F$</span> for each <span class="math-container">$i \le m$</span>, but it doesn't support floating weights <span class="math-container">$w$</span> of vectors.</li> </ol> https://cs.stackexchange.com/q/162319 0 Time complexity summations Ninaaaaa https://cs.stackexchange.com/users/161729 2023-10-03T22:25:11Z 2023-10-03T22:25:11Z <p>How to calculate the time complexity of a algorithm which contains while loops or if statements using summations? I only know how they work with the for loops. And I'm guessing the if loop are calculated as a time complexity of (1)?</p> <pre><code>r=1 for i=6 to n+2 do { j=n−3 while j≥log7(n−1) do { j=j−2 r=2⋅r } } </code></pre> https://cs.stackexchange.com/q/162316 0 How can I organize groups of people, who don't know each other, on a regular cadence? Craig https://cs.stackexchange.com/users/106787 2023-10-03T18:23:54Z 2023-10-03T20:14:02Z <p>I'm trying to figure out an algorithm for this specific problem.</p> <p><strong>The problem</strong>: I have N people (say 60 but could be far more) that I want to organize into groups of 4 on a monthly cadence.</p> <p><strong>The constraints</strong>:</p> <ol> <li>Each month, groups should contain people that haven't been grouped before (until they've been in a group with everyone)</li> <li>Since these people all work for the same company, people in a group should never be on the same team (as in, reporting to the same manager).</li> </ol> https://cs.stackexchange.com/q/162315 0 Minimum number of states in a DFA Rishi https://cs.stackexchange.com/users/163389 2023-10-03T17:00:05Z 2023-10-03T17:12:14Z <p>Consider the language L given by the regular expression (a + b )*b(a + b) over the alphabet {a, b} . The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is :</p> <p>My attempt :<br /> I designed the following DFA <a href="https://i.stack.imgur.com/cgtb4.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cgtb4.png" alt="My DFA for the language" /></a></p> <p>The answer key says that minimal DFA will have 4 states. I am unable to find a counterexample for my DFA. So where am I going wrong?</p> https://cs.stackexchange.com/q/162311 0 How to convert a NFA to alternating finite automata AFA? walla https://cs.stackexchange.com/users/163382 2023-10-03T08:44:24Z 2023-10-03T08:44:24Z <p>I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?</p> https://cs.stackexchange.com/q/162309 0 What does the data field store? Cerise https://cs.stackexchange.com/users/162479 2023-10-03T07:46:23Z 2023-10-03T11:03:58Z <p>This semester we have a class related to Operating Systems.The class itself is not obligatory but the class is done at the same time with a core class and I will simply not waste a year for 1 class so I have decided to access the resources of the Operating Systems class and study on my own.</p> <p>A process is any program loaded into the main memory currently being executed or which awaits execution.Any process is made of :the code where the instructions are stored , the call stack and the data field.However what exactly is the data field.After a brief search the data field stores any process related data(input or output) so I guess it stores any parameters or temporary variables used by the process?</p> https://cs.stackexchange.com/q/162307 0 Abstract Interpretation: prove that the sign subtraction is increasing in each of its parameters Kiuhnm https://cs.stackexchange.com/users/163371 2023-10-03T07:22:30Z 2023-10-03T07:22:30Z <p>I need to prove that the binary operator <span class="math-container">$-_\pm: \mathbb{P}^\pm\times\mathbb{P}^\pm\rightarrow\mathbb{P}^\pm$</span> is increasing in each of its arguments, where</p> <p><span class="math-container">$$\mathbb{P}^\pm = \{\top_\pm, \leq0,\neq0, \geq0,&lt;0,=0,&gt;0,\bot_\pm\}$$</span></p> <p>are the abstract properties it operates on. They represent the &quot;signs&quot; of values in <span class="math-container">$\mathbb Z$</span>.</p> <p>Their concretizations are, resp.,</p> <p><span class="math-container">$$\mathcal{P}^\pm = \{ \mathbb Z, \{z \in \mathbb Z \mid z \leq0\}, \{z \in \mathbb Z \mid z \neq0\}, \{z \in \mathbb Z \mid z \geq0\}, \ldots, \emptyset \}$$</span></p> <p>The concretization of a sign property <span class="math-container">$s$</span> is given by <span class="math-container">$\gamma(s)$</span>, where <span class="math-container">$\gamma$</span> is an isomorphism between the posets <span class="math-container">$(\mathcal{P}^\pm, \subseteq)$</span> and <span class="math-container">$(\mathbb{P}^\pm, \sqsubseteq)$</span>, and</p> <p><span class="math-container">$$\forall s_1,s_2\in\mathbb{P}^\pm . s_1 \sqsubseteq s_2 \iff \gamma(s_1)\subseteq\gamma(s_2).$$</span></p> <p>I couldn't find any smart way to prove the monotonicity of <span class="math-container">$-_\pm$</span>, so I just built an <span class="math-container">$8\times8$</span> &quot;subtraction table&quot; with <span class="math-container">$s_1-_\pm s_2$</span> for every possible pair of signs. For each valid <span class="math-container">$i$</span>, let <span class="math-container">$r_i$</span> be the <span class="math-container">$i$</span>-th row, and <span class="math-container">$s_i$</span> the property associated with <span class="math-container">$r_i$</span>. I simply verified that if <span class="math-container">$s_i \sqsubseteq s_j$</span> then, for all valid <span class="math-container">$k$</span>, <span class="math-container">$r_{ik}\sqsubseteq r_{jk}$</span>. I did the same for the columns.</p> <p>This is quite bruteforc-y, although it didn't take long thanks to the table. I'd just like to know whether this is the correct way to solve this exercise or not.</p> https://cs.stackexchange.com/q/162305 0 Valid Lambda Expressions Jeremy Bowens https://cs.stackexchange.com/users/163370 2023-10-02T23:08:45Z 2023-10-03T18:44:34Z <p>I have two questions about the validity of lambda expressions.</p> <p>First, is a variable on it's own a valid lambda expression (ex: λx)</p> <p>Second, take for example these two lambda expressions (λx.fxya and λz.fxya). They're identical besides the fact that the bounded variable is different. Does this affect it's validity?</p> <p>Also, if these are all valid, is there a way to see some invalid lambda expressions so I can get an idea between what a valid and invalid one looks like?</p> https://cs.stackexchange.com/q/162304 0 In a directed graph, efficiently determine node reached after traveling k edges from the starting node Falls2879 https://cs.stackexchange.com/users/163369 2023-10-02T20:55:28Z 2023-10-03T07:38:29Z <p>I am trying to solve a problem where I am given a directed graph with <span class="math-container">$n$</span> nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from <span class="math-container">$1$</span> to <span class="math-container">$n$</span>. Starting at node <span class="math-container">$1$</span>, the problem consists in writing an algorithm which determines on which node we end up after moving along <span class="math-container">$k$</span> edges.</p> <p>Here is an example graph:</p> <p><a href="https://i.stack.imgur.com/9E6pQ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9E6pQ.png" alt="graph example 1" /></a></p> <p>If <span class="math-container">$k=2$</span>, then the final node will be <span class="math-container">$3$</span>. If <span class="math-container">$k=9$</span>, then we will reach node <span class="math-container">$5$</span> instead.</p> <p>In order to solve this problem, I chose to represent the graph as a one-dimensional array, where the index of the array represents the current node and the value at said index the node which we can reach. Since in Python, arrays are 0-indexed, the first value is 0.</p> <p>The following array represents the graph above:</p> <pre class="lang-python prettyprint-override"><code># indexes: 0 1 2 3 4 5 my_graph = [0, 2, 3, 5, 1, 3] </code></pre> <p>From here on, I utilized a naive approach to determine the final node:</p> <pre class="lang-python prettyprint-override"><code>current_node = 1 while k &gt; 0: k -= 1 current_node = my_graph[current_node] print(current_node) </code></pre> <p>This code works fine and outputs the correct answer, however it is obviously too slow for huge values of <span class="math-container">$k$</span> (upwards of <span class="math-container">$10^{15}$</span>). I am guessing that dynamic programming could be of help in order to produce faster results, but I am having a hard time determining the &quot;smallest subproblem&quot; here...</p> <p>I would appreciate any help or hints towards an efficient algorithm which solves the described problem.</p> https://cs.stackexchange.com/q/162301 0 How to prove that $L=\{0^m1^n\;|\; \mathbf{gcd}(m,n)=1\}$ is not regular CXLi https://cs.stackexchange.com/users/163366 2023-10-02T15:41:16Z 2023-10-03T16:42:32Z <p>The <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages" rel="nofollow noreferrer">pumping lemma</a> is allowed to be used in this assignment, so I have tried to make <span class="math-container">$|0^{m+b|y|-|y|}| = |xy^b| = a!, a\ge |y|,a\ge n$</span> so that <span class="math-container">$gcd(|0^{m+b|y|-|y|}|,n) \neq 1$</span>.</p> https://cs.stackexchange.com/q/162298 1 Number of maximal induced trees in a connected planar graph YoloV4 https://cs.stackexchange.com/users/161862 2023-10-02T14:42:36Z 2023-10-03T15:24:35Z <p>An induced subgraph <span class="math-container">$G’$</span> of a graph <span class="math-container">$G$</span> is a subset of its vertices along with all the edges that are present in <span class="math-container">$G$</span> among those vertices. For <span class="math-container">$G’$</span> to be a tree, all vertices of a cycle in <span class="math-container">$G$</span> cannot be in <span class="math-container">$G’$</span>. The tree composed of bold edges in the illustration given below shows an induced tree <span class="math-container">$T$</span>. Vertex <span class="math-container">$u$</span> cannot be included in <span class="math-container">$T$</span> because u brings with itself edges <span class="math-container">$(u, v)$</span> and <span class="math-container">$(u, w)$</span> which completes a cycle <span class="math-container">$u-v-w-u$</span> and <span class="math-container">$T$</span> no longer remains a tree. <span class="math-container">$T$</span> is also a maximal induced tree because no more vertices can be included in <span class="math-container">$T$</span> without violating it being a tree.</p> <p>The question is, what is a tight upper bound on the number of maximal induced trees in a connected triangulated planar graph.</p> <p><a href="https://i.stack.imgur.com/kKkVr.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/kKkVr.png" alt="enter image description here" /></a></p> https://cs.stackexchange.com/q/162276 0 Optimal reassociations is NP-hard? Konstantin Vladimirov https://cs.stackexchange.com/users/107037 2023-10-01T08:37:26Z 2023-10-04T05:50:22Z <p>Consider signed integers with common addition and multiplication.</p> <p>Reassociation of expression is another equivalent form.</p> <p>Say expressions:</p> <pre><code>a * b + a * c + c * b a * (b + c) + c * b a * b + c * (a + b) </code></pre> <p>Are all reassociations of each other.</p> <p>Lets call optimal reassociation with one with minimal multiplications.</p> <p>It can be hard to observe. For instance:</p> <pre><code>a * c - a * d - b * c - e * f + e * d + b * f </code></pre> <p>Optimal reassociation is tricky:</p> <pre><code>(a - b) * (c - d) - (e - b) * (f - d) </code></pre> <p>To build this one we need to guess utterly non-obvious step: add and subtract b * d to original one.</p> <p>Yes/No problem may be stated like this: I give you expression E which is sum of monomials and number N, you shall answer is there exists reassociation of E with no more than N multiplications.</p> <p>I believe this is no harder than NP: if oracle gives us simplified expression it takes polynomial time to simplify braces and check answer against E.</p> <p>My question is: if this problem NP-complete and how can I prove this? Or is there some smart polynomial algorithm?</p> https://cs.stackexchange.com/q/162272 1 Specialized SAT solver (?) fuzzypixelz https://cs.stackexchange.com/users/133479 2023-09-30T20:53:06Z 2023-10-03T03:56:50Z <p>(<a href="https://fuzzypixelz.com/blog/absolut/" rel="nofollow noreferrer">Context</a>)</p> <p>Given two byte arrays of length 16, say <span class="math-container">$L$</span> and <span class="math-container">$H$</span>, one can define a mapping <span class="math-container">$M$</span> from the set of all bytes to itself in the following way.</p> <p>If <span class="math-container">$0 \le b \lt 256$</span> is a byte, let <span class="math-container">$\text{lo}(b)$</span> denote the lower 4 bits of <span class="math-container">$b$</span> and let <span class="math-container">$\text{hi}(b)$</span> denote the higher 4 bits of <span class="math-container">$b$</span>.</p> <p>Let <span class="math-container">$L_i$</span> (resp. <span class="math-container">$H_i$</span>) denote the <span class="math-container">$i$</span>-th byte of <span class="math-container">$L$</span> (resp. <span class="math-container">$H$</span>). Also let <span class="math-container">$L_{i,j}$</span> (resp. <span class="math-container">$H_{i,j}$</span>) denote the <span class="math-container">$j$</span>-th bit of the <span class="math-container">$i$</span>-th byte of <span class="math-container">$L$</span> (resp. <span class="math-container">$H$</span>).</p> <p><span class="math-container">$$M: \{0,\dots,255\} \to \{0,\dots,255\} \\ b \mapsto L_{\text{lo}(b)} \land H_{\text{hi}(b)}$$</span></p> <p>Where <span class="math-container">$\land$</span> is bitwise logical conjunction.</p> <p>If we want <span class="math-container">$M$</span> to satisfy <span class="math-container">$M(b_0) = m_0, \dots, M(b_p) = m_p$</span> for bytes <span class="math-container">$b_k$</span> and bytes <span class="math-container">$m_k$</span> with <span class="math-container">$0 \le k \lt p$</span>. Then <span class="math-container">$L$</span> and <span class="math-container">$H$</span> have to be chosen accordingly (if possible). Note that while the <span class="math-container">$b_k$</span> bytes are known, the <span class="math-container">$m_k$</span> bytes are not. Hence why they persist as propositional variables in the following clauses.</p> <p>A constraint of the form <span class="math-container">$M(b_k) = m_k$</span> can be translated to:</p> <p><span class="math-container">$$L_{\text{lo}(b_k)} \land H_{\text{hi}(b_k)} = m_k$$</span></p> <p>Or more precisely:</p> <p><span class="math-container">$$L_{\text{lo}(b_k), j} \land H_{\text{hi}(b_k), j} = m_{k,j}$$</span></p> <p>Where <span class="math-container">$m_{k,j}$</span> is the <span class="math-container">$j$</span>-th bit of <span class="math-container">$m_k$</span>.</p> <p>In general, any equation of the form <span class="math-container">$X \land Y = Z$</span> where <span class="math-container">$X, Y, Z$</span> are bits (or booleans) is equivalent the following boolean clauses in propositional logic:</p> <p><span class="math-container">$$\bar{X} \lor \bar{Y} \lor Z \\ X \lor \bar{Z} \\ Y \lor \bar{Z} \\$$</span></p> <p>Where <span class="math-container">$\bar{X}$</span> is the negation of <span class="math-container">$X$</span>.</p> <p>The last remaining piece of the problem is the fact that all <span class="math-container">$m_k$</span> bytes should be distinct. Two bits <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are non-equal iff the following clauses hold:</p> <p><span class="math-container">$$X \lor Y \\ \bar{X} \lor \bar{Y}$$</span></p> <p>Hence this problem can be solved using 3-SAT. I have three question with regards to this:</p> <ol> <li>Is my problem equivalent to 3-SAT, i.e. can an arbitrary 3-SAT problem be reduced to it? Or is it further simplifiable into something less difficult?</li> <li>If not, do you see an algorithm for solving it efficiently?</li> <li>If yes, would a &quot;simple&quot; CDCL-based solver suffice? (We're dealing with around 3000 clauses and 300 variables).</li> </ol> <p>I have already tried a basic backtracking solver and it failed to terminate even after multiple hours. I'm writing this after having spent multiple weeks thinking about this, and having failed to come up with a specialised algorithm. I could of course just use an off-the-shelf SAT solver but I'm interested in solving this as efficiently as possible.</p> <p>Thank you in advance.</p> https://cs.stackexchange.com/q/162253 1 Question about step in proof that predecessor subgraph forms a breadth-first tree Hugh Mann https://cs.stackexchange.com/users/113534 2023-09-28T15:21:08Z 2023-10-03T18:37:40Z <p>Given the following theorem and definitions from <em>Introduction to Algorithms</em> 3rd edition by CLRS:</p> <p><strong>Theorem 22.5: (Correctness of breadth-first search</strong>)</p> <p>Let <span class="math-container">$G = (V, E)$</span> be a directed or undirected graph, and suppose that <span class="math-container">$BFS$</span> is run on <span class="math-container">$G$</span> from a given source vertex <span class="math-container">$s \in V$</span>. Then, during its execution, <span class="math-container">$BFS$</span> discovers every vertex <span class="math-container">$v \in V$</span> that is reachable from the source <span class="math-container">$s$</span>, and upon termination, <span class="math-container">$v.d = \delta(s, v)$</span> for all <span class="math-container">$v \in V$</span>. Moreover, for any vertex <span class="math-container">$v \neq s$</span> that is reachable from <span class="math-container">$s$</span>, one of the shortest paths from <span class="math-container">$s$</span> to <span class="math-container">$v$</span> is a shortest path from <span class="math-container">$s$</span> to <span class="math-container">$v.\pi$</span> followed by the edge <span class="math-container">$(v.\pi, v)$</span>.</p> <p><span class="math-container">$\delta(s,v) \rightarrow \text{length of the shortest path from s to v} \\\ v.d\rightarrow \text{distance assigned to vertex$v$from$s$by BFS}\\\ v.\pi\rightarrow \text{predecessor of$v$in the path from$s$to$v$in the BFS}$</span></p> <p>For a graph <span class="math-container">$G = (V, E)$</span> with source <span class="math-container">$s$</span>, the <strong>predecessor subgraph</strong> of <span class="math-container">$G$</span> is <span class="math-container">$G_{\pi} = (V_{\pi}, E_{\pi})$</span>, where <span class="math-container">$V_{\pi} = \{ v \in V : v.\pi \neq NIL\} \cup \{s\}$</span> and <span class="math-container">$E_{\pi} = \{ (v.\pi, v) : v \in V_{\pi} - \{s\}\}$</span></p> <p>The predecessor subgraph <span class="math-container">$G_{\pi} = (V_{\pi}, E_{\pi})$</span> is a <strong>breadth-first tree</strong> if <span class="math-container">$V_{\pi}$</span> consists of the vertices reachable from <span class="math-container">$s$</span> and, for all <span class="math-container">$v \in V_{\pi}$</span>, the subgraph <span class="math-container">$G_{\pi}$</span> contains a unique simple path from <span class="math-container">$s$</span> to <span class="math-container">$v$</span> that is also a shortest path from <span class="math-container">$s$</span> to <span class="math-container">$v$</span> in <span class="math-container">$G$</span></p> <p>I have a question about the following proof:</p> <p><strong>Lemma 22.6:</strong></p> <p>When applied to a directed or undirected graph <span class="math-container">$G = (V, E)$</span>, procedure BFS constructs <span class="math-container">$\pi$</span> so that the predecessor subgraph <span class="math-container">$G_{\pi} = (V_{\pi}, E_{\pi})$</span> is a breadth-first tree.</p> <p>Line 16 of BFS sets <span class="math-container">$v.\pi = u$</span> iff <span class="math-container">$(u, v) \in E$</span> and <span class="math-container">$\delta(s, v) &lt; \infty$</span> - that is, if <span class="math-container">$v$</span> is reachable from <span class="math-container">$s$</span>- and thus <span class="math-container">$V_{\pi}$</span> consists of the vertices in <span class="math-container">$V$</span> reachable from <span class="math-container">$s$</span>. Since <span class="math-container">$G_{\pi}$</span> forms a tree, it contains a unique simple path from <span class="math-container">$s$</span> to each vertex in <span class="math-container">$V_{\pi}$</span>. By applying <strong>Theorem 22.5</strong> inductively, we conclude that every such path is a shortest path in <span class="math-container">$G$</span>.</p> <p>I'm not sure I understand the last sentence of this proof. Can anyone elaborate on how to &quot;apply <strong>Theorem 22.5</strong> inductively&quot; to &quot;conclude that every such path is a shortest path in <span class="math-container">$G$</span>&quot;?</p> <p><strong>Update:</strong></p> <p>One interpretation might be that we need to use induction to prove the last claim and the last part of Theorem 22.5 about a shortest path from <span class="math-container">$v.\pi$</span> to <span class="math-container">$v$</span>is used in the proof.</p> <p>For example, we can order the vertices in <span class="math-container">$V_{\pi}$</span> in non-decreasing order of distances from <span class="math-container">$s$</span>. The base case would be the first vertex in <span class="math-container">$V_{\pi}$</span>, which is <span class="math-container">$s$</span>. We then assume that it holds for the first <span class="math-container">$n$</span> vertices in <span class="math-container">$V_{\pi}$</span> and we show that it holds for <span class="math-container">$v_{n+1}$</span> by appealing to the last part of Theorem 22.5.</p> https://cs.stackexchange.com/q/162204 3 how to do incremental construction of the minimal model in logic programming? alim https://cs.stackexchange.com/users/53213 2023-09-25T05:03:42Z 2023-10-03T14:43:57Z <p>I was reading a book titled &quot;Essentials of Logic Programming.&quot;, most parts of the book are easy to understand. but now having a problem with Theme 45: incremental constructions of the minimal model. The relevant parts are shown below.</p> <p>Some notations: <span class="math-container">$P$</span> is a definite program, <span class="math-container">$B(P)$</span> is the Herbrand base of <span class="math-container">$P$</span>, <span class="math-container">$G(P)$</span> is a ground instantiation of <span class="math-container">$P$</span>, <span class="math-container">$MM(P)$</span> is a minimal model of <span class="math-container">$P$</span>.</p> <p>Theme 45 explains the incremental constructions of the minimal model as follows.</p> <blockquote> <p>The method starts by choosing some interpretation <span class="math-container">$I_1 \subseteq B(P)$</span>. Later on, we shall see that there is a preferred choice of <span class="math-container">$I_1$</span> and that not all choices are adequate. Choosing <span class="math-container">$I_1$</span> can be viewed as guessing which atoms have to be true in any model of <span class="math-container">$P$</span>. Now consider any clause in <span class="math-container">$G(P)$</span> kind(Chris) q if body</p> </blockquote> <blockquote> <p>if our guess assigns true to all atoms in this body then an immediate consequence of that guess is that q should also be made true, for otherwise the clause as a whole would be made false. Our next iterate <span class="math-container">$I_2$</span> comprise just those heading atoms q made true by this argument. This new iterate will not necessarily contain all those body atoms which justified the introduction of the new atoms q; this does not matter - successive iterates will eventually introduce and retain all of these atoms which must be true in any model of the program. Consider this example of a program <span class="math-container">$P$</span> on the domain <span class="math-container">$H=\{ dov,chris\}$</span>:</p> </blockquote> <blockquote> <p>kind(X) if nice (X)</p> </blockquote> <blockquote> <p>nice(X)</p> </blockquote> <blockquote> <p>whose ground instantiation <span class="math-container">$G(P$</span> is highly abbreviated form is</p> </blockquote> <blockquote> <p>kind(dov) if nice(dov)</p> </blockquote> <blockquote> <p>kind(Chris) if nice(Chris)</p> </blockquote> <blockquote> <p>nice(dov)</p> </blockquote> <blockquote> <p>(where K=kind, N=nice, D=dov,C=Chris)</p> </blockquote> <blockquote> <p>and suppose we choose <span class="math-container">$I_1= \{ kind(dov),nice(Chris)\}$</span>. Applying the above method yields <span class="math-container">$I_2= \{ nice(dov), kind(Chris)\}$</span> and <span class="math-container">$I_3= \{ nice(dov), kind(dov)\}$</span> All further iterates merely replicates <span class="math-container">$I_3$</span>, which is accordingly referred to as a fixpoint. We have, in fact, converged upon the minimal model <span class="math-container">$MM(P)$</span>.</p> </blockquote> <p>Let me explain how I understand or did not understand this example.</p> <ol> <li>is <span class="math-container">$I_1$</span> a guess? why not just make <span class="math-container">$I_1 = \{ nice(Chris)\}$</span>?</li> <li>nice(Chris) leads to kind(Chris) is true, so &quot;kind(Chris) if nice(Chris)&quot; is true. So, we have kind(Chris) in <span class="math-container">$I_2$</span>. But why there is nice(dov) in <span class="math-container">$I_2$</span>?</li> <li>as said further iterates will replicate <span class="math-container">$I_3$</span>, but I did not see how this works because I did not see the iterate from <span class="math-container">$I_1$</span> to <span class="math-container">$I_2$</span>.</li> </ol> <p>I just did not get this example. Could anyone clarify it to me?</p> <p>Thanks in advance!</p> https://cs.stackexchange.com/q/159988 0 Ticket Dispenser algorithm and the size of the Ticket array RT. https://cs.stackexchange.com/users/160367 2023-05-05T12:11:26Z 2023-10-03T09:02:10Z <p>The following is a ticket Dispenser Mechanism, it's from the article:</p> <p>&quot;Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion By Robert Danek and Wojciech Golab&quot; <a href="http://www.cs.toronto.edu/%7Erdanek/fcfs_disc.pdf" rel="nofollow noreferrer">http://www.cs.toronto.edu/~rdanek/fcfs_disc.pdf</a></p> <pre><code>shared variables: Tickets: array[0..7N-1] of {INUSE, FREE } initially Tickets[0..(3N-1)] = FREE and Tickets[3N..(7N-1)] = INUSE lastTicket: 0..7N-1 initially 7N-1 private variables: ticket: 0..7N-1 uninitialized </code></pre> <pre><code> Implementation of ObtainTicket(): 45 first := lastTicket 46 i := 1 // Find upper bound on the smallest FREE ticket. 47 while i &lt; 3N ( Tickets[(first + i) mod 7N] = INUSE do 48 i := min {3N, i x 2 } // Now do binary search to find the ticket. 49 last := first + i 50 while first &lt; last do 51 midpoint := RoundDown[(first + last )/2] 52 if Tickets[midpoint mod 7N] = INUSE then 53 first := midpoint + 1 54 else 55 last := midpoint // At this point first = last holds. 56 ticket := first mod 7N 57 Tickets[ticket ] := INUSE 58 return ticket </code></pre> <pre><code>Implementation of DoneWithTicket(): // Reset a ticket that was previously active. 59 Tickets[(ticket + 3N) mod 7N] := FREE 60 lastTicket := ticket </code></pre> <p>Why do we need 7N tickets and not 3N ?, it seems to suffice if every process can run this function and bypass us up to 3 times while process p is inside (It's Guaranteed according to the paper)</p> <p>The 7N size is not explained in the paper whatsoever..</p> https://cs.stackexchange.com/q/159982 2 Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph? Ike348 https://cs.stackexchange.com/users/160358 2023-05-05T02:47:27Z 2023-10-03T08:16:41Z <p>I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same size (either in terms of number of nodes or sum total of node weight), and the sum total weight of edges that cross between components is minimized. Problems of this nature are generally NP-hard, but I am aware of the software <a href="https://github.com/KarypisLab/METIS" rel="nofollow noreferrer">METIS</a> which can obtain good quality partitions very quickly. METIS also has the feature that it can enforce the constraint that each component in the resulting partition be contiguous (&quot;connected&quot;).</p> <p>What I am looking for is an algorithm or some sort of software package that is similar to METIS, but can also enforce the constraint <em>that each partition is still contiguous when only a certain subset of edges from the original graph are considered</em>.</p> <p>Here is an example:</p> <p><a href="https://i.stack.imgur.com/pTxEd.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pTxEd.png" alt="enter image description here" /></a></p> <p>The graph on the left is the original graph. All nodes have the same weight. If I want to partition the graph into two components, while enforcing contiguity constraints, I would choose the highlighted groups. This partition has a &quot;cost&quot; of 5. But what I actually want to do is partition the graph on the left, while enforcing the constraint that each component be contiguous if it only had the edges in the graph in the middle. This obviously results in a different partition (which is actually the only feasible partition in this small example). This partition has a cost of 9 (note I am still counting the edges from the original graph), but it satisfies the constraints.</p> <p>I would be interested in algorithms that solve this problem directly, or that transform the problem into something that can be solved by currently-existing software, e.g. METIS.</p> <p>It is not sufficient to just perform graph partitioning on the middle graph, because that ignores the potential cost of the additional edges that may or may not cross between different components in the resulting partition.</p> <p>(For those wondering the use case, I am interested in redistricting. I have a graph that quantifies the relationships between different precincts, but I need to enforce a contiguity constraint on the graph that represents which precincts actually border each other, which is much smaller than my input graph.)</p> https://cs.stackexchange.com/q/159962 0 Can all LL(k) grammar can be recognized by LR(1)? xie cui https://cs.stackexchange.com/users/160326 2023-05-03T13:55:20Z 2023-10-03T15:44:11Z <p>For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?</p> https://cs.stackexchange.com/q/154059 0 formal definition for "data type with larger range" hasanghaforian https://cs.stackexchange.com/users/141700 2022-09-09T05:00:46Z 2023-10-04T11:01:05Z <p><a href="https://en.wikipedia.org/wiki/Range_(computer_programming)#Range_of_a_variable" rel="nofollow noreferrer">Wikipedia</a> defines <code>range of data type</code>:</p> <blockquote> <i>the set of possible values that that variable can hold.</i> </blockquote> <p>Suppose we have two data types <i>A</i> and <i>B</i>. Now, with attention to the definition of <i>widening</i> in section <code>7.4</code> of <a href="https://rads.stackoverflow.com/amzn/click/com/0134997182" rel="nofollow noreferrer" rel="nofollow noreferrer">Concepts of Programming Languages</a>, we can say:</p> <blockquote> <i>range of B is larger than A</i> when <i>range of B</i> includes at least approximations of all members of <i>range of A</i>. </blockquote> <p>But above definition is informal; because &quot;accuracy&quot; of approximation is not determined. For example we can consider <code>0</code> as approximate for <code>0</code> of <code><i>int</i></code> and <code>1</code> as approximate for all other members of <code><i>int</i></code>. So we give a strange statement:</p> <p><code>range of <code><i>int</i></code> ≤ range of <i>{0,1}</i></code></p> <p>Although we can add the <code><i>|A| ≤ |B|</i></code> as a criteria to avoid some strange statements like above one (<code><i>|A|</i></code> means <a href="https://en.wikipedia.org/wiki/Cardinal_number" rel="nofollow noreferrer">Cardinal number</a> for set <code>A</code>); but the problem of &quot;accuracy&quot; remains again.</p> <p>Do you know a formal definition for &quot;a data type with larger range&quot;?</p> https://cs.stackexchange.com/q/151255 2 Show all chains per user Andrei T https://cs.stackexchange.com/users/21809 2022-05-05T12:17:41Z 2023-10-02T21:07:40Z <p>Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it.</p> <p>You have a chains of reservations from AirBnb:</p> <pre><code>reservations:[ {user = 1, res_id = 1001, checkin = 100, checkout = 101}, {user = 2, res_id = 1002, checkin = 104, checkout = 105}, {user = 1, res_id = 1003, checkin = 101, checkout = 103}, {user = 3, res_id = 1004, checkin = 104, checkout = 105}, {user = 3, res_id = 1005, checkin = 105, checkout = 107}, {user = 4, res_id = 1006, checkin = 106, checkout = 108}, {user = 4, res_id = 1007, checkin = 108, checkout = 110}, {user = 4, res_id = 1008, checkin = 108, checkout = 109}, {user = 4, res_id = 1009, checkin = 110, checkout = 112}, {user = 4, res_id = 1010, checkin = 109, checkout = 113}, ]; </code></pre> <p>where all res_ids are unique and check_out is always bigger than check_in for a reservation.</p> <p>We name a chain something like:</p> <p><code>[checkin = 1, checkout = 3], [checkin = 3, checkout = 5]</code>.</p> <p>If there are no two reservations connected then no chain. We are interested only in reservation chains, two or more reservations connected by checkin/checkout. Since check_out is always bigger than check_in for a reservation, there will be no cycles.</p> <p>My task was to find all the chains per user. In the example from above the chains would be:</p> <p><strong>Example:</strong> <code>{ 1: {{1001, 1003}}, 3: {{1004, 1005}}, 4 : {{1006, 1007, 1009}, {1006, 1008, 1010}} }</code></p> <p>In fact, I do not need the users, only the list would work too.</p> <pre><code>{ {1001, 1003}, {1004, 1005}, {1006, 1007, 1009}, {1006, 1008, 1009}}. </code></pre> <p>In case the chains were not overlapping I solved it by using sorting based on checkin and checkout. It worked. However, when the reservations were overlapping I had no idea.</p> <p>I put here an example where they are overlapping.<br /> I tried using a stack, something similar to the minimum number of knight moves to reach coordinate (x, y) from (0, 0) but with no success as number of top level are not one after the other. Any suggestions?</p> https://cs.stackexchange.com/q/148265 1 Call by name, lambda calculs. Multiplication chillovecheck https://cs.stackexchange.com/users/146984 2022-01-09T12:42:28Z 2023-10-03T20:07:50Z <p>How to multiply in CBN strategy?</p> <pre><code>mul = \m.\n.\f. m(n f) two = \f.\x. f (f x) mul two two = (\m.\n.\f. m(n f)) (\f.\x. f (f x)) (\f.\x. f (f x)) = = \f. (\f0.\x0. f0 (f0 x0)) ((\f1.\x1. f1 (f1 x1)) f) </code></pre> <p>As I understand, after that, calculations in the CBN strategy stop, because in CBN no reduce under abstractions.</p> <p>is it possible to get 4 in my example after multiplying in the CBN strategy?</p> https://cs.stackexchange.com/q/134186 1 Calculate the effective access time h_55 https://cs.stackexchange.com/users/130640 2021-01-10T15:14:34Z 2023-10-03T07:09:06Z <p>This question seems to be causing a lot of debate and I'm wondering whether my working is correct.</p> <blockquote> <p>A computer with a single cache (access time 20ns) and main memory (access time 500ns) also uses the hard disk (average access time 0.01ms) for virtual memory using paging. If it is found that the cache hit rate is 95% and the page fault rate is 1%<br /> Calculate the effective (average) access time (EAT) of this system for a sequential access system.<br /> <br /> (a) 73.5ns. (b) 55ns. (c) 50ns. (d) 74.75ns.</p> </blockquote> <p>My working was as follows: (0.95x20) + 0.05 (0.01(10000+500+20) + 0.99(500+20))</p> <p>Leading me to an answer of 50 being C), however others have seem to have chosen D) as their answer</p> <p>Any help would be appreciated.</p> https://cs.stackexchange.com/q/130217 1 proof non-empty AVL tree Eden Gilad https://cs.stackexchange.com/users/126486 2020-09-16T20:23:02Z 2023-10-04T05:07:00Z <p>The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.</p> <p>The root is not considered an single child.</p> <p>let mark in numOnly a number of vertices in T that hold the attribute &quot;single son &quot;, and ‘with n we mark the total number of vertices in the T tree.</p> <p>i need to prove that every non-empty AVL tree has inequality <span class="math-container">$\frac{numOnly}{n}\leq \frac{1}{2}$</span></p> https://cs.stackexchange.com/q/126830 2 Is process address space part of Process Control Block(PCB)? Always_Beginner https://cs.stackexchange.com/users/84137 2020-06-06T13:28:45Z 2023-10-03T11:08:26Z <p>I recently read about the process address space and PCB and trying to link them together. I don't find much literature on their relation. </p> <p>Is the process address space a part of the PCB data structure?</p> https://cs.stackexchange.com/q/109081 0 I want to find the number of steps it takes to find the GCD by Euclidean Algorithm Talha Chafekar https://cs.stackexchange.com/users/93326 2019-05-08T00:29:10Z 2023-10-04T09:31:40Z <p>Let's say I have two numbers a and b. I want to find the number of steps it takes to find the GCD by Euclidean Algorithm by a closed formula which includes parameter a and b. If I go by this implementation , in how many steps will I reach gcd:</p> <pre><code> public static int gcd(int a, int b) { if (a == 0) return b; return gcd(b%a, a); } </code></pre> https://cs.stackexchange.com/q/108580 0 Aggregate text data of some particular column Encipher https://cs.stackexchange.com/users/90585 2019-04-26T18:08:23Z 2023-10-03T10:04:45Z <p>I have a dataset as follows</p> <pre><code>Biodata last_name first_name age Description Hobby Smith John 20 In high school Music Johnson Robert 45 Software Developer Gardening Williams David 15 Junior school Baseball Davis Michael 65 Traveler Skydiving Miller Molly 25 Scientist Cycling </code></pre> <p>Now I got a question from a assignment that <strong>Aggregate text data under “Description” and “Hobby”</strong></p> <p>I cannot understand what is the meaning of Aggregate text data?</p> <p>If any one understand the question please share their view point. I want to know it theoretically how could any one aggregate text data depend upon description and Hobby column.</p> <p>This is a coding assignment of python. But currently I don't bother about coding. I want to know the theoretical meaning of this question and want to solve it manually.</p> <p>Thank you in advance</p> https://cs.stackexchange.com/q/105361 0 algorithm analysis - complex dependant nested loop candh https://cs.stackexchange.com/users/101065 2019-03-09T11:45:11Z 2023-10-02T23:07:15Z <p>First of all, I know there are many questions like this on the site. But I think this case is a bit different.</p> <p>Consider the following code:</p> <pre><code>int i, j, k; for (i = 1; i &lt;= n; i++){ for (j = 1; j &lt;= (n-i); j++) { System.out.print(" "); } for (k = 1; k &lt;= (i-j); k++) { System.out.print(i); } System.out.println(); } </code></pre> <p>What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.</p> <p>How our professor told us to compute complexity is just by adding all the summations together from every line. </p> <p><span class="math-container">$$(n+1) + \sum_{j=1}^{N-i} + \sum_{j=1}^{N-i} + \sum_{k=1}^{i-j} + \sum_{k=1}^{i-j} + n$$</span></p> <p>However, I've never seen examples with summations like <span class="math-container">$\sum_{j=1}^{N-i}$</span>, It's always either <span class="math-container">$\sum_{j=1}^{N-1}$</span> or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)? </p> https://cs.stackexchange.com/q/50767 8 Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently? calm-tedesco https://cs.stackexchange.com/users/43731 2015-12-15T13:46:28Z 2023-10-04T09:53:27Z <p>First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.</p> <p>As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (<a href="https://en.wikipedia.org/wiki/Integer_factorization">https://en.wikipedia.org/wiki/Integer_factorization</a>) puts it, </p> <blockquote> <p>When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known; an effort by several researchers concluded in 2009, factoring a 232-digit number (RSA-768), utilizing hundreds of machines took two years and the researchers estimated that a 1024-bit RSA modulus would take about a thousand times as long.</p> </blockquote> <p>So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.</p> <p>The time it takes the code to check if a number is prime doesn't grow exponentially with the input. </p> <pre><code>function[]=prime(n) tic f=floor(sqrt(n)); for i=2:f if rem(n,i)~=0 b=0; else b=1; disp(i) break end end if b==0 disp('prime') else disp('not prime') end toc end </code></pre> <p>And so I go back to the question in the title. What is wrong with my reasoning?</p> https://cs.stackexchange.com/q/35744 11 What is the difference between variables and pointers? Russell Ormes https://cs.stackexchange.com/users/26222 2014-12-29T03:13:15Z 2023-10-03T05:10:01Z <p>Whist reading an article outlining differences in <a href="http://blog.cleancoder.com/uncle-bob/2014/11/24/FPvsOO.html">OO and Functional programming</a> I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked up pointers to refresh my memory. </p> <p>Pointers are variables that contain a reference to a memory address. They can be considered to point to the data that is contained in that memory address if such data exists. Or, as in the case in the article, they might indicate the entry point to a section of code and can be used to call that code. </p> <p>Why is this different from a variable? Variables are symbolic names for memory addresses and compilers will replace the name with the actual address. This means that variables contain references to memory locations and can be considered to point to the data at that address if such data exists. </p> <p>If the difference is in behaviour (maybe a pointer cannot be reassigned at runtime, or can only be assigned a symbolic variable name, not any other value) doesn't that mean it is just a variable of a particular type, the pointer type? In just the same way a variable declared to be of type integer is restricted by the compile in what it can be used for. </p> <p>What am I missing here? </p>