# All Questions

48,760 questions
Filter by
Sorted by
Tagged with
7 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....
• 101
12 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, ...
23 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 ...
• 217
55 views

• 63
1 vote
30 views

• 161
42 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 ...
369 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
359 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
40 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
35 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
38 views

### Shortest path between two nodes with time-dependent edge weights

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
• 111
25 views

• 41
864 views

### Do analog computers exist?

Given the current state of physics and quantum mechanics is it possible theoretically to build an analog computer that, for example, calculates the addition of two real numbers? Where theoretically if ...
• 304