# All Questions

48,764 questions
Filter by
Sorted by
Tagged with
2 views

### Maximum number of sets in algebra induced by convex $k$-vertex polygons

I have a set $\mathcal{P}$ of $n$ convex $k$-gons (convex $k$-vertex polygons) on the (Euclidean) plane. These define a partition of the plane, or rather the plane sans the pointer on the contour of ...
• 975
3 views

### I am trying to construct an npda for L = {w ∈ {a,b}*| na(w) <= 3*nb(w)}. This means that for every b there can be at most 3 a's

So far I understood that for each b i should pop 1 or 2 or 3 a's. But I'm not sure how to translate that into transitions and diagram.. I need help.
5 views

### Benjamin Pierce Types and Programming Languages 6.1.5 Clarification

I'm currently following Pierce's Types and Programming Languages, and I find myself stuck at exercise 6.1.5 (the implementations of removenames? and restorenames?). The rules are as follows: ...
49 views

### Is there a fully combinatorial version of MLTT without lambda abstraction?

I have been learning MLTT and working on implementing its type checker. Currently, I am at the stage of implementing its termination checker. I find it somewhat dissatisfying that I need to implement ...
• 153
1 vote
26 views

### Desktop computing: who needs multi-threading, multi-processing; and how much?

I am currently running the KDE on OpenSuSE in a VirtualBox hosted by Windows 11 running on a processor with 14 cores. I gave Linux 4 CPUs to play with. So, I am aware of the need for some amount of ...
23 views

### The definition of "||" for function $H(M||w_1)$

I confused about the notation of "||" in function. My major is mathematics, but now I read a paper in informatics. In the paper, I looked at the notation $H(M||w_1)$ where $H$ is a function....
• 97
1 vote
40 views

### Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
1 vote
37 views

### Find the transitive closure but with a twist

Situation I have a set of set of elements V, and relations over V: a R b: "a is related to b" (reflexive and symmetrical) a N b: "a is not related to b" (anti-reflexive and ...
• 229
62 views

• 63
1 vote
31 views

• 161
43 views

### Is there a formal methodology for determining time complexity of an implementation of an algorithm?

Basically what the title says. take for example a simple function: def swap(a,b) temp = a a = b b = temp This one is pretty easy to solve intuitively. if we ...
371 views

### Applicability of approximation algorithms vs meta-heuristics in practice

How useful are approximation algorithms over say, metaheuristics or even problem-specific heuristics in practice? Let's say a certain NP-hard minimization problem (take the travelling salesman problem ...
• 369
39 views

### How to formulate Leetcode 1296 problem as optimization problem

I am reviewing how to design greedy algorithms and specifically I have the following problem that it is suggested to be solved using a greedy approach: Given an array of integers nums and a positive ...
• 711
361 views

### Easy/hard NP-hard problems on perfect graphs

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph....
• 369
1 vote
30 views

### Rough sketch for an Algorithm to show that a context free grammar G generates only words that are solely made up of b's

The title is a bit long but bare with my english skills. As the title says I have a the task to give a rough sketch for an algorhitm that checks whether a give grammar G, with the alphabet {a,b,c}, ...
1 vote
29 views

### Why does ISA includes instruction for logical operation?

I'm a junior student in Electronic Engineering. Recently, I learned about Gödel's incompleteness theorem. One of the concepts related to this theorem is Gödel numbering, which shows that every logical ...
• 11
42 views

### Time complexity of delete and insert operations in a hash table

Let's take a hash table where the collision problem is solved using a linked list. As we know, in the worst case, due to collisions, searching for an element in the hash table takes O(n). But why does ...
• 11
1 vote
57 views

### If Halting is not recursive, then why is it that not every set of the form $\{M: \text{M is a Turing machine that does XXX}\}$ is not recursive?

Suppose I wish to find out whether $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive, where $XXX$ can be anything about the Turing machine. I have a bad proof that proves that all such ...
• 13
1 vote
37 views

### Applications of a SAT Solver Oracle for Determining the Uniqueness of Solutions

I am exploring two kinds of model $𝑝_{𝑚,𝑛,k}$ and $S_{m,n,k}$ within the realm of satisfiability problems (SAT). Formal construction of $𝑝_{𝑚,𝑛,k}$ To construct the $𝑝_{𝑚,𝑛,k}$ model in ...
• 338
1 vote
43 views

• 369
1 vote
25 views

### Is there a lower bound on space complexity of non-in-place sorting?

There is a well known result stating that any comparison-based sorting algorithm has a time complexity of at least O(n log n). Selection sort and merge sort are two common examples, with time ...
• 123
70 views

### Decidability of {M | M accepts some x in less than |x| steps}

Is this language decidable? {M | M accepts some x in less than |x| steps} It feels like it should be undecidable but I can't think of a good proof that isn't similar to that of Rice's theorem (which I ...
34 views

### Subset sum problem but for XOR

I'm looking for hints. I have a set of integers and I need to pick 3 integers x,y,z, which satisfy $x \oplus y \oplus z = some\_constant$. Is there a known name for this problems? Is there something ...
42 views

### Termination of standard encoding of CFG as PDA for words not in the language

The construction of a PDA from a CFG on wikipedia (1) is like a nice exercise for implementing a minimal-and-slow-but-functional parsing algorithm. I have a question about termination of the PDA that ...
47 views

### Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $G = (V, E)$ where a vertex $v \in V$ is designated as the center if it is connected to every other vertex $u \in V$, such that both $uv$ and $vu$ are present in $E$. A ...
1 vote
41 views

### Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a ...
1 vote