All Questions

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

Time complexity of recurrence function with if statement

Given the following code. ...
1
vote
0answers
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? ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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-...
2
votes
1answer
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 >}",...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
15 views

Is this inequality about Hamming code correct?

i am wondering if the following is correct: if my Hamming code allows repairing of no more than $k$ errors inclusive and $m$ is the number of information bits and $r$ the check bits, then $\sum _{i=1}...
0
votes
1answer
12 views

Grouping/Clustering results based on shared values

I have a data set that is similar to this: 10,000 jobs with 200,000 applicants which are linked to a job. I'm looking to cluster the shared jobs based on applicants that they share, am I reinventing ...
-1
votes
0answers
10 views

Difference of simulated annealing and random search for generating crossword puzzles?

I heard that when one wants to write a program to make a crossword puzzle, he can use for example simulated annealing as in the thesis Crossword Construction using Constraint Satisfaction and ...
-1
votes
1answer
20 views

Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time

We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, ...
1
vote
0answers
21 views

Global indexing of shared nodes in parallel

Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of ...
-2
votes
0answers
26 views

Sort an array of large number (every programming language) [on hold]

enter an array of array elements (Unlimited number of array elements). Then sort up gradually. If you meet -1, keep the position of -1
9
votes
2answers
629 views

Language involving irrational number is not a CFL

I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
2
votes
1answer
52 views

Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?

One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a ...
1
vote
0answers
17 views

Join Order Optimization

Based on the schema on the following picture: Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? I am suppoused (and that's what I tried) to use ...
0
votes
1answer
28 views

Using Union find to check whether there is a cycle in a graph

I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. ...
1
vote
1answer
28 views

Asymptotic complexity of function with two Input variables

Suppose I have a function with two input below. $f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$. Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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.
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
6
votes
1answer
72 views

Index matching algorithm without hash-based data structures?

I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time. Given two arrays $...
0
votes
0answers
15 views

VPN encryption per device [migrated]

When you use the same VPN on several devices, if one device is compromised/hacked, can it be used to decrypt the traffic of the other device using the same vpn? Or does it weaken the encryption of the ...
2
votes
1answer
28 views

Constructing a reduction between two languages about pairs of Turing machines

I'm curious about a potential relation between the following two languages. $L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$. $L_2 := \{\langle M_1, M_2 \rangle : L(M_1) \...
0
votes
0answers
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?...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
45 views

Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma

Showing that the language $L$ with $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}...
4
votes
1answer
42 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
0
votes
0answers
22 views

Probabilistic r-way cut set algorithm

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph. In this generalized version, instead of ...
-2
votes
0answers
11 views

How can I build a web page with web mining my artificial intelligence? [on hold]

I would like to build a webpage which use the web-mining but for cryptocurrency mining but also my artificial intelligence training in the web page background. Can we do this? How can I do?
-1
votes
0answers
16 views

Could Web 3.0 exist without cloud and vice-versa? [on hold]

I would want to know if could web 3.0 exist without cloud and vice-versa? Would I want to know also why? and some examples. Thank you.
0
votes
0answers
18 views

Random Forest - Conditional Permutation Importance

I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features. Besides the most commonly preferred ...
-1
votes
0answers
34 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
7
votes
2answers
436 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
2
votes
0answers
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 ...
0
votes
0answers
34 views

Number of ways in which you can traverse N meters by doing jumps of 1,2,3,4 or 5 meter length [on hold]

I am sorry if this is not the right platform to ask this question. I have searched for a solution for the past two days and haven't been able to find it. The problem is as follows: Design an ...
0
votes
0answers
36 views

RAM and Turing machines: time complexity of simulation

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

15 30 50 per page