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

5,567 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 (...
963 views

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. ...
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, ...
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 ...
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 ...
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}$$...
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, ...
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$ ...
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 ...
29 views

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
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 ...
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 ...
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 ...
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
23 views

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