All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
einpoklum's user avatar
  • 975
0 votes
0 answers
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.
William's user avatar
0 votes
0 answers
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: ...
chakravyuh's user avatar
2 votes
1 answer
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 ...
12412316's user avatar
  • 153
1 vote
1 answer
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 ...
Steven Thomas Hatton's user avatar
-2 votes
0 answers
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....
Yos's user avatar
  • 97
1 vote
1 answer
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, ...
user166586's user avatar
1 vote
1 answer
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 ...
aioobe's user avatar
  • 229
2 votes
1 answer
62 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
44 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
1 vote
1 answer
31 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
-4 votes
2 answers
98 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
27 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
25 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
-1 votes
1 answer
29 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
37 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
2 votes
0 answers
23 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,684
2 votes
1 answer
40 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
28 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
93 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
45 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
287 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
31 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
25 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
39 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
59 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
51 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
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 ...
UNRESTR1CTED's user avatar
2 votes
3 answers
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 ...
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
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....
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
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 ...
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
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 ...
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
40 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

15 30 50 per page
1
2 3 4 5
976