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

7
votes
1answer
53 views

Applications of the following theorem in the real world

We know that every permutation can be expressed as a product of transpositions ( cycles with length 2). As a class project I'm looking for the applications of this fact in the real world; especially ...
0
votes
1answer
28 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
1
vote
1answer
20 views

Generating a 2D coordinate from a 1D Index

Imagine you have a 5x5 matrix (zero indexed), where only the upper right coordinates are valid. I am unsure if this is the terminology to use, so the following coordinates should be the valid ones: ...
3
votes
2answers
42 views

Is there a way to rewrite this recursive function so that it can be calculated in linear time?

I have this recursive function: $$ f(0)=f(1)=1 \\ f(x)=\sum_{i=0}^{x} f(i)×f(x-1-i) $$ The sequence turns out to be $1,1,2,5,14,42, \dotsc$ I want to be able to calculate the nth element ...
-6
votes
1answer
213 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
0
votes
0answers
20 views

Fractional hexadecimal addition.

i have searched the web and through out the forums but, i couldn't find an exact answer. This is my first question, and please excuse my english. I am doing my CS homework which includes adding some ...
0
votes
0answers
16 views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
2
votes
1answer
57 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
3
votes
1answer
90 views

What is the difference between Set, and Class in object oriented languages?

What is the difference between Set in set theory, and Class in object oriented languages?
0
votes
0answers
45 views

Best time complexity for calculating the next, unique graph.

Whats the best time complexity, for a known algorithm, that when called generates the next, unique, graph, in order of node count? For example, the first result being the only single node graph, I ...
1
vote
0answers
44 views

Application run time estimation as mathematical formula/function

I'm writing a program that sends out text messages en masse. The program will split up the total number of texts into batches. These batches will be triggered, one at a time, after a set time period, ...
3
votes
2answers
70 views

What are BesselJ functions?

I solved an integration on mathematica which gives BesselJ functions and some other terms. I explored mathematica help and google but could not understand the difference between different types of ...
2
votes
1answer
38 views

Why does complement arithmetic work?

I'm learning about how computers store and manipulate integers, and I want to understand two's complement. Despite an abundance of web-sites demonstrating how to perform complement arithmetic, the ...
2
votes
2answers
21 views

Deriving a Formula From a Simple Artificial Language

The three rules of the language are: The letters P and Q are sentences. If φ and ψ are sentences, then Nφ and (Iφψ) are sentences. Nothing else is a sentence. (no more information was given about ...
1
vote
0answers
18 views

What is a strictly casual function?

What is the difference between a strictly casual function and just a casual function?
-2
votes
1answer
77 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?
2
votes
1answer
30 views

Discrete Mathematics: Relations

Confused about this question: Describe two binary relations $R$ and $S$ on $\{1, 2, 3\}$ that are not equivalence relations, but whose composition $R\circ S$ is an equivalence relation.
3
votes
0answers
43 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
0
votes
2answers
51 views

Complete labeled Graph $K_6$ and Spanning Tree [closed]

I ran into a nice interview question, anyone could described it for me? from Complete labeled Graph $K_6$, remove one edge, how many spanning tree, the resulted graph has? Mathematician Learn ...
1
vote
1answer
45 views

Book recommendation for wavelet analysis

I am master student doing research in data mining, i read a paper about wavlet analysis for data mining, so i think it may help me in the future. But in my undergraduate degree the last course in ...
0
votes
1answer
34 views

Homework in logics for Computer Science : Prove that the groups are equal

$A$ is a group and $B_1,B_2\subseteq A$. $F_1,F_2$ groups of functions so each $f\in F_1\cup F_2$ : $f:A^{n}\to A$. We call $S_1= X_{B_1,F_1}$, (this notation means the group that contains B1 members ...
0
votes
1answer
21 views

Application of wavelet analysis in computer science

I am doing research in computer science (data mining), do you think wavelet analysis is useful for me?
1
vote
1answer
19 views

Why is the maximum number of integer values per fixed-length variable sightly more than the amount of values for the previous one squared?

For example; an 8-bit variable can have 255 total values. 255 squared is 65,025, but the amount of total values for a 16-bit variable is 65,536. Where do these extra 511 values come from?
-1
votes
2answers
72 views

How many Hamiltonian cycles are there in $K_{10,10}$?

I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$ Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian cycles.
0
votes
1answer
64 views

Better time complexity.

I am new to complexity theory and want to know, Which one is better time complexity(faster) for an algorithm ? \begin{equation} \frac{n^{k+\log_2(n)}}{\log_2(n)2^{n}} \end{equation} or ...
0
votes
1answer
29 views

Closure of regular languages, Star Operator

Show with a counterexample that the following construction doesn't prove the closure of regular languages at the concatenation. In other words, find a NFA $N_1$ such that the NFA $N$ of the ...
9
votes
2answers
218 views

Counting sets by their connectedness

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
4
votes
1answer
73 views

Maths Discoveries thanks to Computer Science

Which discoveries have been made in mathematics thanks to computer science ? For example fractals have been discovered thanks to computers (correct me if im wrong) do you know any similar discoveries ...
0
votes
2answers
74 views

how many subsets with 4-elements? [closed]

I ran into a non-trivial question on one Statistics Book, how many subsets with 4-elements from set {$1,2,...,10$} can be taken such that hasn't two consecutive number in that subsets. how we ...
2
votes
1answer
26 views

Finding the size of sumsets in limited space

Let $S=\{a+b:\ a\in A,\ b\in B\}$. I have an explicit representation of $A$ and $B$, but $S$ is too large to store in memory. (For the sake of argument, say $A$ and $B$ are 100 MB and $S$ is 1000 TB.) ...
0
votes
1answer
41 views

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
1
vote
1answer
37 views

Sorting algorithms

How could we show that the algorithm of Mergesort is stable, Quicksort is not stable but it can be implemented as stable, Heapsort is not stable. I have show that the algorithm of Insertion ...
0
votes
1answer
25 views

the minimal deterministic finite automaton recognizing $\{1^n 0^n /n\leq N\}$

Given a language $L$ how can I determine the number of states of the minimal automate which recognizes $L$. I want some examples and to understand the methods that we can use to find a lower bound for ...
0
votes
1answer
28 views

Is the invariant correct?

I want to show that Insetion Sort is stable... Do I have to do that using an invariant?? Is the invariant the following?? At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b ...
2
votes
1answer
57 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
0
votes
1answer
21 views

Probability distribution of number of ordered items in a permutation

I have a simple algorithm to check if a series of numbers is sorted: if the first two numbers are sorted, move to the next two. Else, stop and return false. I want to figure out the average case ...
0
votes
0answers
20 views

Time estimation and big-O notation

Let a and m be elements of $\mathbb{Z}$ where m is positive. How can I show that the inverse of $a$ can be computed in $O(log^3m)$ bit operations? I thought that I should find the greatest common ...
1
vote
1answer
16 views

An infinite number of solutions available to the sparse representation problem

I would like to analyze the following problem (different cases leads to which solutions to the problem and such): $$||y-Dx||_2 \leq \epsilon$$ (an overcomplete dictionary matrix $D \in \mathbb{R}^{n ...
2
votes
1answer
42 views

Question about an inequality in a published paper which is yielded from an approximation

I am reading a published paper on K- SVD: An algorithm for designing overcomplete dictionaries for sparse representation In the introduction, it says: Recent years have witnessed a growing ...
0
votes
0answers
20 views

Question about a cycle when doing topological sorting

First off, this is a homework question, but I'm just a bit confused on some of the smaller details of doing a topological sort. The homework question can be seen here (it shows the graph). It says: ...
4
votes
1answer
133 views

Can someone verify my answers to these questions regarding this poset?

Problem: 18. Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4},{1,3,4}, {2,3,4}}, $\subseteq$) $\quad$a.Find the maximal elements $\quad$b.Find the minimal elements ...
0
votes
2answers
53 views

How to prove what amounts of postage can be formed with normal mathematical induction?

This is similar to my other question Strong induction but it addresses standard mathematical induction. Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 ...
0
votes
2answers
44 views

How to mathematically show that the relation is transitive?

Problem: Show that the relation $x R y$ iff $x \leq y$ is a poset over the set of integers $\mathbb{Z}$ My work: I know that to show the relation is a poset or a post order, I have to show the ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
3
votes
2answers
138 views

De Morgan laws of linear logic

I find it stated, in all the resources I have searched, that the following De Morgan laws$$(A\otimes B)^{\perp}\equiv A^{\perp}\wp B^{\perp}\quad\quad\quad (A\text{&}B)^{\perp}\equiv A^\perp ...
1
vote
2answers
42 views

Dividing the interval in subintervals of equal length

I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$ dividing the interval $[0, 1)$ ...
0
votes
0answers
36 views

Intersection of 2 deterministic finite state automata, but nondeterministically

Starting from 2 simple deterministic finite state automata, I need to construct a non-deterministic automaton that accepts the intersection of the two inputs. Using the algorithm presented at ...
2
votes
0answers
18 views

Compute the coefficients of a Runge-Kutta method

Let $f$ be a Lipschitz continuous function, $(a_{ij})_{1\le i,j\le s}$ and $(b_i)_{1\le i \le s}$ some real numbers, $x_0 \in \mathbb{R}$ and $h$ an arbitrary small positive number. Under some ...
1
vote
0answers
31 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
3
votes
0answers
159 views

Execution time of function

At the algorithm SELECT, there is the following step: ...