# All Questions

29,670 questions
2 views

### Avl tree worst case height proof

The worst case height of AVL tree in 1.44 * log(n).How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.
4 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$-...
3 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....
8 views

### Asymptotic notation: Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n))

I was reading Cormen's book, Intro. to Algorithm. The book literally explained the three asymptotic notations very well. However, there was this para: Technically, it is an abuse to say that the ...
5 views

### Time complexity of recurrence function with if statement

Given the following code. ...
10 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? ...
18 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 ...
10 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 ...
12 views

### How to re-color a red-black tree with a specific property

Let us consider a red-black tree in which for every path from the root to a leaf of minimal depth, there is exactly one red-colored vertex in it. How should we re-color the tree so that, after the re-...
9 views

### checking whether a language is turing recognizable

After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept. so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}",...
26 views

### Datalog Self Interpretation

According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO[LFP] can define its own semantics, though the proof (of ...
15 views

### Longest common sequence matrix giving wrong answer

I am trying to find longest common sequence for these two strings SHINCHAN NOHARAAA The common sequence is NHA of length 3 ...
13 views

### The longest simple path on a cycle

We have n cities {1,2,3,...,n}. The city i is connected by two-way road with the city i+1. The city n is connected with the city 1 by two-way road. The distances between cities are known. Let say ...
15 views

33 views

### How to perform particle swarm optimization clustering of results obtained from tf-idf vectorizer?

I have a collection of news articles. I have performed tf-idf operations on them. I am using python as programming language so it was just the use of TF-IDF vectorizer function. I now have the ...
48 views

### Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the ...
41 views

### NP-Completeness and commutative property

If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$? My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.
25 views

### Why does Skillicorn's Taxonomy allow us to design 30 models?

In Skillcorn, David B, "A Taxonomy for Computer Architectures", IEEE Computer, 21(11):46-57, Nov 1988, a taxonomy of multiprocessor architectures is described. My teacher said that Skillikorn's ...
20 views

### How does a Turing machine compute when its head is at the right-hand end of its configuration?

I'm reading Sipser's Introduction to the Theory of Computation (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of ...
30 views

### Devising a way to spot a contradiction given a set of statements using graphs

If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John. Would there be a way to figure out that there is a contradiction ...
18 views

### why doesn't the command prompt show the cpp file that are saved in Desktop or Documents? [on hold]

My problem is I have cpp files in desktop and documents. I wrote a c++ code using notepad++ and tried to build it through the command prompt. But when i try to access the directory of where I saved my ...
72 views

14 views

### How do I find the sampling rate? And what is the formula for sampling rate? [on hold]

Suppose you have a 100 MHz CPU and a A/D converter with an 8 kHz sampling rate. Samples of the A/D converter are 32-bits. What is the sampling rate? and how do I get the formula for the sampling rate?...
16 views

### Persistent Memory Emulation Platform (PMEP) [on hold]

How can I access to Persistent Memory Emulation Platform (PMEP)? It is supposed to be designed by Intel to simulate Non-Volatile Memory. It's mentioned in a few articles but quite unclear how to get ...
30 views

### Solving a in/equality constraint problem with graph search

You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types. An equality constraint of the form xi = xj for some i!=j. An ...
45 views

24 views

### Problems in $\textbf{DSPACE}(\log^2 n)$

Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$ and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations ...
48 views

### proving big theta [duplicate]

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$ I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as $$10n^3+3n \leq c_1n^3$$ 0 \leq ...
436 views

### Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
28 views

### Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
My RAM machine is very simple: it has $k$ tapes, an input tape and one special control tape it has an infinite memory (array called $A$) which can be accessed randomly the control tape is read ...