A Peer reviewed online Journal keeps track of all the articles received by it using an online system. It has a list of reviewers in which reviewers are added or deleted. A reviewer can be assigned articles of one area only. An article is identified by an article id, title, authors (can be more than one), expertise area and status. On submission of an article, it is sent to two reviewers who are given a time of two weeks to review the article and send back the comments. You need not make this process ...
An e-commerce store sells Grocery products. It takes online orders of registered customers. It takes orders of only those products which are available in the store. The basic product information that is displayed online includes Product ID, Product Name, Date of Manufacture, Best Before date, Price, basic details of the product and discount on that product, if any. An order includes order number, customer ID of the customer who placed the order, address where order is to be delivered, date ...
INDIRA GANDHI NATIONAL OPEN UNIVERSITY Maidan Garhi, New Delhi-110068, INDIA (For Information Only) B.Ed. Entrance Test October, 2016 Results held on 23.10.2016 ...
Problem Detail: Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$? Is it possible to write a polynomial time algorithm for it? I asked this question on mathematics and got no answer by far. Asked By : Gigili Answered By : Artem Kaznatcheev Although you already know from the other answers that the question is solvable in polynomial time, I thought I would expand on the computational complexity ...
Problem Detail: Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$ To proof that the language $L$ is undecidable I should reduce something to $L$, right? I tried with the classic $A\ TM$, but I could not figure out how to reduce properly. How I can I proof that $L$ is undecidable? Asked By : Rafael Castro Answered By : David Richerby The usual reduction from the halting problem: for example, the same reduction that shows ...
[Solved]: When does the function mapping a string to its prefix-free Kolmogorov complexity halt?
posted on , by Akshay Mishra
Problem Detail: In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that $\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$, where $K(\sigma)\downarrow$ means that $K$ halts on $\sigma$, $\sigma$ being a binary string. $K$ denotes the prefix-free Kolmogorov complexity. When does $K$ halt? I think it only halts on a finite number of inputs, since the classical proof on non-computability of the Kolmogorov complexity gives an ...
Problem Detail: I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. Here is the example: "Here is a TM that accepts the non-context free set $\{a^nb^nc^n \mid > n\geq 0\}$. Informally, the machine starts in its start state s, then scans to the right over the input string, checking that it is of the form $a^* b^* c^*$. It doesn't write anything ...
Problem Detail: While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the buckets it should loop through. More precisely: each thread gets an ID, by that ID it fetches its triangle from the memory (3 integers each) and by those 3 it fetches its vertices(3 floats each). Then it transforms the vertices into integer grid points (currently 8x8x8) and transforms ...
Problem Detail: I am wanting to try and prove that the English language is not regular. The alphabet is the set of all words in the English dictionary. Looking at sentences, I was able to use this pattern of sentences { [ (determiner) (noun)]n (verb)n where n is >= 1} ⊆ of the English language and { [ (determiner) (noun)]m (verb)n where m ≠ n} ∩ of English determiner is anything like the, my etc. Noun is any noun and verb is also any verb. All three of these (determiner, noun, ...
Problem Detail: I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ edges. Assuming we have no negative edge weights at all, can we use Dijkstra's algorithm for the same? My thoughts/algorithm: I was wondering if instead of having a $dist[u$] array (storing the best known distance from s to u), we could use a $dist[u][k]$ table to store the best ...
Problem Detail: I'm reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory. In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a single-reader, single-writer (SRSW) safe Boolean register. So, the only difference is that the new register supports multiple readers, but the consistency guarantee (safe) is the same. The implementation (figure 4.6) uses an array of SRSW ...
[Solved]: Is the difference of a non-recursive and recursive set recursive?
posted on , by Akshay Mishra
Problem Detail: I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively enumerable (to generate its elements, I can generate B's elements and check if they are in A). If A is the empty set or $A \cap B$ is the empty set, it's easy. Otherwise, I believe $B-A$ is not recursive (I can't tell if a number is in B, since B is not recursive) and $A-B$ is ...
Problem Detail: I'm trying to figure out if there is a proper or commonly accepted name for this particular function (f). float clamp(float min, float max, float v) { if (v < min) return min; else if (v > max) return max; else return v; } float f(float min, float max, float v) { float t = (v - min) / (max - min); return clamp(0.0, 1.0, t); } Asked By : Colin Basnett Answered By : Big Al This is sometimes called "0-1 normalization" or "feature scaling". ...
Problem Detail: I have designed a classifier M which recognizes gestures and classifies it under any category always. A gesture is classified based on the hamming distance between the sample time series y and the training time series x. The result of the classifier are probabilistic values. There are 3 classes/categories with labels A,B,C which classifies hand gestures where there are 100 samples for each class which are to be classified (single feature and data length=100). The data are different ...
[Solved]: Can one consider living (biological) cell to be Turing Complete?
posted on , by Akshay Mishra
Problem Detail: Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending on input provided by the tape. From this point of view cells have some properties very similar to UTMs, the DNA is in an essence a tape of instructions that can be read and written to. Rest of the cell behaves similar to action table, defining rules that guide which part of DNA ...
Problem Detail: Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll. A table in the database will record the time-in and time-out for each project as a row. A user should be able to sign out and back into the same project multiple times throughout the day, and also can enter time out of order (e.g. sign into Project X at 9:00 AM to 2:00 PM, then into Project ...
Problem Detail: Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8: A: 0 0 0 B: 0 0 1 C: 0 1 0 D: 0 1 1 E: 1 0 0 F: 1 0 1 G: 1 1 0 H: 1 1 1 Now I have the additional constraint that each column must contain at most p bits set to 1. For instance for p=2 (and n=8), a possible solution is: A: 0 0 0 0 ...
Problem Detail: How would I rewrite an XOR gate into the three basic logic gates (AND, OR, NOT). To be more specific, I have to write it in such a way with 2 NOT gates, 2 OR gates, and 1 AND gate. I also have to do it with 1 OR gate, 2 AND gates, and 1 NOT gate. I'm not looking for just the answer, I'm looking for a way to come up with the answer. Thanks! Asked By : 4everPixelated Answered By : Pål GD Hint: $a \oplus b = \neg \big( (a \land b) \lor (\neg a \land \neg b)\big)$ ...
[Solved]: Can nodes in red-black trees have one nil child and one non-nil child?
posted on , by Akshay Mishra
Problem Detail: I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is the number of nodes, and I don't see how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of n. Asked By : Kelmikra Answered By : hengxin Can ...
[Solved]: Why do relational databases use 2PC for distributed transactions over the likes of Paxos?
posted on , by Akshay Mishra
Problem Detail: Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case of Paxos. Why do relational database use 2PC in real world? Also 2PC is not fault tolerant because it uses a single coordinator whose failure can cause the protocol to block. Asked By : Nitish Upreti Answered By : Andrei One of the reasons is the message complexity. ...
Problem Detail: Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail). Is there a simple algorithm that doesn't require extra structures that makes $e$ at the head? meaning to get us to the queue $eabc@d$? P.S.: I need an algorithm like that for the purpose of a queue automaton. Asked By : TheNotMe Answered By : Gari BN If you can only push (enqueue) ...
Problem Detail: A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests a refund (i.e. the machine gives back the coin: $\bar b$). This dispenser can be modeled by the following CCS process: $$ M \stackrel{\mathrm{def}}= c.(d_{\text{tea}}.\bar e_{\text{tea}}.M + d_{\text{coffee}}.\bar e_{\text{coffee}}.M + r.\bar b.M)$$ A civil war raises the price ...
Problem Detail: I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable. What is the proof that Σ* is decidable? Asked By : Charles Answered By : Andrej Bauer Theorem: The set $\Sigma^{*}$ of all words is decidable. Proof. According to the definition of decidability, we must provide a computable function $d$ which takes a word $w$ and outputs $1$ if $w \in \Sigma^{*}$, and outputs $0$ if $w \not\in ...
[Solved]: How do I explain that a polynomial time reduction is in fact polynomial time?
posted on , by Akshay Mishra
Problem Detail: I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete. My solution is as follows, which is pretty much copied almost 100% from a textbook example with only an extra requirement for satisfiablity at the end... $$QuadSat\leq_{p} Clique$$ Let $\phi$ be a formula with k clauses such as $$\phi=\bigwedge_{1}^{k}(a_k\vee b_k\vee c_k)$$ The reduction ...
Problem Detail: I have the following Bayesian Network and need help with answering the following query. EDITED: Here are my solutions to questions a and b: a) P(A,B,C,D,E) = P(A) * P(B) * P(C | A, B) * P(D | E) * P(E | C) b) P(a, ¬b, c ¬d, e) = P(a) * P(¬b) * P(c | a, b) * P(¬d | ¬b) * P(e | c) = 0.02 * 0.99 * 0.5 * 0.99 * 0.88 = 0.0086 c) P(e | a, c, ¬b) This is my attempt: ...
Problem Detail: I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer. E.g. In this set of notes, it says: Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits. There must be a gap in my understand because I thought I could compress all ...
Problem Detail: Let $p$ be the six-figure Boolean function with the following definition: $p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{cases} true & \text{if } x_{0}=x_{5} \text{ and } x_{1}=x_{4} \text{ and } x_{2}=x_{3}, \\ false & \text{else.} \end{cases}$ This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a palindrome. Provide ...
Problem Detail: I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero. $$ \lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}} $$ But I'm not sure how I can reduce this expression. Asked By : David Faux Answered By : Reza $\qquad \begin{align} \lim_{x \to \infty} \frac{ (\log(x))^{99} }{x^{\frac{1}{99}}} &= \lim_{x \to \infty} \frac{ (99^2)(\log(x))^{98} }{x^{\frac{1}{99}}} \\ &= \lim_{x ...
Problem Detail: Given a $0,1$ (binary) integer program of the form: $$ \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} &A\vec{x} = \vec{b} & \quad \forall i\\ &x_i\ge 0 & \quad \forall i\\ &x_i \in \{0,1\} & \quad \forall i \end{array} $$ Note: the size of $A$ is not fixed in either dimension. I believe this problem has been shown to be hard to approximate (strongly ${\sf NP}$-Complete) Garey & Johnson. If so, is this still the case when $A$, ...
[Solved]: Natural occurrences of monads that make use of the category-theoretical framework
posted on , by Akshay Mishra
Problem Detail: Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, i.e. with uncountably infinite state sets and different notions of traces. To this end, he goes up through several layers of abstraction to finally end up with the notion of monads which he combines with measure ...
Problem Detail: In Sipser's book there is a section describing how to decide $\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$ in polynomial space. To do so, it shows $\overline{\mathrm{ALL}_\mathrm{NFA} }$ is in NPSPACE. I don't understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that ...
Problem Detail: Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states: Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether of not there exist two elements in S whose sum is exactly x. At first, I had no idea how to solve it since I thought you couldn't access elements of a set by index, but assuming you could, here was my solution: First off, we sort the set S, and then for every element y ...
