All Questions

Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00. $\{a^n b^m : n ≥ 4, m ≥ 3\}$. Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.

I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...

I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained: ...

In basic type inference for 𝜆-calculus with parametric polymorphism à la Hindley–Milner, when can we say that we cannot give a type to a lambda constructor? For example $$(λx.λy.y(x\ ...

I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...

I understand that $\phi$ is a null symbol. why concatenation of any language L with $\phi$ is $\phi$ rather than L ?

According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances ...

Problem: Given a set of N non-overlapping convex polygons {S_i, i=1..N} defined by their vertex coordinates (x,y) and a convex polygon P, also defined by its vertex coordinates, find all polygons S_i ...

lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1). ...

A clear rehap on the conceptual approach to the closest string would be appreciated. Especially to clear the confusion I'll provide a link to a computer script written with the linear approach in ...

Here is an example taken from CLRS. q)Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a ...

Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?

About 2 weeks ago I was doing a decryption to a partition on an External HDD.. - encryption type:(Bitlocker Encryption). But Unfortunately my laptop had shut down during the operation. since then I ...

When I apply pumping lemma on this language: ${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular. let ${n=4}$, then $w=010000$...

I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers. But I want to know how does ...

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...

I have searched on internet but didn't get any exact answer of method that how fingerprints are converted into binary that is understand by machine and keep record of every human.

May I know whether the below link answer is right or wrong?

I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the ...

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...

...

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...

Recap of the terms from the dictionary: semantics: the study of meaning in a language (words, phrases, etc) and of language constructs in programming languages (basically any syntactically valid part ...

I have this question I found regarding n-gram modelling in the Speech and language processing text book: ...

I've been trying to get a working radix sort for days now, and I'm nearing my wits end. First I thought that LSD would work for strings of unequal lengths, then I read somewhere that MSD radix was the ...

I am writing a computer vision related program and stuck on a problem. I have a system of quadratic equations where M is a constant 3x3 matrix, is the 3x3 identity matrix, and we are solving for the ...

I came across this on the internet, and wasn't sure how each step of the code execution worked.

I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size. Chunking can be used I found, but how ...

I am trying to have my Minimax AI chess players play against each other. I was a bit confused about an implementation detail. Let's call black my first minimax AI ...

Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time. However, red-black tree ...

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$. The polygon is represented by an array of its vertices where each vertex is represented by its ...

I have to manage shifts of a variable number of people inside several rooms for a week. Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same ...

I have implemented a simulation of the model (for $i=1,...,N$ representing nodes of a graph) $$\frac{d\omega_i}{dt} = P_i -\alpha_i \omega_i + K \underset{i \neq j}{\sum_{i=1}^N} \sin(\phi_i - \phi_j)...

In Javascript const a = {red: "red"} const b = a; then the object b is not different than a. It is literally just a reference to a. Objects/Arrays follow the ...

need a CFG for the following language: $L={(a^n b^m)^z d^z}$ $m=2n, \ \ \ n,z \\$≥0 Any ideas?...

Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (...

Find the results of the following substitutions. Just give the answer and explain the reasons if the result is undefined: a) (∀𝑥)(𝑓(𝑥) < 7)[𝑥 ≔ 7] b) (∀𝑦)(𝑓(𝑥) < 7)[𝑥 ≔ 7] There is ...

I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have ...

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...

I want to write a cfg for the following language: $ L = {((ab)^n)^m }$ $m,n >= 0$ this language produces (abababababab) where: $n=2, m=3 \\ or \\ n=3, m=2$ I have no idea what to do with it!

int n; cin >> n; int sum = 0; for (int i = 1; sum <= n; i++) { sum += i; } If I assumed that $N = 100$, the loop will run $13$ steps, ...

The worst case height of AVL tree is $1.44 \log n$. How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with $1\le R,C\le 100$, $1\le H\le R$, $1\le W\le C$, an $R\times C$-matrix $L$ and an $H\times W$-...

So lets say that have a system with a PMMU that supports 10 bit physical addresses, and its processes are only able to use 8 bit logical addresses. The page size is 64 byte and the word size is 1 byte....

I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms. The book explained the three asymptotic notations literally very well. However, there was this paragraph: ...

Given the following code. ...

I'm self-studying, but I've gotten stuck already. If I'm given the logic table for a full-adder or any two-output table, how do I figure out the NAND-gate configuration, preferably methodically? ...

In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$. However, I went through the following ...

I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am ...