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

2
votes
0answers
28 views

Hashing Probability

I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a ...
0
votes
0answers
16 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
0
votes
0answers
7 views

How to find a strictly increasing sequence of words $(t_i)_{0\leq i\leq n}$ of maximum length ?

Let $L=\{0,1\}^*$ be the set of all words consisting of $0$ or $1$, we define an order in $L$ by: $$\begin{align}\forall (x,y)\in L^2 && \big( x\leq y&&\Leftrightarrow y=x\text{ or ...
0
votes
0answers
12 views

a proof about Gastnel's Method

this is a proof problem in in the book that i meet consider the linear system $Ax=B$,where $A$ is SPD matrix.Consider a projection step with $\mathcal{K}=\mathcal{L}=span\{v\}$,where $v$ is some ...
8
votes
0answers
168 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
0
votes
0answers
52 views

The problem of making change for $n$ using the fewest number of coins

Consider the problem of making change for $n$ cents using the fewest number of coins. Assume that each coin’s value is an integer. Describe a greedy algorithm to make change consisting of quarters ...
-2
votes
1answer
75 views

Application of the Knapsack Algorithm

I want to apply the Knapsack algorithm at the following: n = 4 (# of elements) W = 5 (max weight) Elements (weight, benefit): (2,3), (3,4), (4,5), (5,6) The ...
1
vote
0answers
35 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
0
votes
0answers
22 views

Are the expressions (a/b) %c and (a%(b*c)) /b equivalent?

As far as I know, to determine (a/b)%c, we need to determine (b^-1)%c which can be done using extended euclid, fermat's theorem, euler's theorem or there may be some other way, but what we must need ...
-1
votes
1answer
43 views

Knapsack Problem [closed]

There are two versions of the Knapsack problem, the integer and the fractional one. Could you describe them to me?? Which are the differences?? With what type of programming do we solve them?? ...
1
vote
0answers
56 views

A decision problem that is Cook reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements. Can anyone give me ...
0
votes
1answer
20 views

Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$

I am stuck at this problem for a long time: Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$ I tried to show that $\lim_{x\to\infty}\frac{ (lg\; lg\; x)^k}{lg^\epsilon ...
2
votes
2answers
43 views

How much knowledge of math do I need before taking bachelor of software engineering ?

I asked this question before, but now I knew who to form it correctly after doing some research for months. It always puzzles me what someone need to know before enrolling in bachelor of software ...
-2
votes
2answers
82 views

What is the algorithm to add 2 binary with boolean operations? [closed]

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
2
votes
2answers
21 views

Find the minimum value of $n$ such that $\sin^n(c)<\varepsilon$ for some small constant $\varepsilon>0$

Let $c$ be a constant such that $0 <c \le \pi/2$ and $\sin(c) \ne 0$. Question: What is the minimum value of $n$ such that $\sin^n(c)< \varepsilon$ for some small constant $\varepsilon >0$ ? ...
0
votes
3answers
38 views

Decrypt the following message that was encrypted using: Caesar’s cipher: WHVWWRGDB

Decrypt the following message that was encrypted using: (a) Caesar’s cipher: WHVWWRGDB I'm told to decrypt the message using Ceasar's cipher but they don't tell me the key shift so how in the world ...
1
vote
1answer
37 views

Huffman Encoding Symbol Probability [duplicate]

Prove for two symbols a and b, if p(a) >= p(b), then according to Huffman encoding algorithm, the resultant code length L(a) <= L(b). I did several examples of this and it is true. But how can I ...
1
vote
2answers
64 views

Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
0
votes
0answers
31 views

On Tree- Doubling Algorithm

Use the Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically. Need help to this question. Thanking you.
3
votes
1answer
25 views

Constructing a recursive definition.

I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of ...
0
votes
1answer
21 views

asymptotic complexity of functions

I'm curious if my asymptotic analysis of these functions are correct. I know the process is to strip the constants and then get to where its just comparing functions and taking limit to infinite and ...
1
vote
1answer
34 views

Determine Sample Space S and Prove Return of 0 with Pr of 2/3?

I have this homework question I'm stuck on. I have no idea where to start for either questions. Any help is appreciated! Thank you
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
211 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
19 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
15 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
56 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
43 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
69 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
76 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
46 views

Complete labeled Graph $K_6$ and Spanning Tree

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