Questions tagged [computer-science]

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For questions from scientific computing, use (computational-mathematics).

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 views

What is the cardinality of the set of all binary trees defined over the natural numbers?

I've been wondering what the cardinality of all binary trees would be? Let me define binary trees to be clear. I am using an inductive definition : The set $B(\mathbb{N})$ of binary trees over the ...
user avatar
2 votes
0 answers
45 views

Doubt in Paper on Algebraic topology and Concurrency

I am trying to read a paper on Algebraic Topology and Concurrency (doi: 10.1016/j.tcs.2006.03.022), which claims to make use of Dijkstra's notation in talking about concurrency. Specifically, I am ...
user avatar
0 votes
0 answers
14 views

How can I create an Arc path from 3 point (p1-->p2-->p3) in 3D space?

I want to create an Arc path over 3 points in 3D space. I decided to draw a circle over them and then extract sector from p1 to p3 that passes through P2. I use this code but it did not extract sector ...
user avatar
  • 1
0 votes
1 answer
40 views

Halting problem reduction, what am i doing wrong

I have the following problem. Prove that $L_1=\{\langle M\rangle| \exists w \in \Sigma^*: M(w)\downarrow\}$ is undecidable (where $M(w) \downarrow$ means M halts on input w). I have come up with this ...
user avatar
4 votes
1 answer
95 views

Good Algorithm to Compute all Subgroups of a Finite Group.

Let's suppose we have a group $G$ of finite order $n$. We want to algorithmically compute all subgroups, and there are some ways to do that. First one: Compute all subsets. Verify for each of them if ...
user avatar
0 votes
0 answers
59 views

Struggling with how to solve Proof by Induction [closed]

If we formally define the length function $f(w)$ of a string $w=w_1w_2\cdots w_n$ (where $n\in \mathbb{N}$ and $\forall i=1,\ldots ,n$, $w_i\in \Sigma$) as if $w=\varepsilon$, then $f(w)=0$. if $w=au$...
user avatar
3 votes
1 answer
43 views

A confusion on $\beta\eta$-reduction

Recently I've started exploring lambda calculus, and currently I'm tackling the next exercise: Prove that if $M =_{\beta\eta} N$, then $FV(M) = FV(N)$, Where $FV(P)$ stands for free variables in the ...
user avatar
0 votes
0 answers
22 views

Difficulty understanding a 1-tape TM program which solves and includes time analysis of the program [closed]

I need to sketch a 1-tape TM program which solves and also includes a time analysis of the program, e.g. 𝑂(𝑛), 𝑂(𝑛𝑙og 𝑛), 𝑂(𝑛3), etc.; 𝐿 = {𝑒#𝑣: 𝑒, 𝑣 ∈ {0,1}βˆ— and 𝑒 is a substring of 𝑣}
user avatar
  • 1
1 vote
2 answers
43 views

The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

I saw this pseudocode from the book Introduction to algorithm (Chapter 31 page 957) on how to implement Modular Exponentiation. ...
user avatar
  • 315
3 votes
2 answers
251 views

Why do greedy coloring algorithms mess up?

It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
user avatar
0 votes
2 answers
46 views

Standard notation for algorithm (instead of function)?

I am writing a math paper and defining various algorithms. A function takes at least one input, and (may) output a result. The notation is $$ \begin{align} f :& \mathbb{R} \to \mathbb{R}\\ &(x)...
user avatar
  • 1,983
0 votes
0 answers
68 views

How can I prove that L = {w ∈ {a, b, c, d} βˆ— | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
user avatar
0 votes
0 answers
23 views

Packing & placing rectangles inside a (not-rectilinear) polygon

Intro I have a polygon (not rectilinear) of a fixed size which would act as the container for some number of rectangles. The rectangles are: the same size (height and width) and, they can be rotated ...
user avatar
0 votes
0 answers
21 views

What does the β‡’ mean in Context Free Grammer? Also, how do I derive/get the L(CFG) from a CFG?

I'm a bit confused. Does the β‡’ simply denote you going through the CFG step by step ? To use a pretty basic-ish example: sentence β‡’ subject | predicate subject β‡’ article | noun predicate β‡’ verb | ...
user avatar
  • 11
0 votes
1 answer
28 views

Functions in "Introduction to the Theory of Computation 3rd Edition by Sipser"

Consider this text from page 7 of the book in the title. "In the case of the function abs, if we are working with integers, the domain and the range are Z, so we write abs : Zβˆ’β†’Z. In the case of ...
user avatar
0 votes
1 answer
36 views

Are DFS trees unique?

Suppose you have no priority on the way you decide which vertices to explore in your DFS algorithm (so that any neighbor is equally likely to be visited in every iteration). Then, is it true that the ...
user avatar
0 votes
1 answer
31 views

Binary variable notation

Suppose we have a memory element, i.e., a Flip Flop ($FF$). A $FF$ can have a current value of binary $0$ or $1$, i.e., $FF \in \{0, 1\}$. Is there any formal way to represent three types of $FF$s: if ...
user avatar
  • 1
0 votes
1 answer
28 views

Proof that Christofides Algorithm is a 3/2-approximation for the TSP

I have quoted a section of the proof for the above statement, from Williamson and Shmoys. Can someone explain the section in italics? "We want to show that the edges in the Eulerian Graph ...
user avatar
1 vote
0 answers
44 views

Proving that these two regular languages are equal

Consider the regular expressions $r_1 = (1+01)^* (0 + \epsilon)$ and $r_2 = (1^* 011^*)^*(0+\epsilon) + 1^* (0+\epsilon)$. I want to show that these the regular expressions generate the same language, ...
user avatar
  • 503
0 votes
1 answer
206 views

Prove that there's no decidable language that separates two other languages.

I was reviewing for an exam and I found this question: Let A and B be two disjoint languages (that is, A ∩ B = βˆ…). Say that a language C separates A and B iff A βŠ† C and B βŠ† (not C) . Define two ...
user avatar
0 votes
0 answers
25 views

Christofides Algorithm for the TSP: A "polynomial time approximation algorithm"?

I'm currently studying the travelling salesman problem and Christofides algorithm. I think I understand that TSP is an NP-hard problem, and so the complexity of calculating a solution grows ...
user avatar
0 votes
0 answers
19 views

Finding a bearing angle from a triangle.

I am a computer science students and I have encountered a task in my learning resource which requires some level of math I couldn't understand. So I have a triangle and all of the known variables are: ...
user avatar
  • 21
1 vote
1 answer
46 views

Proof (More rigorous) for LeetCode: 11. Container With Most Water problem

I came across this problem yesterday and I was struggling understanding the solution. I'll give my version for the proof of correctness of the algorithm (leetcode lists such a problem as a greedy ...
user avatar
  • 5,008
0 votes
0 answers
20 views

Probability an abstract lakes of size $6\times 4$ units in size will become unpassable due to the positions of 5 random holes

There is a rectangular lake that people need to cross to get from village $A$ to village $B$. This is a rather abstract lake with size $6\times 4$. Every winter it freezes over and will always have $5$...
user avatar
  • 9
4 votes
1 answer
160 views

Why doesn’t $T(n) = 2T(\frac{n}{2}) + O(n^2)$ solve to $T(n) = \Theta(n^2)$?

I am told that the following statement is not true: $T(n)=2 T (\frac{n}{2})+ O(n^2)$ then $T(n)=\Theta (n^2)$ My challenge is we can solve it by Master Theorem and reach to $T(n)=\Theta (n^2)$. What ...
user avatar
0 votes
1 answer
82 views

time complexity condition among merge-sort and bubble-sort?

I ran into a strange note as follows: we consider bubble sort time complexity as: $c_1n^2$ and merge sort time complexity as: $...
user avatar
  • 1
0 votes
0 answers
21 views

Having trouble understanding the notation for matrices with seemingly incompatible dimensions in a paper; dimensions for matrix math?

Looking at equation 4 in this paper. $$ H_{aj}^{k+1} = H_{aj}^{k} \frac{\sum_{i=1}^{n}W_{ia}^{k}V_{ij}/(W^{k}H^{k})_{ij}}{\sum_{i=1}^{n}W_{ia}^{k}} $$ For more context, this is a non-negative matrix ...
user avatar
  • 1
0 votes
0 answers
89 views

How easy is it to break this encryption system a buddy of mine and I just discovered?

This is gonna take a little bit of background to explain, so here goes: In base $11$, we have $11$ numerals to form numbers: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$, and since there is no single symbol ...
user avatar
0 votes
2 answers
63 views

How to prove that 2SAT $\in$ P

I want to understand the proof in the following link for 2SAT $\in$ P... What for the need of the last corollary? Wouldn't be enought to just prove the case for the graph with the help of the path ...
user avatar
0 votes
1 answer
45 views

Are complexity classes sets?

The definition of a complexity class reads in various different sources roughly as "a collection/set/... of decision problems". My question is: Is every complexity class a set (in the sense ...
user avatar
0 votes
2 answers
29 views

Proving NP Completeness of "the project manager's problem"

Suppose we have a list of basic/'atomic' tasks $\{p_1, ..., p_n\}$ and each task has an associated cost $c_i$ for all $i \leq n$. Morover, we have a list of projects $P_1,..., P_m$ which are ...
user avatar
2 votes
2 answers
102 views

Which grows faster $n!$ or $n^{\sqrt{n}}$?

From graph it can be easily seen that $n!$ grows faster that $n^{\sqrt{n}}$. Also wolfram alpha says that $\lim _{n\to \infty }\left(\frac{n^{\sqrt{n}}}{n!}\right)=0$. I'd appreciate if anyone could ...
user avatar
1 vote
1 answer
48 views

Use of Parentheses in Lambda Calculus when Ξ» is Involved

The question about use of parentheses in lambda calculus here covers the basic idea of how parentheses are formatted in lambda calculus; however, it does not cover scenarios where $\ \lambda $ is ...
user avatar
1 vote
1 answer
87 views

Understanding the Different Properties of Lambda Calculus [closed]

So I am currently learning about lambda calculus in my computer science class, and really having trouble understanding the various properties and operations thereof. There is a great post here ...
user avatar
1 vote
2 answers
52 views

Failure of context-free pumping lemma of $a^nb^n$

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try: Using pumping length $p = 3$ $n = p$, thus we have $aaabbb$ $u =aa$ and $y = bb$ $v = a$, $w = b$ and $x=Ξ»$, then $|...
user avatar
-1 votes
1 answer
53 views

Is it possible (in principle and in meaningful way) to describe any subset of n-dimensional real Euclidean space?

Let us start with some background and motivation. My main question is very simple and it is available few paragraphs further and it is written in bold. My problem is based from the emerging theory of ...
user avatar
  • 1,181
0 votes
0 answers
40 views

Prove $O(f(n))=O(g(n))$ ⟺ $g(n) ∈ O(f(n))$ and $f(n) ∈ O(g(n))$

I want to prove $O(f(n)) = O(g(n))$ ⟺ $g(n) ∈ O(f(n))$ and $f(n) ∈ O(g(n))$ by using mathematics. So, we have 𝑂(𝑓(𝑛)) = 𝑂(𝑔(𝑛)) β‡’ βˆƒπ‘“(𝑛) ∈ 𝑂(𝑔(𝑛)) , βˆƒπ‘“(𝑛) ∈ 𝑂(𝑓(𝑛)) , βˆƒπ‘”(𝑛) ∈ 𝑂(𝑔(𝑛)...
user avatar
  • 1
0 votes
0 answers
33 views

How do i prove that HALT TM is undecidable with Diagonalization?

I am currently struggling with Theory of Computation Diagonalization topic, we are supposed to prepare for the test and one of the exercises I found is to prove that HALT TM is undecidable via ...
user avatar
1 vote
0 answers
46 views

Showing $a_0 + a_1 n + \ldots + a_{k-1} n^{k-1} + a_k n^k = \Theta(n^k)$ when $a_k > 0$

As exercise I am trying to show $$ f(n) = a_0 + a_1 n + \ldots + a_{k-1} n^{k-1} + a_k n^k = \Theta(n^k) $$ when $a_k > 0$. My proof is based on the idea of showing $f(n) = O(n^k)$ and $f(n) = \...
user avatar
  • 5,008
0 votes
0 answers
50 views

The gap size of floating point

In Trefethen Bau Numerical Algebra, floating point set F is defined by $\textbf{F} = \left\{\pm(m/\beta^{t})\beta ^{e}| 1 \leq m \leq \beta^{t}, e \in \mathbb{Z} \right\}$ Equivalently, by making $m$ ...
user avatar
  • 11
3 votes
1 answer
58 views

Is soft-O notation transitive?

We write $f(n) = Γ•(g(n))$ if $f(n) = O(g(n)\log^k(g(n))$ for some natural $k$. (we call $Γ•$ "soft-O") My question is: If $f(n) = Γ•(g(n)\log^a(g(n)))$ for some natural $a$, is then $f(n) = Γ•(...
user avatar
3 votes
1 answer
57 views

How do I multiply using this "Addiator"-style calculator?

I've got an old "Addiator"-style calculator (pictured below), but not the instruction manual. I know how to use it to add (place the stylus next to a digit and pull down, pushing up and ...
user avatar
  • 730
1 vote
1 answer
34 views

How to solve a max CSP with a set of linear constraints?

Suppose there is a set of $n$ linear constraints $\{a_i^Tx+b_i\le 0\}_{i=1}^n$ with $a_i\in\mathbb{R}^d$, $b_i\in\mathbb{R}$, $x\in\mathbb{R}^d$. How can I find $x^*$ that maximizes $\vert \{i\in [n]\...
user avatar
  • 49
-3 votes
1 answer
21 views

Two-tape deterministic Turing machine input block [closed]

I was working through a textbook and got stuck on a question. The Main tape contains a non-empty block of as and bs (representing a word w) "In the case where the input block on the Main tape ...
user avatar
0 votes
0 answers
11 views

Is the Time complexity of MPSS exponential?

I am trying to analyse the running time of the Minimum Positive Subsequence Sum algorithm mentioned here (https://home.csulb.edu/~tebert/teaching/spring15/328/lab/mpss/mpss.pdf) . Here’s what I have ...
user avatar
  • 97
1 vote
1 answer
32 views

$1-x=e^{-x+O(x^{2})}$ for $0\leq x\leq 1$?

I'm struggling to understand a computer science article which uses the approximation, $1-x=e^{-x+O(x^{2})}$. I don't understand where they get this approximation from. To see what they might have done,...
user avatar
0 votes
1 answer
41 views

Provide a grammar to generate strings that are only made of 1’s, where A={0,1}

My solution so far is as follow: S -> 1S | 1 Is it necessary to include lambda in this grammar? Edit: To further elaborate, my logic is that since lambda is not 1 it does not belong in the grammar ...
user avatar
2 votes
0 answers
86 views

What does the notation $2^{-\Omega(n)}$ mean in probability?

When I read papers in theoretical computer science, I see the notation $probability<2^{-\Omega(n)}$ to denote the probability. My queestion is What Does $\Omega$ mean? Is it the same as in ...
user avatar
  • 69
0 votes
1 answer
23 views

In ZFS RAID 6 implementation, why certain shifts are βŠ•, but not the others?

ZFS is a computer filesystem, which has an implementation of the RAID 6. I understand the simplified example of the RAID 6 implementation in Wikipedia, which each data chunk D is bit-shifted by a ...
user avatar
  • 121
0 votes
0 answers
6 views

Maximum safe value for bounded unsigned integer multiplication factors

When performing unsigned integer multiplication, I want to find out the largest numbers that can be multiplied and still safely fit $N$ bits. Intuitively, I find that $x*y$ reaches some sort of local ...
user avatar

1
2 3 4 5
…
103