Skip to main content

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
-2 votes
0 answers
45 views

Proof the number of nodes in a full binary tree +1 is equal to the double of the leafs [closed]

This is a class problem from the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 191, I believe I have done it correctly but ...
0 votes
0 answers
35 views

Software language specification: null VS empty objects.

I have noticed that in software language specifications, there is pretty much always a NULL element and I am wondering if it is strictly necessary and how it maps to algebraic structures, given that ...
0 votes
0 answers
53 views

How does $G_n$ relate to $F_n$ here? [duplicate]

Let $F_n$ be the $n$th Fibonacci number, i.e $$F_n=\left\{\begin{array}{cl}F_{n-1}+F_{n-2} & \text { if } n>1 \\ 1 & \text { if } n=1 \\ 0 & \text { if } n=0\end{array}\right.$$ and ...
-1 votes
0 answers
18 views

How to prove the recursively defined set L' is equal to L?

In the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 199,there is an excercise on recursive sets and structural induction ...
5 votes
2 answers
135 views

"Encode" all $n$-permutations with the fewest number of swaps

The goal is to find $m$ swaps $s_1, s_2, \dots, s_m$ such that any $n$-permutation can be encoded as a binary sequence of length $m$, $x_1, x_2, \dots, x_m$, where $x_i$ indicates whether to perform ...
-1 votes
1 answer
91 views

How can I prove the derivative is closed in a set of elements? [closed]

I was doing exercises on recursive data types of the book "Mathematics for Computer Science revised Monday 18th May, 2015, 01:43 "https://people.csail.mit.edu/meyer/mcs.pdf",Problem 6.3,...
0 votes
0 answers
19 views

Number of significant digits when computing percentages on prices

I have two numbers total and partial that are always rounded to two decimals as they are prices in currencies that have cents (...
0 votes
1 answer
963 views

Quickest algorithm to intersect a line and a circular arc , using vectors where possible.

Assuming the line is given by two points $\textbf{a,b}$, and the circular arc by radius $r$ and its exponential coordinate interval $(\theta_0, \theta_1) \subset [0, 2\pi)$. Let $\textbf{y} = \textbf{...
0 votes
1 answer
62 views

How to define the reverse of a string recursively and then prove that : $Reverse(s*t)=Reverse(t)*Reverse(s)$?

I was doing the excercises of section 6.5 of the book Mathematics for Computer Science revised Monday 18th May, 2015, of the MIT opencourseware(https://ocw.mit.edu/courses/6-042j-mathematics-for-...
1 vote
1 answer
999 views

Clock Frequency and Duty Cycle

A clock has a 1ns clock period with rise and fall time as 0.05ns. The clock signal stays at exact Boolean state 1 for 0.35ns and at state 0 for 0.55ns. The memory used in the design takes 2 clock ...
9 votes
5 answers
8k views

What is a fast algorithm for finding the integer square root?

What is a fast algorithm for computing integer square roots on machines that doesn't support floating-point arithmetic? I'm looking for a fast algorithm for computing the integer square root of an ...
1 vote
1 answer
342 views

Is unit norm gradient a necessary and sufficient condition for a signed distance function?

I've seen proof that a signed distance function $f$ satisfies the eikonal equation $$\|\nabla_{\mathbf{x}} f(\mathbf{x})\| = 1, \mathbf{x} \in \Omega$$ where $\Omega$ is an open set with boundary $\...
2 votes
1 answer
43 views

Unclear evaluation of brackets in $\lambda$-Calculus

I have problems with evaluating this $\lambda$-Expression. $$(\lambda x.\lambda y.x(yx))\ (\lambda z.w)$$ The result should be, according to online calculators, $\lambda y.w$. But Iam really confused. ...
2 votes
2 answers
216 views

What does it mean when the transition function of a NFA returns an empty set?

Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
0 votes
1 answer
57 views

Expected time to receive all n numbers at least once [duplicate]

Consider the following problem: every second we receive a random number from the set $ A = \{1, \ldots, n\} $. We stop when we have received all $ n $ numbers at least once. We want to know the ...
0 votes
1 answer
87 views

What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?

Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
2 votes
1 answer
50 views

Taking K elements from an infinite set sum, the expectation of getting a duplicate element exactly the Kth time

First, the probability of selecting $ k $ elements from an $ n $-element set, where the $ k $th selection is the first time a duplicate occurs, is given by: $$ \frac{\binom{n}{k-1} (k-1)!(k-1)}{n^k} $$...
0 votes
1 answer
2k views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that is, ...
2 votes
1 answer
62 views

Is this looser case of the maximal clique(connected subgraph) problem also hard?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. We'll call vectors $(x_1,\dots,x_n), (y_1,\dots,y_n) \in Y$ independent iff $\forall 1 \leq i \leq n, x_i \neq y_i$. There can be at most $m$ ...
-1 votes
2 answers
54 views

Why $d^*(q, \epsilon)$ has definition when $d(q, \varepsilon)$ does not in DFA?

I'm reading an online book about DFA and NFA but it confuses me. Given a DFA say $D=(Q,\Sigma, q_0, \delta, F_Q)$, its transition function is a total function defined on every symbol from a given ...
0 votes
0 answers
29 views

Conditional Probability of Byte Being Smaller Than the Max in a Sequence

I have the following byte sequence. $X, A, B_1, \ldots, B_h$ are discrete i.i.d. random values in $[0,255]$. I want to simplify the probability $$ P(X < \max(A,B_1,\ldots,B_{h-1})\mid\max(B_1,\...
0 votes
0 answers
20 views

Converting generalized nondeterministic finite automata (GNFA) into regular expressions

When converting from a GNFA to a regular expression, we systematically remove states from the GNFA until we are left with just the start and accept state such that the transition arrow from the former ...
3 votes
1 answer
228 views

UPD: Structure of subgroups of $S_{2^n}$ generated by $\langle x \mapsto ax \mod 2^n \rangle$ and linear groups

It's a very well known result by Gauss that $(\mathbb{Z}/2^n \mathbb{Z})^\times = \langle -1 \rangle \times \langle 3 \rangle \cong C_2 \times C_{2^{n-2}}$. Consider a faithful action $\mathrm{mul}: (\...
0 votes
0 answers
35 views

Calculating N evenly spaced points on a ringed torus surface(not randomly)

I have been trying to find a optimised solution for calculating the x, y, z of a point that lives along the surface of the torus and is equally spaced out like other points. The naive approach is to ...
2 votes
2 answers
93 views

ODE book for a computer science researcher (Birkoff/Rota vs Arnold)

I've have been looking for a book on ODEs and have narrowed it down to 2 candidates: Birkoff and Rota's 'ordinary differential equations' or Arnold's 'ordinary differential equations: 3rd edition'. ...
1 vote
2 answers
59 views

XOR sum of array

When you are given an array of even number of elements: [$a_1$ $a_2$ $a_3$ ….. $a_n$] ($n$ is even) Assume the $a_i$ are not all zero Let $S$ = the XOR sum of all these original elements You will ...
1 vote
1 answer
965 views

On the Yale sparse matrix format

I am wondering if someone could provide me with additional information with regard to the so called Yale sparse matrix format, other that what can be already found here: https://en.wikipedia.org/wiki/...
1 vote
3 answers
3k views

Order of growth rate in increasing order

This question is related to maths, so I post here. Actually it's a computer science question and I am facing this type of question while learning Design and Analysis of Algorithms, but we all know ...
0 votes
0 answers
42 views

Definition of carrier map/ task for two processes

In distributed computing, we define a carrier map to be a map between a graph $\mathcal{G}$ and the power set $2^\mathcal{H}$ of a graph $\mathcal{H}$ s.t, for simplices $\sigma$ and $\tau$ of $\...
1 vote
1 answer
75 views

What is the computational complexity of generalized Long Live the Queen?

Consider the following model of computation: The computer's memory consists of $n$ registers denoted $r_1, ..., r_n$, each holding an integer. In the following, an affine combination means an ...
0 votes
0 answers
31 views

Formalities on loop invariant - algorithms

When proving an algorithm using a loop invariant, we need to check these three things. The loop invariant holds before the loop is entered (initialization) If the loop invariant holds before the loop ...
0 votes
1 answer
37 views

Is there a technique for solving magic square-style puzzle using matrices on pen and paper?

The cells (in the puzzle below) must be filled with integers in {1,2,...,12} and they must all be distinct. The numbers on the outside indicate the sum of the cells. For example, the 1st row's cells ...
0 votes
0 answers
11 views

For $n,m \geq 1$, when do exist $p_1,\dots,p_n \in S_m$ so that they coordinate-wise map $X$ to $X'$, where $X,X' \subset \{1,\dots,m\}^n, |X|=|X'|$?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. Suppose $p_i \in S_m, i = 1,\dots,n$. Define $P_{p_1,\dots,p_n}: Y \rightarrow Y$ as follows: $\forall y=(y_1,\dots,y_n) \in Y, P(y) = (p_1(y_1)...
0 votes
0 answers
22 views

Bounding d-regular graph traversal length for every starting node and every traversal

Question: (Past exam question i'm using to revise) Let $G = (V,E)$. A connected d-regular graph. Let $v_1 \in V$. Assume that at each node, the ends of the edges incident with the node are labelled $1,...
1 vote
2 answers
66 views

How many isomorphism classes are there of strings of length $n$ over alphabet $\Sigma$ of size $k$?

Isomorphisms of Strings. $$ s = aa \simeq bb\\ s = ab \simeq ba $$ So the set of strings over a 2-letter alphabet of length 2 have merely 2 isomorphism classes. $$ s = aaa \simeq bbb \\ s = aab \simeq ...
0 votes
0 answers
15 views

The elements of a list of length n that take the greatest number of function calls to be found using binary search

I was wondering if there was any information on determining the indices of the elements that take the greatest number of function calls to be found, if binary search is used to find the element, in a ...
1 vote
1 answer
968 views

Proving L is regular or not using pumping lemma

So I'm trying to prove that the language $L = \{1^n \mid n \text{ is composite}\}$ is either regular or non-regular using the pumping lemma. I wanted to ask if I'm on the right track. So I assume ...
0 votes
1 answer
24 views

Problem understanding proof about deterministic pushdown automaton

So I already posted this in Computer Science Stack Exchange but haven't received any real answers and my exam is tomorrow, so I'll post it here too hoping for some clarification: I'm having problem ...
0 votes
3 answers
318 views

Computable Distance in a Projective Space?

So this is absolutely not my area of expertise. Still, I wondered if someone could point me in the direction of a computational distance measure between points in a projective space? (ie. an algorithm ...
0 votes
1 answer
5k views

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question: Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also the ...
1 vote
1 answer
23 views

General Solutions to Probabilistic Systems

Suppose we have a system like this (the actual numbers and structure don't matter): $$ P(a_1) = 0.28, P(a_2) = 0.36, P(a_3) = 0.41,\\ P(a_1 \cup a_2) = 0.59, P(a_1 \cup a_3) = 0.6, P(a_2 \cup a_3) = 0....
1 vote
0 answers
29 views

Comparing functions with regard to runtime complexity

Just started studying runtime complexity, and I'm starting to compare functions to determine whether one or the other is "faster". I've got five definitions, which can be condensed into ...
0 votes
0 answers
27 views

Asymptotic analysis of $(\log n)^{\log n}$ vs $n^{\log \log n}$

What is the most informative relationship between the functions $$\begin{align*} f(n) &= (\log n) ^ {\log n} \\ g(n) &= n ^ {\log \log n} \end{align*}$$ out of $f = O(g)$, $f = \Omega (g)$, $f ...
1 vote
0 answers
89 views

What is the proof that Term Finding in Calculus of Constructions ($\lambda{C}$) is undecidable?

It is mentioned in a textbook "Type Theory and Formal Proof: An Introduction", but couldn't find the paper or proof anywhere on the internet. To quote the textbook: The question of Term ...
15 votes
3 answers
2k views

A seemingly contradictory function - where's the issue?

I have constructed a function of seemingly contradictory nature. Let $f$ be a function which, given an input $n\in \mathbb{N}$, lexicographically searches through all strings and finds the $n$th pair $...
3 votes
1 answer
88 views

Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?

Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
1 vote
0 answers
57 views

Mathematical and Intuitive understanding of "Optimal Substructure"

Wikipedia formally puts the definition of optimal substructure as below: "A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of &...
2 votes
1 answer
58 views

Is there any quick way to compute/approximate a symmetric, scale-invariant (declining color) gradient around an ellipse?

First the goal is to draw en ellipse with a (grey color) gradient like this: With minimum at the center of the line and symmetrically declining towards the in- and outside. Other than shown in the ...
0 votes
1 answer
3k views

How to prove that regular language is decidable

I understand that i am trying to show that: | D is a DFA that accepts w TM=with input Stimulate D on w: 1) TM accepts if stimulation ends with accept state of the DFA D 2) TM rejects if ...
1 vote
0 answers
28 views

Prove one specific Upper bound of the minimum time of a p-processor schedule

In spring18 mcs.pdf, it has Problem 10.26: We want to schedule n tasks with prerequisite constraints among the tasks defined by a DAG. (a) Explain why any schedule that requires only p processors ...

1
2 3 4 5
112