All Questions

-1
votes
1answer
4 views

Regular expressions for some languages

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$.
-1
votes
1answer
8 views

Term for an A*-like pathfinding strategy where only the heuristic goal distance matters

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 ...
1
vote
1answer
12 views

L1 and Ln cache: when are they written?

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: ...
0
votes
0answers
10 views

Check if a lambda constructor is well-typed

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\ ...
1
vote
0answers
16 views

Perfect Completeness of AM protocols?

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 ...
0
votes
1answer
23 views

Hitting probability of random walk within given number of steps

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 ...
1
vote
2answers
29 views

Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? [duplicate]

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

Floyd–Warshall algorithm on an undirected graph contains negative weight edges

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 ...
0
votes
0answers
17 views

Find all polygons from a set that overlap a given polygon (convex case)

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 ...
1
vote
1answer
20 views

general question amortized cost and worst case

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). ...
-1
votes
0answers
28 views

What approach is best to a problem such as the closest string? [on hold]

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 ...
0
votes
0answers
17 views

How to do if a potential function Does not work? Amortized analysis

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 ...
-1
votes
0answers
22 views

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

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

Can I ever get my data back? HELP [on hold]

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 ...
0
votes
1answer
28 views

Confused about pumping lemma, What i'm missing?

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$...
2
votes
2answers
745 views

How does a computer interpret real numbers?

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 ...
0
votes
0answers
27 views

How to generate random strings from Context-Free Grammar in GNF

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 ...
0
votes
0answers
25 views

how fingerprints are converted into binary? [on hold]

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.
0
votes
0answers
19 views

Insert 8,5,18,15 using Red -Black concept? [on hold]

May I know whether the below link answer is right or wrong?
0
votes
1answer
29 views

Finding often repeating substrings in multiple strings

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 ...
3
votes
1answer
74 views

Can this equation be solved in polynomial time?

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$ ...
3
votes
1answer
30 views

Word Problem over Finite Groupoids

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://...
3
votes
1answer
43 views

What's the difference between: operational, denotational and axiomatic semantics?

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 ...
0
votes
1answer
24 views

N-gram language model question

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

Radix Sort for unequal strings not working [on hold]

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 ...
2
votes
0answers
34 views

Efficient algorithm for numerical estimation of 3D rotation matrix

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 ...
0
votes
0answers
11 views

How do you explain each step of these two lines? [on hold]

I came across this on the internet, and wasn't sure how each step of the code execution worked.
1
vote
0answers
19 views

How do I implement fixed block storage file system in database from typical file-level file system?

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 ...
1
vote
1answer
26 views

Two Minimax AIs playing against each other

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 ...
2
votes
1answer
61 views

Why use heap over red-black tree?

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 ...
1
vote
1answer
51 views

An algorithm that find the max X/Y in a polygon in O(log n)

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 ...
3
votes
0answers
58 views

Which algorithm can I use to allocate human resources?

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 ...
0
votes
0answers
23 views

Matlab simulation: conflicting results [migrated]

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)...
0
votes
0answers
11 views

What is the name for “referenced” datatypes vs non-referenced datatypes? [on hold]

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 ...
-1
votes
0answers
25 views

Find a context-free grammar for L={(a^n b^m)^z d^z} [duplicate]

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

Augmenting a tree such that we preserve the insertion operation optimal runtime

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$ (...
-1
votes
0answers
70 views

Extended Boolean Logic

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 ...
5
votes
2answers
2k views

Why do ¬, ∀ and ∃ have the same precedence?

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 ...
1
vote
0answers
45 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

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? ...
0
votes
1answer
33 views

Context free grammar for L={ ((ab)^n)^m }

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!
5
votes
1answer
44 views

How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

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, ...
1
vote
1answer
35 views

AVL tree worst case height proof

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.
4
votes
0answers
54 views

Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

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$-...
-1
votes
0answers
22 views

Multiprogramming within a paged system

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....
1
vote
1answer
25 views

Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) [duplicate]

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: ...
1
vote
1answer
27 views

Time complexity of recurrence function with if statement

Given the following code. ...
1
vote
0answers
19 views

How do I get the NAND gate configuration for full adder from the logic table?

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? ...
2
votes
2answers
33 views

What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

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 ...
0
votes
1answer
16 views

Finding topologically sorted connected components in directed acyclic graph

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 ...

15 30 50 per page