All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
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....
Yos's user avatar
  • 101
0 votes
0 answers
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, ...
user166586's user avatar
0 votes
1 answer
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 ...
aioobe's user avatar
  • 217
2 votes
2 answers
55 views

Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq ...
HonestSJ's user avatar
0 votes
0 answers
42 views

Is this how I could come up with the time complexity for the Sieve of Eratosthenes?

So here is how I tried to come up with the time complexity for the Sieve of Erast. According to Wikipedia it is $O(n \; \text{log} \;\text{log}\;n)$. I got $O(n \; \text{ln}(\sqrt{n}))$ Here is what I ...
Yuirike's user avatar
  • 29
-3 votes
1 answer
36 views

How to prove p is not NPC?

Given p="Determine whether a given number n is 5 or not". What is the VALID proof that p∉NPC?
wij's user avatar
  • 1
1 vote
1 answer
27 views

How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows: Based on this definition, how can I formally prove that any regular ...
Vegetal605's user avatar
-3 votes
2 answers
90 views

Are my ideas good enough to be hired by programming design groups?

Am I having any chance if I implement a system programming from scratch? I have some ideas. The first is to fix malloc in C. Add a last parameter to all function calls, use LINE and ThreadId and make ...
mostafas's user avatar
2 votes
0 answers
24 views

Complexity class BPP, but with only expected polynomial running time

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output. ZPP, on the other hand, guarantees correct output, but now only ...
Mike Battaglia's user avatar
1 vote
1 answer
24 views

Recurrence Upper Bound Estimation

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$ According to CLRS definition of Master Theorem, ...
Jackson Schuetzle's user avatar
0 votes
1 answer
27 views

Top K Most Frequent Elements and Bucket Sorting Intuition

Link to Problem: https://leetcode.com/problems/top-k-frequent-elements/description/ Bucket Sort Solution: https://leetcode.com/problems/top-k-frequent-elements/solutions/5032156/beats-96-39-of-users-...
penguin365's user avatar
-1 votes
0 answers
12 views

how can i find the average degree of concurrency for the dependency graph

i found 2 solution to the average degree of concurrency if assigned to only one processor the first is that 14 as the code is serial and another 5 what is the right answer
Fathy Ramadan's user avatar
1 vote
1 answer
36 views

Kleene star of any unary language is regular

I want to prove: Let $L \subseteq \Sigma^*$. If $\Sigma=\{a\}$, then $L^*$ is regular. I found this answer: Kleene star of an infinite unary language always yields a regular language. But I do not ...
shinichi's user avatar
0 votes
0 answers
17 views

Dividing Two Integers [closed]

I'm solving the Divide Two Integers problem from leetcode. My solution is the following: ...
Karol Borkowski's user avatar
0 votes
0 answers
15 views

Complexity of checking validity of condensed distance matrix

Let $M$ be a distance matrix of a simple graph. Then a condensed distance matrix $M'$ is defined with the following procedure: ...
rus9384's user avatar
  • 1,664
2 votes
0 answers
23 views

Weaknesses of the alternative RSA-like algorithm

Disclaimer: it is a purely out-of-curiosity question. We discussed this implementation with a friend and could not find any breaches, but I have a gut feeling that there might be some. Consider a ...
Ivan Smirnov's user avatar
2 votes
0 answers
27 views

Approximate Set Intersection datastructure

I'm working on a project involving set-like data structures. For one of the algorithms I am using that does a merge-like operation on two of these structures I can take a very big shortcut if I know ...
MacroPolo's user avatar
0 votes
1 answer
21 views

Discard all ambiguity from given CFG

Here is given CFG : CODE→VDECL CODE | FDECL CODE | ϵ VDECL→vtype id semi | vtype ASSIGN semicolon ASSIGN→id assign RHS RHS→EXPR | lit | char | bool EXPR→EXPR addsub EXPR | EXPR multdiv EXPR EXPR→...
bFur4list's user avatar
  • 103
2 votes
1 answer
84 views

NP-hardness of solving systems of *homogeneous* polynomial equations

It is well-known that deciding if a system of quadratic polynomial equations in several variables admits a solution in a finite field is NP-complete. There is a simple reduction from 3SAT, that works ...
Charles Bouillaguet's user avatar
0 votes
1 answer
13 views

Z vs B-method vs VDM?

What are the differences between these formal methods? Is one objectively better than the others or do they all have pros and cons?
UNRESTR1CTED's user avatar
1 vote
1 answer
43 views

Is there a concept of multidimensional call stacks in computer science?

Had this random thought while running. If I think of a conventional computer program function execution, I think of piece of paper. The program can only run down the page, it can never go backwards. ...
dwjohnston's user avatar
3 votes
1 answer
280 views

Prove that "max independent set is larger than max clique" is NP-Hard

We define B as: $B = \{ <G> | \text{ G is an undirected graph in which} \\ \text{the number of vertices in the largest independent set} \\ \text{is greater than the number of vertices in the ...
shaggy's user avatar
  • 63
1 vote
0 answers
30 views

MSOL for a vertex-cover enlargement problem

Consider the following problem. Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|\le k$, and any subset $V'\...
Lisa E.'s user avatar
  • 369
0 votes
0 answers
24 views

Adding edges to enlarge vertex cover

Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
Lisa E.'s user avatar
  • 369
1 vote
1 answer
38 views

BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
Caroline's user avatar
1 vote
0 answers
41 views

Communication Complexity of "2-Bit"

[For context, I'm trying to work through the derivation of Lemma 2.1 (2-Bit) here, https://users.cs.utah.edu/~jeffp/papers/multiCC-soda12.pdf. ] The '2-Bit' setup is that Alice draws a bit-string of ...
brownrice's user avatar
2 votes
1 answer
58 views

Find hierarchical clustering of documents

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)? My ...
olivarb's user avatar
  • 121
3 votes
1 answer
48 views

Cover a set of points using subintervals of a list of intervals

Given a set of points $\{p_1, p_2, \dots p_n\}$ and a set of intervals $I =\{[a_1, b_1], \dots [a_m, b_m]\}$, you are asked to find a set of subintervals $S = \{[c_1, d_1], \dots [c_m, d_m]\}$ where $[...
SimonNW's user avatar
  • 161
2 votes
1 answer
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 ...
UNRESTR1CTED's user avatar
2 votes
3 answers
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 ...
Lisa E.'s user avatar
  • 369
-1 votes
0 answers
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 ...
user8469759's user avatar
3 votes
1 answer
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....
Lisa E.'s user avatar
  • 369
1 vote
1 answer
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}, ...
pewwwpewww's user avatar
1 vote
0 answers
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 ...
MS Keane's user avatar
0 votes
1 answer
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 ...
Slaycapь's user avatar
1 vote
1 answer
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 ...
Kindness's user avatar
1 vote
1 answer
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 ...
Jxb's user avatar
  • 338
1 vote
1 answer
43 views

Exercise C-1.3 in Algorithm design and applications

There is a exercise in Algorithm design and applications (Goodrich) that I don't understand. It says: What is the amortized running time of the operations in a sequence of n operations $P=p_1p_2 \...
Science Guy's user avatar
3 votes
1 answer
55 views

Maximum distance between two points of a polyhedron

Given a (bounded and feasible) polyhedron, $P=\{x\mid Ax\le b\}$ and a number $\gamma > 0$, decide if there are two points $x, y \in P$ such that $\Vert x - y\Vert_p \ge \gamma$. Is there an $\...
Lisa E.'s user avatar
  • 369
1 vote
1 answer
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 ...
A. Darwin's user avatar
  • 123
3 votes
2 answers
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 ...
defonottyler's user avatar
-2 votes
0 answers
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 ...
Arthur Strong's user avatar
2 votes
2 answers
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 ...
bobismijnnaam's user avatar
0 votes
1 answer
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 ...
Stephen Stone's user avatar
1 vote
1 answer
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 ...
Ferran Gonzalez's user avatar
1 vote
2 answers
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 ...
Sgg8's user avatar
  • 111
-2 votes
0 answers
25 views

How to solve PDA and DPDA construction for given languages? [closed]

I'm working on a theoretical computer science exercise and need some help with solving it. Here's the task: Task: Let $w^R$ be the reverse of a word $w$ (e.g., $w = 0101$, $w^R = 1010$), $L1 = \{ ww^...
Harold 's user avatar
4 votes
0 answers
48 views

Deterministic solution of "nuts and bolts" problem

How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
Gh0st's user avatar
  • 41
-2 votes
2 answers
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 ...
JobHunter69's user avatar
0 votes
1 answer
117 views

Analog computers more powerful than turing machines?

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing ...
JobHunter69's user avatar

15 30 50 per page
1
2 3 4 5
976