Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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).

0
votes
2answers
33 views

The definition of the empty string.

Here I'm having some confusion on what exactly is the empty string $\epsilon$. I'm going to list some prerequisite definitions I have surrounding the string, so please correct them as necessary. I ...
0
votes
0answers
15 views

How do applications of finite automata physically transition?

Just began studying automata. I've already seen several examples of the applications of finite automata: pattern matching, automatic doors, etc. And so far, I understand the logical connection between ...
0
votes
2answers
22 views

Difference between Kleene Closure in Group and in Alphabet

Having a group $A = \{a, b\}$ and an alphabet $B = \{a, b\}$ Is there any difference between $A^*$ and $B^*$? I think there is no difference, but I would like to be sure. Thanks in advance.
3
votes
0answers
47 views

Why are integrals and summations useful in computer science and what do these function mean?

I am reading my way through an introductory MIT computer science book called Structure and Interpretation of Computer Programming, and while I understand the programming and logic behind the book, ...
0
votes
0answers
11 views

How to get only max value from variable in nested for loop [on hold]

i need help with this code? Result is : jon 15 bob 38 steve 180 bob 14 steve 240 steve 180 luk 203 but i espected like this : jon 15 bob 38 steve 240 luk 203 max value from loop of user ...
4
votes
2answers
73 views

Multiplying two numbers using only the “left shift” operator

At Geeks for Geeks, I came across a question "Add two numbers without using arithmetic operators", which basically states that you can multiply two numbers using the left shift operator. I am confused ...
-2
votes
1answer
26 views

Finding the most restrictive Big O, O(n^k), where k is some integer for an function [on hold]

How can I find the most restrictive Big O, O(n^k), for a function? for k is an integer k >= 0 For example, f(n) = $\sqrt{log(n)*n}$ Of course, I could say it's O(n^99999), but that's not very tight....
-3
votes
1answer
48 views

How many polynomials are O(x^4), if each of the coefficients is either 0 or 1? Stuck on this question.

A polynomial of degree $n$ can be written in the form $a_n x^n+a_{n-1} x^{n-1}+⋯+a_2 x^2+a_1 x+a_0$,where $a_0,\dots,a_n$ are constants (i.e. the coefficients) and $x$ is the variable. How many ...
0
votes
0answers
7 views

HELP with SAS DATA programs [on hold]

I need help writing a SAS program that does the following in order. Write a SAS program to do the following in order: Create a SAS library, mylib that connects to the folder U:\STA575\Exam1. You ...
0
votes
3answers
39 views

Natural logarithm approximation of numbers greater than 2 for computers

I am interested in approximating the natural logarithm for implementation in an embedded system. I am aware of the Maclaurin series, but it has the issue of only covering numbers in the range (0; 2). ...
0
votes
0answers
7 views

Convex hull properties and hyperplanes

Let P be a closed point set (not necessarily finite) in d-dimensional Euclidean space (Ed). Let conv P denote the convex hull of P. (i) Given a point q ∈ Ed \ closure conv P, describe how to ...
2
votes
1answer
97 views

Gcd is a Regular Language

Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]
0
votes
1answer
30 views

Does the empty string share properties of both zero and $\emptyset$?

I'm confused by the use of the empty string as the author uses it below. This is a excerpt from Introduction to the Theory of Computation by Sipser. Regarding the emptystring line, is this how ...
2
votes
1answer
23 views

How are clock cycles and clock rate inverses?

So I'm trying to understand this simple math formula, but I can't wrap my ahead about what it means to be an "inverse". So for example, a CPU execution time for a program is given by the formula: $$...
1
vote
1answer
37 views

Using the substitution method on $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$ [duplicate]

My task at hand is to find a tight asymptotic upper bound for the recurrence $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$. My initial idea has been to substitute $m=\lg n$ and define a new recurrence $s(m)=p(2^...
0
votes
0answers
13 views

Connectionism and AGI

Marvin Minsky and Papert prove that the XOR function($\newcommand{\xor}{\oplus} x \oplus y$) cannot be implemented by a single layer perceptron and ended connectionism research for some time. My ...
1
vote
1answer
40 views

Is there a probabilistic Turing machine whose halting probability is non-measurable?

I was wondering if there a probabilistic turing machine whose halting probability is non-measurable? By that, I mean that the probability measure applied to the event "the machine halts" is undefined.
-2
votes
1answer
78 views

Is there a distinction between a “specific” (“nominated”) real number and an “anonymous” real number?

The Axiom of Choice: If $a$ is a class of non-empty sets $x,$ there exists a function $f$ such that $f\left(x\right)\in{x}$ for all $x\in{a}.$ https://mitpress.mit.edu/contributors/h-behnke The ...
1
vote
2answers
43 views

How many essentially different strings are there of length $\leq n$ and over an alphabet of size $|\Sigma| = m$?

For example, $aaaaaabb \simeq ccccccdd$ essentially, because a smallest grammar algorithm would perform the exact same steps to reduce one as the other. So how can I phrase this in terms of formal ...
2
votes
1answer
31 views

Reduction from 3-SAT to MAX 2SAT

For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an ...
1
vote
1answer
66 views

Is “type theory” the only way to get a computer to “do math” on its own? [closed]

It seems like one of the direct applications of type theory definitions & algorithms is to implement them on a computer and use it for proof assistants, etc. But why couldn't you just implement ...
0
votes
0answers
19 views

Notation for Markov chain

I am reading this paper. However, I don't understand the Markov chain notations(my go to book (Mathematical Notation: A Guide for Engineers and Scientists) sadly doesn't contain anything about Markov ...
0
votes
0answers
21 views

Minimum path distance from a source

Suppose I have a path-connected subset $I$ of $\mathbb{R}^n$ (not convex, but can be contained in a product of finite-measure closed intervals), and I define a "source point" $a \in \mathbb{R}^n$. ...
0
votes
0answers
40 views

What does the first “non-free” variable mean here when substituting in simple type theory?

See this screenshot of the book "Basic Simple Type Theory". The infinite sequence they refer to is just a way to formalize the concept of having enough variables to work with no matter what. In my ...
0
votes
2answers
86 views

What is meant by “free choice” in mathematics?

The following quoted text was written before 1963, so the authors didn't have the benefit of decades of automated computing machines to inform their statements. The essential feature of an ...
1
vote
2answers
15 views

Theory of Computation (Regular/Non-Regular proof)

Suppose that L0, L1, L2 are languages over the same alphabet and that L0 ⊆ L1 ⊆ L2. Is it true that if L0 and L2 are regular, then L1 must be regular as well? ...
0
votes
1answer
81 views

How to find all the equivalence classes of a given language without using the Table-Filling-Algorithm.

I'm trying to solve an exercise problem for my formal languages class, that's to do with the Myhill-Nerode Theorem for regular languages. I'm given the following information and asked to find out all ...
1
vote
1answer
24 views

Why was letter T chosen in T-joins in Graph Theory

In one of my master's courses, Advanced Graph Theory, we studied T-joins and their applications. I asked my teacher why was letter T chosen in T-joins' name and he didn't know. I guess there's ...
0
votes
0answers
14 views

Maximum Expected Fishing Day (Recurrence Relation)

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. ...
0
votes
1answer
20 views

Discrete mathematics - tree problem

Prove that a connected graph G = ( V, E ) is a tree, if | V | = 6 and |{ v ∈ V | deg( v ) = 1 }| = 4 and |{ v ∈ V | deg( v ) = 3 }| = 2
0
votes
1answer
33 views

Give a state diagram for an NFA whose language L = …

L = {w ∈ {0,1,2} *: w is a ternary representation of an integer that is a multiple of 3 but not a multiple of 9} I've written a DFA accepting multiples of 3, but I'm not sure how I should proceed. ...
0
votes
1answer
23 views

A uses 100nlog(n) operations while B uses n^(1.5) operations. Determine the value n0 such that A is better than B for n ≥ n0 assuming log base 2

I've tried a few different approaches but I'm not getting anywhere with this. 100log(n) = n^(0.5) ==> log(n) = n/100 ==> n = 2^(n/100) Stuck at this dead end. 100log(n) = n^(0.5) ==> log(n^(100)) =...
0
votes
1answer
24 views

Breaking a set into continuous subsets such that number of 1's are greater than number of 0's

You are given a list of $0$’s and $1$’s: $B[1], B[2], . . . , B[N]$. A sublist of this list is any contiguous segment of elements—i.e., $A[i], A[i + 1], . . . , A[j]$, for some $i$ and $j$. A ...
0
votes
1answer
12 views

Specify a decisive Turing machine that calculates the following function $f$.

Specify a decisive Turing machine that calculates the following function $f$: $$\small f:\{a,b\}^*\to\{a,b\}^*\textrm{ with } f(w)= \begin{cases} (bba)^{3\cdot\#_b(w)}& \text{if } \#_a(w) \text{ ...
1
vote
1answer
41 views

Show $\frac{n+1}{2n^2+5} \in \Theta (\frac{1}{n})$ using definition

Show $\frac{n+1}{2n^2+5} \in \Theta (\frac{1}{n})$ using definition First showing the upper bound $\frac{n+1}{2n^2+5} \in O (\frac{1}{n})$ $\frac{n+1}{2n^2+5} \leq \frac{2n}{2n^2} = \frac{1}{n}$ ...
0
votes
1answer
52 views

Underflow while evaluating softmax, despite using exp-normalize

I have a very simple linear classifier that uses softmax (with exp-normalize trick) for the output: ...
1
vote
3answers
52 views

Partition of set with N integers such that each subset has length less K.

You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3, . . . , N}$. An ordered tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and it is different ...
0
votes
0answers
12 views

Gröbner basis vs Brute Force Attacks on GF(2) polynomial system of equations?

I'm studying cryptography and I have a question regarding the complexity analysis of algorithms. In AES cryptography, the Gröbner basis algorithm for solving systems of polynomial equations over the ...
0
votes
0answers
29 views

Formal Proof - premises and conclusions

So I'm learning about formal proof and understand the beginning steps. However, after it gives an argument and conclusion. I then don' t understand how to do the actual formal proofing. For example: ...
2
votes
1answer
92 views

Number of occurrences of a generic recurring event between two dates

Intro Cron is a very common tool in computer science, which allows to schedule an event given a generic pattern written in a file called crontab. I'm researching on an algorithm to calculate the ...
1
vote
1answer
53 views

predecessor and multiplication prove

I have trouble, when attempting to : 1- prove mult defines the multiplication function. 2- Prove pred defines the predecessor function. 1- for mult: Base Case: mult 0x= 0 Inductive case: := $(\...
5
votes
1answer
39 views

Example of graph with two different MSPs via Prim's Algorithm?

I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible. We ...
2
votes
1answer
52 views

Best-known Boolean Circuits for Clique?

In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-monotone circuits that are smaller than monotone circuits for Clique. I’m looking for a reference ...
1
vote
2answers
35 views

Proving $3n^2 - 4n \in \Omega(n^2)$

Proving $3n^2 - 4n \in \Omega(n^2)$ Attempt: $3n^2 - 4n \geq cn^2$ $n(3n-4) \geq cn^2$ $(3n-4) \geq cn$ $3n - 4 - cn \geq 0$ $n(3-c) \geq 4$ $n \geq \frac{4}{3-c}$ would do I choose for $n_0$ ...
-1
votes
1answer
43 views

Regular Grammar

Devise a regular grammar in normal form that generates the language L. Let L be the language consisting of all binary numbers divisible by 4. I know the different aspects needed to be generated: ...
0
votes
0answers
45 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this CS-SE answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we ...
3
votes
3answers
100 views

How can I break RSA if I know the private key?

Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$. So I know $d\cdot e = 1(mod (p-1)(q-1))$ for the primes $p\neq q$ that generate $n$ by $p\cdot q=n$ but from ...
1
vote
2answers
38 views

Program or computing system [closed]

What programs do you suggest to me such that when introducing a set of numbers, it will answer possible functions that generate them? Different wolfram, neither OEIS. For example, if I input 2, 3, ...
0
votes
1answer
36 views

Calculating Running time from Time Complexity

I have read about big $O$ notation for time complexity and for counting functions like that for prime numbers. Recently on StackOverflow I read: The problem with defining how long an algorithm ...
0
votes
0answers
8 views

What is h5-median index?

I know h5-index shows that n articles being cited at least n times. I have searched and found no references citing h5-median.