# All Questions

6 views

### What's are the consequences of subject expansion property?

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?
10 views

### Is it possible to solve maximum weight independent set in linear time for a cycle?

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

### How to design a “multithreaded” LRU cache using C++ (unordered_map and Linkedlist)?

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

### Find the number of continuous subsequences in the array which have sum S in the range [B, C]

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 &...
17 views

### Find common min in logarithmic time

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(...
13 views

### Permutation of words that have matched parentheses

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

### Is there a way to pull data automatically from TeamTrack? [on hold]

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

### Preserving a propositional formula

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

### Understanding reductions for NP-completeness

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

### Paying money for internet package [on hold]

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?
24 views

### Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

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

### Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

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

### Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$

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$ ...
21 views

### knapsack problem

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

### Merits/Drawbacks of Different Multithreading Techniques

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

### Counting Inversions with merge-sort

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

### Prove $\forall c \in \mathbb{R}^{+}, \forall B \in \mathbb{N}, \exists n \in \mathbb{N}, (n \geq B) \wedge (\sqrt{2n} > c \ln(n+2))$ [migrated]

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

### Convert arbitrary length String representing a decimal number to another base

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

### Is Alan Turing's proof of the incomputability of halting problem invalid?

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

### Randomized quicksort expected running time analysis

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

### Why use logic gates in this situation? (XOR gates)

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

### Path in an edge-weighted undirected graph

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

### What to do for Combinatorics in CS?

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

### How to generate branch tables from SSA form?

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

### Path in a vertex-weighted undirected graph

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

### Chernoff-like Concentration Bounds on Permutations

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

### Literature on recusively applying predicated transformations to a symbol tree to match some target symbol tree

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

### Proof of correctness of reversal algorithm for array rotation?

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}. ...
26 views

### How is context switching disabled in a process?

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 ?
35 views

### Probability that a random graph will remain planar after adding an edge

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

### Does UDP always deliver packets inorder to the application layer

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

### Is there a way to store/transfer online data that is on RAM memory to ROM when offline? [on hold]

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

### What is the Definition of a counting semaphore

Can someone give me simple definition of a counting semaphore ?
32 views

### Are all terms of type forall a. a operationally bottom?

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

### Shell sort vs quick sort, which is better?

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

### Are there any advantages of using threads in single core system? [on hold]

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 ?
22 views

### What algorithm to use to optimizing C(n, 2) operations?

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

### Big O notation: removing big O from denominator

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

### How to determine R-Tree MBR Nodes?

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