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
2answers
47 views

Finding a grammar for given language

So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be. The language in this problem is: $\{bb, bab, baab, ...
0
votes
2answers
53 views

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered the same when everyone has the same immediate left and immediate right ...
1
vote
1answer
46 views

How many binary bit strings of length 32 are there

How many binary bit strings of length 32 are there? I think I know the answer but I'm not sure...wouldn't it just be $2^5$ ?
1
vote
1answer
22 views

How to show that a language is regular?

Let $L$ be a regular language over $\Sigma$. Show that: $$\left\{ x_1x_2 \dotsm x_k \mid x_1,x_2,\ldots , x_k \in \Sigma, \exists y_1, y_2, \ldots, y_k \in \Sigma: x_1y_1\dotsm x_ky_k \in L ...
0
votes
0answers
19 views

How did we get the relation?

The fractional knapsack has the greedy choice property. Proof: Let`s consider that the ratio $\frac{V°}{w°}$ is maximal. This assumption implies that $$\frac{V°}{w°}\geq \frac{v}{w}\text{ for ...
2
votes
1answer
25 views

Average case complexity for checking if list is sorted

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is ...
2
votes
0answers
34 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
1answer
30 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
13 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
171 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
80 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
77 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
37 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
24 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
55 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
1answer
64 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
23 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
68 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 ...
-1
votes
2answers
94 views

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

What is the algorithm to add up two binary numbers using only boolean operations (negation, conjunction, disjunction) in linear time? Also the program flow needs to be "linear" as well, meaning there ...
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
57 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
42 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
75 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
37 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
36 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
22 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
35 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
54 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
31 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
23 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
43 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 ...
-5
votes
1answer
217 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
1answer
31 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
17 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
58 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
93 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
46 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
61 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
91 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
40 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
22 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
20 views

What is a strictly casual function?

What is the difference between a strictly casual function and just a casual function?
2
votes
1answer
31 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
49 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
55 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
49 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
36 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
23 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?