All Questions

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
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.
0
votes
0answers
4 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 ...
2
votes
1answer
749 views

Turing Machine remembering copied symbols

So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting ...
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 ...
0
votes
0answers
5 views
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 ...
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 ...
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? ...
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
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
vote
3answers
79 views

Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic

How can I prove that $\Box(P\rightarrow Q)\rightarrow (\Diamond P\rightarrow\Diamond Q)$ is valid in linear temporal logic (LTL)?
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 ...
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 >}",...
9
votes
2answers
637 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\}$ ...
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^...
-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-...
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
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, ...
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}...
-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 ...
-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 ...
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 ...
84
votes
11answers
13k views

Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
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 ...
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
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 ...
1
vote
2answers
102 views

Correct term for a priority queue with unique elements

Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element ...
1
vote
2answers
39 views

Term for the tree of all paths starting from a given vertex in a graph

What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex? This is the tree that is implicitly or explicitly constructed when ...
-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
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
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 ...
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 $...
1
vote
1answer
75 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
6
votes
1answer
155 views

Incremental strongly connected components

For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data ...
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 ...
2
votes
1answer
51 views
+50

How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
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 ...
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 ...
2
votes
3answers
880 views

Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which ...
6
votes
2answers
112 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
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: ...
3
votes
2answers
47 views

Enumerate over all halting Turing Machines?

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
0
votes
3answers
92 views

Solving recurrence equation $T(n)=T(n^{2/3})+17$

How can the following recurrence equation be solved by one of three main ways: $$T(n)=T(n^{2/3})+17$$ I have tried solving it by the iteration way. However it does not work for me since I can't find ...
1
vote
2answers
49 views

Build a balanced binary tree from list in linear time

I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in ...
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 ...
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
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 ...
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 ...

15 30 50 per page