# Tagged Questions

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

83 views

### Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
50 views

### b tree least upper bound

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The ...
16 views

### Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
45 views

### In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
20 views

### Rightmost derivation word aaaccb

I have got these context free grammar: $S \implies aSA | a \\A \implies Ab|c$ The goal is find rightmost derivation of word $aaaccb$ a draw derivate tree, which corresponding with this derivation. ...
21 views

37 views

### Course or book - Math Foundations in CS

I want to improve my math skills, now I'm trying to find good route for this purpose. I'm using Khan Academy, and recently found "CS103 - Mathematical Foundations of Computing" course which looks good ...
50 views

### What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: \begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ &... 0answers 28 views ### ternary string that contains only 0's, 1's, and 2's A string that contains only 0's, 1's, and 2's is called a ternary string. (a) Find a recurrence relation for the number of ternary strings that do not contain two consecutive 0's. (b) What ... 0answers 24 views ### What does “symbolic computation” mean in this context? From Wikipedia In computational mathematics, computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of algorithms ... 0answers 33 views ### What is the root of first class object in programming languages? What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and http://stackoverflow.com/questions/245192/what-are-first-class-... 0answers 23 views ### Help with a proof of the computability of the monus function by recursion Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) (x+... 1answer 38 views ### If NP-complete, prove another is also NP-complete I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step. 0answers 12 views ### Minimum number of pages in a B-Tree of order n? How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages? 1answer 23 views ### Time complexity for loops I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. int j = 1; int n = any; ... 1answer 53 views ### Algorithms - Finding Clique of size n in a Graph I have the following statements (NOTE: \bar x means the complement of x): (x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4) I need to do the ... 4answers 56 views ### How to check if n! is  O(2^n) How can I check if n! \in O(2^n)? The definition of f being O(g) is f(n) \le c g (n), where c>0. So it would mean n! \le c 2^n. What is the clearest way to solve this? (As I am ... 1answer 39 views ### Hash functions - show how to find collisions I'm currently trying to solve this exercise (sorry for image, it's for the notation and I'm not allowed yet to post images directly): I have read the exercise question a lot of times and I think I ... 0answers 18 views ### Balancing integer bins to have a certain summation Assume that we have bins B_1, B_2 ..., B_n $$There exists integer bin values$$ V_1, V_2 ..., V_n $$Let$$ Total_{V} =\sum_{i=1}^{n} V_i$$There then exists weights (  W ) of each bin to ... 0answers 14 views ### Is O(x^2) equal to OR a tighter bound for O(x(x-y)) if x, y >0 and x>y alway hold? In the question, O is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. x and y are variables. Here, let me give you an example showing there exist such questions in ... 0answers 20 views ### Is the Antikythera Mechanism Turing-Complete? Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ... 1answer 22 views ### Encryption - show probability for obtaining specific bit Assume a person A encrypts a message which consist of the bits m1, ..., mn. The person is using the one-time pad algorithm. Another person B intercepts the ciphertext and we suppose he knows that mi (... 0answers 11 views ### Does the Method of Compliments also work for (non-integers)? I have only ever seen Method of Complements applied to integers, never non-integers (most notably in the field of modern programming) However curiosity got the better of me, and I was wondering if ... 1answer 35 views ### Big O for factorials Hello I have trouble proving:$$(n+1)!\notin O(n!)$$My first step is the following:$$(n+1)!-cn!\le0 Can you please help me with the next step?
Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$? I found some estimate on computing the Smith Normal Form $N$ such that \$...