0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 &...
1
vote
0answers
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(...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
-2
votes
0answers
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?
2
votes
2answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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$ ...
-3
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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.
0
votes
0answers
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 ...
-2
votes
1answer
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 ...
5
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
2answers
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....
0
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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}. ...
0
votes
0answers
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 ?
1
vote
2answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
67 views

What is the Definition of a counting semaphore

Can someone give me simple definition of a counting semaphore ?
3
votes
1answer
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 ...
-1
votes
0answers
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 ...
-4
votes
0answers
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 ?
-1
votes
0answers
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 ...
5
votes
2answers
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: \begin{equation} \frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\...
0
votes
0answers
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 ...
1
vote
0answers
25 views

Need help figuring out a planning/assignment problem

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 ...
4
votes
2answers
45 views

Fast sampling from discrete space

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=...
0
votes
1answer
20 views

How to collect all states of a behavior in TLA+?

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 (...
-1
votes
1answer
24 views

OS process management

Assume a process execution interrupted at the middle and CPU started executing a different process.How does the OS handle this situation?
-1
votes
0answers
20 views

Using CNN to learn the non-linear mapping between two images

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 ...
0
votes
0answers
22 views

Problems reading input in C++, skipping lines [on hold]

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 ...
3
votes
1answer
19 views

Algorithm to establish a global ranking given individual rankings

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 ...
0
votes
0answers
11 views

Can self-taught learning generalize to open-set classification?

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 ...
4
votes
1answer
86 views
+50

How can I correct this Hamming code?

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

Changing the representaion of numbers in lisp? [migrated]

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 ...
0
votes
0answers
9 views

Dynamic deleting of edges in complete graph [duplicate]

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

15 30 50 per page