Tagged Questions
3
votes
0answers
65 views
What is Algorithmic Graph Theory?
I'm an undergraduate and I signed up for a course next semester called Algorithmic Graph Theory. The course description doesn't give any details on the contents of the class, and there's no listing of ...
1
vote
3answers
109 views
Largest prime factor of 600851475143 [duplicate]
I'm trying to use a program to find the largest prime factor of 600851475143.
This is for Project Euler here: http://projecteuler.net/problem=3
I first attempted this with the code that goes through ...
1
vote
1answer
142 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
2
votes
1answer
79 views
Computing RSA Algorithm
Modulus $N=247$; encryption exponent $r=7$
Encrypt $100$; Decrypt $120$.
$Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$.
For a discrete math ...
0
votes
1answer
41 views
How to use Warshall's Algorithm
This question appeared on my homework and I don't have the slightest idea how to solve it!
...
3
votes
0answers
82 views
Difference between two sets of data points
I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
1
vote
1answer
86 views
Topological Sorting in Linear Order for Hasse Diagram
I have come across an exam review question that I am stuck on. The question states:
Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram:
This is ...
0
votes
1answer
54 views
Big-O Big theta Big omega papers
I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
0
votes
4answers
120 views
Solving recurrence relations (change variable etc.) problems
I have been given
$$f(1) = 3\\
f(2) = 8\\
f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$
How would I go about solving this? I've tried working so hard to get this to no avail. If someone can ...
0
votes
1answer
72 views
Recurrence relation using the master theorem $ T(n) = 4T(n/2) + n^2 \log n$
I am trying to solve the following recurrence relation using the master theorem:
$ T(n) = 4T(n/2) + n^2 \log n$
So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2 $
Now i know that $n^2 \log n ...
0
votes
1answer
23 views
How to compare $ n^{\epsilon} $ and $ \log^bn $ ($\epsilon>0 ,b>1)$
How to compare :
1) $ n^{\epsilon} $ and $ \log^bn $ ($\epsilon>0 ,b>1)$
and 2)$n^{\log n\log\log n}$ and $(\log n)!$
0
votes
0answers
17 views
Dutertre-DeMoura worked examples
does anybody know where I could find some worked examples + an easy-to-understand explanation of the Dutertre-DeMoura algorithm?
I have found this pdf (contains two examples), but I'm not so good at ...
3
votes
2answers
279 views
Graham scan convex hull algorithm - include all points on boundary
I have am implementing the Graham scan algorithm to find the convex hull of a set of (two-dimensional) points. (My implementation is in Haskell in case anyone wants to know.) The problem is that not ...
0
votes
1answer
61 views
Why is the upper bound of this statement always incremented by 1?
Why is "for j = 1 to n" translate to this? Why is the upper bound always incremented by 1?
$$\sum_{j=1}^{n+1}1 $$
Why isn't it
$$\sum_{j=1}^n1 $$
"for j = 1 to n" is written in pseudo code btw ...
0
votes
2answers
82 views
Finding a shortest path between a set of points
Suppose:
$x_1,x_2,x_3,x_4$ is a shortest path from $x_1$ to $x_4$
$x_2,x_5,x_6,x_7,x_9$ is a shortest path from $x_2$ to $x_9$
$x_{10},x_5,x_8,x_3,x_9$ is a shortest path from $x_{10}$ to $x_9$
...
0
votes
1answer
43 views
Finding recurrence and an algorithm to represent it
You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy
algorithm is not guaranteed to find the optimal way to ...
1
vote
0answers
113 views
0
votes
1answer
72 views
how can i solve sigmoid function?
$$\frac{1}{ 1-e^ {-(-3.0)}} = -0.052$$
$-0.052$ is the answer. This equation is sigmoid function. How could I get the answer like that? Please understand me T.T
4
votes
3answers
175 views
0
votes
1answer
85 views
Using induction to show a greedy algorithm always makes the optimal task selection
Suppose we have a greedy algorithm like the following:
...
0
votes
2answers
79 views
How can induction be used to prove binary search is correct?
I'm having trouble understanding how to find an invariant to check if it's preserved, and generally how induction is used in proving the correctness of algorithms (binary search primarily, but others ...
1
vote
1answer
532 views
How does Dijkstra's algorithm work?
Can someone succinctly explain how Dijkstra's algorithm works and how it may be used to find the shortest path for such a graph (from a to z)?
I've looked at some procedures online, but many of ...
2
votes
1answer
116 views
Find number of sub-squares in portion of graph
i cam across this puzzle, we are supposed to find out the total number of squares present in this picture...
as being a computer programmer i designed a algo in my head for the solution and did a ...
0
votes
1answer
134 views
has deleting node in a binary search tree Displacement feature?
I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
1
vote
0answers
85 views
Question about ratios and combinatorics
In this question that I posted yesterday (11/15):
I am solving a programming puzzle that consists of finding all the possible ways to build a brick wall of $48$" $\times$ $10$" (width $\times$ height ...
2
votes
4answers
216 views
why $m$ power by $n$ equals sum of $n$ numbrs
$$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$$
(a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are $m$ and $n$. I know that this is true, ...
1
vote
3answers
165 views
Proving a factorial is not a certain complexity
I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that?
Problem: Prove ...
1
vote
2answers
275 views
Calculating Average Case Complexity
I am trying to find the average case complexity of a sequential search. I know that the value is calculated as follows:
Probability of the last element is $\frac{1}{2}$
Probability of the next to ...
1
vote
2answers
102 views
Algorithmic Complexity of $i^2$
I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone ...
1
vote
2answers
140 views
If $f(n) = \sum_{i = 0}^n X_{i}$, then show by induction that $f(n) = f(n - 1) + X_{n-1}$
I am trying to solve this problem by induction. The sad part is that I don't have a very strong grasp on solving by inductive proving methods. I understand that there is a base case and that I need an ...
5
votes
1answer
102 views
What function $f$ such that $a_1 \oplus\, \cdots\,\oplus a_n = 0$ implies $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$
For a certain algorithm, I need a function $f$ on integers such that
$a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$
(where the ...
3
votes
1answer
192 views
Karatsuba Multiplication
Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm):
$$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd ...
1
vote
1answer
272 views
Ulam's problem - guessing a chosen number in a set
I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition):
Suppose someone ...
4
votes
1answer
671 views
Quick sort algorithm average case complexity analysis
This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications".
The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
1
vote
0answers
202 views
Mathematics in the “ The Art of Computer Programming”
I don't know of this the right place to ask this type of question and hence I apologize (in advance) for any inconvenience. Here is my question: I have studied Concrete Mathematics by Knuth, Graham ...
1
vote
0answers
23 views
Petri net analysis.
I have problems with this exercise. First: can the token in place $p_1$ to enable the transitions $t_2$ and $t_3$? The place $p_1$ has a single token, I think it fails to enable $t_2$ and $t_3$. Any ...
3
votes
2answers
260 views
Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.
This question is from "Discrete Mathematics and Its Applications", from Kenneth Rosen, 6th Edition.
Devise a Monte Carlo algorithm that determines whether
a permutation of the integers 1 through ...
0
votes
1answer
165 views
Finding Big-Theta
I need to use the Master Theorem to find $\Theta(f(n))$ if $f(n)=f(n/2)+3n$ and $f(1)=3$
I don't know how to use the MT in this case, can anyone provide help?
4
votes
1answer
196 views
Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?
This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.
Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
2
votes
1answer
314 views
Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements
I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
4
votes
0answers
116 views
Convex hull of balls
The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
1
vote
2answers
256 views
Number equal to the sum of powers of its digits
I've got another interesting programming/mathematical problem.
For a given natural number q from interval $[2; 10000]$ find the number $n$
which is equal to sum of $q$-th powers of its digits, ...
0
votes
1answer
116 views
About showing that the print statement in the pseudocode is executed $C_n$ times
It is an exercise I meet in the book Discrete Mathematics Fifth Edition written by Richard.It is on page 184.It is not my homework!I just learned it by myself but I can't catch up with the solution to ...
-3
votes
1answer
118 views
Proving $T(n) \ge 2^{n/2}$, for all n, by induction
Trying to solve the following induction question, but I seem to be getting cold cause I am lost! Can someone help me, then point me in a direction I can relearn this stuff :)
Wanted to prove: ...
2
votes
0answers
58 views
Petri net analysis (attainability)
how to analyse safe petri net for attainability?
(i need algorithm)
I have an oriented multigraph $\mathbb{G}$.
$A$ - adjacency matrix.
$m$ - the count of input elements.
$n$ - the count of ...
1
vote
0answers
45 views
determine the max flow function $f^*$ in a network given the maximum flow value
Suppose I have a Network N
( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out)
...
1
vote
1answer
353 views
Partitioning a set of integers into 4 subsets with equal subset sums
Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other.
I am interested in ...
0
votes
1answer
195 views
properties of the Greedy Algorithm (Graph Colouring)
So I have shown, that for all n $\in N $ there is a graph $G$ with n vertices such that the Greedy Algorithm will colour it in exactly 2 colours.
Further I have shown that for a Graph with diameter ...
0
votes
1answer
161 views
Existence of Vertex Ordering in Greedy Algorithm to get “optimal” colouring
I am trying to prove that for any Graph there is an ordering of the vertices, sucht that the Greedy Algorithm will colour the vertices in such a way that it uses the Chromatic number of colours.
I am ...
2
votes
2answers
139 views
Traditional Marriage GS female pessimality
In the context of stable matchings I am currently trying to understand the Gale-Shapely Algorithm (traditional marriage algorithm).
I have proved it s correctness and I have shown that its male ...
