# All Questions

29,681 questions
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$.
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 ...
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: ...
10 views

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 ...
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?...
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$ (...
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 ...
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 ...
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? ...
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!
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, ...
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.
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$-...
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....
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: ...
27 views

### Time complexity of recurrence function with if statement

Given the following code. ...
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? ...
### 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 ...