All Questions

Subject reduction is a well and widely used property of typed rewriting systems. Subject expansion is much less known. What are the applications of this property and which systems enjoy it?

Given a cycle of $n$ vertices and each vertices of the input graph $G$ assigned a weight. We want to find an independent set of cycle such that weight of the vertices taken in the independent set is ...

Please note that this is about a thread-safe LRU cache (not simply a LRU cache as specified in https://leetcode.com/problems/lru-cache/description/). It isn't a duplicate of LRU cache design question ...

I have a question, wherein: Given an array of non negative integers A, and a range (B, C), find the number of continuous subsequences in the array which have sum S in the range [B, C] or B <= S &...

I am looking for a data structure to store a set such that given two instances of size O(n) which are known to have non-empty intersection, the minimum element of the intersection can be found in O(...

Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem: Input: words $x_1,\dots,x_n \in \Sigma^*$ Question: does there exist a ...

I'm trying to write a program that pulls my data from TeamTrack so I can use it for other things. Is there a TeamTrack api or some way to do this? I have looked far and wide and can't for the life of ...

I know I must be getting stuck on notation. However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf. They define what preserving a propositional ...

Let's I have to make the following reduction: $$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$ The technique of building the reduction is - Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in ...

Why should we pay money for the Internet connection, while someone who creates website also pays a lot of money annually? Why it should not be free to use?

So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you ...

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...

my solution is that $L\in co-RE$ by showing that $\overline{L}\in RE$ TM $M$ on input:$\langle M_1,M_2,w\rangle$ Build TM $M_1,M_2$ Simulate $M_1$ on $x\in\Sigma^*$, before that check if $x\neq w$ ...

i have a question for the knapsack problem that i am totally not able to comprehend properly. I know how to knapsack works with the 0-1 approach and fractional. kindly can i be helped with this ...

I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. From the research that I have done up to this point, I ...

I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array. The idea ...

So far I've proved the following: $2n \geq \ln(2n) > \ln(n+2)$ for $n \geq 3 $ The proof must be without the use of calculus but I have no idea on how to proceed.

Hopefully this question is fairly straight forward. I need to convert a String representing a decimal number to another base 2^16. I have a way to store very large numbers and perform arithmetic on ...

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...

I came across this circuit that swaps logical signals: However I don't understand why would you need to use logic gates. Would it be possible to just connect the A on the left to the B on the right ...

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....

Im a undergrad student of CS Engg. and I am really weak in this topic I wish to hone my programming skills but combinatorics doesnt let me What can I do to counter this? Should I start learning it ...

Branch tables are usually described as an efficient way a compiler can implement a switch statement, and that actually seems how GCC and Clang do it (and LLVM even has an opcode just for that). If a ...

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$. Does ...

Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black ...

I am working on a problem that can be simplified to consist of the following: an initial symbol tree a list of interpretations (an interpretation is a transformation guarded by a predicate) a ...

We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}. ...

By what provision is context switching disabled in a process ? Or is it the case that if a process is in in kernel mode , context switching is disabled by default ?

According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is ...

I was reading about UDP and TCP. TCP is a stream-oriented, connection-oriented protocol and always delivers the segments in order to the application layer. But UDP being connectionless, does it also ...

You are viewing a webpage and suddenly the internet connection goes off. Unfortunately, you have to turn off the computer but you don't want to lose the data. is there a way to store it on ROM without ...

Can someone give me simple definition of a counting semaphore ?

Is there a proof that all terms of type $\forall{a}. a$ are operationally $\bot$, in a non-weakly-normalising version of System F? If you ask a free theorem calculator such as this one for the free ...

Referring to this website : Toptal This website is confusing me, on clicking on play all, website starts to play animations of all available algorithms sorting the given arrays, which shows shell ...

Are there any advantages of using threads in single core system? And if there , your answer still valid if we have One-to-One mapping between user and kernel threads? Why ?

Let's say we've got an array like this [1,2,3], I'm doing an operation for all pairs of the items, (1,2), (1,3), (2,3), by doing a double loop, is there a method or algorithm to reduce the ...

In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation: \begin{equation} \frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\...

I understand the concept of an R-Tree and how it is used to spatially index and store geometric objects such as polygons and points, but I am not sure how to construct it by choosing MBRs that group ...

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...

Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...

Description of the problem: I am modeling checking a distributed protocol against a global property with TLA+ developed by Leslie Lamport. The global property is defined on all states of a behavior (...

Assume a process execution interrupted at the middle and CPU started executing a different process.How does the OS handle this situation?

I'm wondering if there a way to enable a CNN to learn the non-linear transfer between two images. For example, the original image looks like The target image looks like I would like to develop a CNN ...

I am writing a pretty simple program in C++ in which I have to read from standard input n cities in consecutive n lines (here I use getline to pass each city as a string), and these n lines are ...

I am looking for an algorithm(s) that can compute a global ranking (partial ordering) given individual rankings, in some kind of principled manner. I want to establish a partial-ordering of some ...

Raina et al. introduced self-taught learning (essentially semi-supervised learning with unlabelled examples unrelated to the training set classes that we are trying to classify) to the ML community in ...

I'm trying to decode the following Hamming sequence (using EVEN parity and knowing there is a 1-bit error), which contains an ASCII value: 01100110101 I've tried ...

Loving lispers often say you can do anything you want in lisp! I was asked this week by a colleague if it is possible in common lisp to define a new numbering schemes, so, for example, all my digits ...

Let's say we have complete graph, we want to build data structure that will allow us two things: Deleting edge from the graph. Telling if the nodes $u$ and $v$ are connected by at least one path in ...