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

learn more… | top users | synonyms

0
votes
0answers
15 views

Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For ...
8
votes
1answer
265 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
-1
votes
0answers
43 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
-1
votes
0answers
6 views

Scilab Programming Question on systems of non-linear equations [on hold]

I am new to Scilab. Can anyone please help with the following tutorial question? I am drawing a total blank and don't know where to start. "Consider the following non-linear system of equations: g(x; ...
0
votes
2answers
40 views

Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers. For example, thease values where $N = 4, B = 4$. ...
11
votes
1answer
249 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
-1
votes
0answers
22 views

What are “bits” when the base is > 2? [on hold]

Is a bitshift operator (f(0)=1) generalizable to systems with base n>2? Because it is a trick to shift the bits n steps to the left if we multiply by 2^n, is that generalizable to any base b^n?
2
votes
0answers
16 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
0answers
40 views

Arc length using bisection error - root finding methods.

Apologies if this is poorly formatted - it is my first time posting a question. I'm trying to find evenly spaced arc lengths along a function (in this case a sinusoid) using the bisection method. ...
1
vote
1answer
18 views

Hilberts tenth problem over $\mathbb R$ with coefficients in $\mathbb Q$

Consider the following decision problem: Given: An equation $f(x_1, \dots, x_n) = 0$ where $f(x_1, \dots, x_n)$ is a polynomial with variables $x_1, \dots, x_n$ and coefficients in $\mathbb Z$. To ...
1
vote
2answers
31 views

Find particular pair of values that satisfy equation

I think this is might be a fairly simple problem, but I can't for the life of me think of a way to approach it. In this equation, for a given $x$ and $y$, with $x,y,a,b$ non-negative integers: $x2^a ...
0
votes
1answer
27 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 ...
1
vote
1answer
40 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 ...
0
votes
1answer
41 views

Solve $T(n)=16T(n/2)+2n^4$

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\\ ...
1
vote
0answers
19 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 ...
0
votes
0answers
20 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 ...
1
vote
0answers
31 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 ...
0
votes
0answers
18 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) ...
-1
votes
1answer
32 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.
0
votes
0answers
10 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?
0
votes
1answer
18 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; ...
0
votes
1answer
43 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 ...
1
vote
4answers
54 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 ...
0
votes
1answer
37 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 ...
0
votes
0answers
17 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 ...
-1
votes
0answers
4 views

Minimizing the distance between two set of vectors such that the angle of both set is equal

Suppose I have two set of vectors K1,I1 and K2,I2 forming a surface S1 and S2 respectively in R2 or R3. The angle between K1 and I1 is T1 and K2 and I2 is T2 respectively. The goal is to minimize the ...
1
vote
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 ...
0
votes
0answers
11 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 ...
0
votes
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 ...
0
votes
0answers
10 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 ...
0
votes
1answer
34 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?
1
vote
1answer
77 views

Computational complexity of solving linear diophantine equations?

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 ...
0
votes
0answers
12 views

conditional in basic arithmetic

So I am creating a CSS Framework (for web), which aim to be very responsive. So here's my problem: Is there a way to get/compute with only using +, -, * and / (basic arithmetic) to replace the if ...
1
vote
1answer
30 views

Boolean Algebra laws of deduction question

I have a question in which I'm a little stuck at answering, could anyone help? ...
0
votes
1answer
25 views

Implementation of Heap (ADT) using Array Vs. LinkedList

In data-structure course , I need to implement a binary heap with the following time - complexity requirements: Find Max - O(1) Insert - O(log n) Delete Max - O(log n) Now I thought to implement ...
3
votes
3answers
41 views

Proving that $\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular using the pumping lemma.

I need to prove that $L=\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular. First of all I assume that L is regular. Then L satisfies the pumping lemma, so let p be the pumping length. I've tried ...
1
vote
1answer
46 views

Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
1
vote
1answer
67 views

Show that the following function is primitive recursive

Let $f$ be a function defined by \begin{array}{l} f(0)=1;\quad f(1)=2;\quad f(2)=3;\quad f(n)=0 \mbox{, for $n>2$} \end{array} How to show that $f$ is primitive recursive?
1
vote
1answer
27 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are ...
1
vote
0answers
18 views

Disadvantages of particle swarm optimization method

I am using particle swarm optimization method. It has a lot of advantages, but I am looking for disadvantages of this method. Can you help me?
-1
votes
4answers
76 views

How in this world can I simplify this $\sqrt 2\cdot(1/(\sqrt2)-1/(\sqrt2)\cdot i)^{31}$ ????

I have a problem, obviously. I am doing some maths and now I have to simplify this: $\sqrt 2\cdot(1/(\sqrt2)-1/(\sqrt2)\cdot i)^{31}$ ????. But I just don´t know how ???? I´ve started simplifying by ...
1
vote
2answers
64 views

Proof by Induction

I am attempting to prove by induction that the algorithm calculates the cube of a number, I can't for the life of my grasp it. I was wondering if someone could help me please. The question is: A ...
0
votes
0answers
18 views

Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
0
votes
0answers
23 views

design a finite state automaton that divides by 2

I'm super confused in my computation class. How do you compute an FSA that divides by 2? Thank you. We can only use 1's and 0's.
0
votes
0answers
20 views

Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
0
votes
0answers
21 views

Convert a PDA to a CFG

My professor doesn't do a very good job at explaining the process of converting a PDA to a CFG. Can someone help explain it? The way I see it (but it produces wrong results) is each production is ...
0
votes
1answer
49 views

Is this a valid representation of real numbers?

I am trying to find the simplest representation of real numbers on the lambda calculus. I've thought about this one, and wonder if this is valid. First, we define a real number in the range ...
1
vote
0answers
36 views

Find a number a using strange computer

IN the $\#1$ slot of the computer memory there is number $a$. The computer is able to sum, multiply, divide and subtract from selected slots, writing the result in to the selected slot. It is also ...
0
votes
1answer
13 views

How to Alphabetically Arrange Nodes in a Huffman Tree

Suppose there is a string of characters helloworld. The frequency of these characters are d1, e1, h1, l3, o2, r1, w1. So, when inserting them into the huffman tree, the root node should contain d1, ...
0
votes
1answer
25 views

Find execution time in DAG of tasks

I have to find the difference between the worst and the best possible execution time in a DAG (directed acyclic graph) of tasks. The DAG of tasks looks like the following: ...