Tagged Questions
0
votes
1answer
26 views
Does this algorithm terminate in finite time?
I am trying to determine whether the following algorithm terminates:
...
1
vote
0answers
49 views
count the number of connected induced subgraphs in a graph with bounded degree
Let $G=(V,E)$ be a graph where the maximum degree of a vertex is 4. I've been asked to find an efficient algorithm for counting how many connected induced subgraphs are in $G$.
What I have so far is a ...
0
votes
0answers
19 views
Divide an array in 3 subarrays satisfying some properties.
Given an array $S[p\dots r]$ and a pivot rearrange the elements such that the returned array follow this properties. Algorithm sould be $O(n)$
if $p \le k \le q_1$, then $S[k] < \mathrm{piv}$;
if ...
1
vote
4answers
98 views
Error in “proof” of $n^2 \in O(n)$.
I need some help. I have homework:
I need to disprove that $f(n^2)$ belongs to $O(n)$.
Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
1
vote
1answer
22 views
Solving recurrenc using recurrence tree method.
I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$.
I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
0
votes
0answers
44 views
How would I create a birthday attack? (Hash Functions)
I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
1
vote
2answers
41 views
Prove that a greedy algorithm selects the maximum number of programs
This is a homework problem. Intuitively, I know it to be true, because the largest group of programs (say, $j$ programs) must be composed of the smallest $j$ programs. But how to go about formally ...
0
votes
1answer
72 views
Solving the following recurrence relation
I have a recurrence relation, it is like the following:
$$
T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm}
$$
To solve this and find a Θ bound, i tried the following: I ...
0
votes
1answer
56 views
Recurrence relation
The recurrence relation $T(n)=4T\left(\frac{n}{2}\right)+n^2$ describes the running time of an algorithm $A$. Competing algorithm $A'$ has the running time of $T'=aT'\left(\frac{n}{4}\right)+n^2$. ...
0
votes
1answer
37 views
What is a good reference for basic shape detection algorithms
I've been doing research for a presentation on computer vision, and right now I'm specifically researching shape detection. Since this is a math course and not a programming course, I'm only concerned ...
1
vote
2answers
40 views
Showing $f(n)$ has upperbound of $O(g(n))$
I am currently enrolled in an algorithms course and was learning about upper, lower and tight bounds of functions.
I am confused on how to show that a function $f(n) = O(g(n))$ for some $n > n_0$ ...
0
votes
1answer
162 views
Dominant term and Big Omega
For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation.
$$n^3+n^2\log_2(n)+n^3\log_2(n)$$
So, I ...
1
vote
1answer
72 views
Properties of shortest walks and simple paths during optimization
Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...
0
votes
1answer
28 views
Bounding below the difference of sums
I would like to bound below the following expression:
$\lambda(m,n)=\sum\limits_{i = 1}^{m+n}\lg{i} - \sum\limits_{i = 1}^{m}\lg{i} - \sum\limits_{i = 1}^{n}\lg{i}$
by some expression that ideally ...
0
votes
0answers
79 views
Implement a Turing machine, Solve the system of logical equations
№ 1 Implement a Turing machine:
The input is a sequence of 0 and 1. The machine should be replaced every second 0 to 1. Example: 000111 replaced to 010111.
To demonstrate the correctness of your ...
0
votes
2answers
59 views
Puzzle involving selecting gloves
There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown, 2 pairs of grey. You select the gloves in the dark and check them only after you have made the selection. What is the ...
1
vote
1answer
452 views
Algorithm to check whether a graph has no cycles
Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of ...
0
votes
0answers
16 views
Show that for every deterministic algorithm ALG, there is some scenario in which the total distance John’s trucks traverse under ALG is 3OPT
There are 3 popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the ...
2
votes
2answers
100 views
Theta bound about $\sum \lfloor {\sqrt{n}}\rfloor$
$$S_k=\sum_{n=1}^{k^2-1}\lfloor\sqrt{n}\rfloor $$
Can somebody give me an idea about the steps I should follow?
Initially I thought
$$n^{1/2}\log(n) \leq n^{1/2}\leq n^{3/2}$$
so $\Theta(f(n))=S_k ...
1
vote
3answers
100 views
Fermats Little Theorem
I need help in the use of Fermat’s Little Theorem, in order to calculate the remainder of $5^{120}$ when divided by 19.
Thank you.
0
votes
1answer
82 views
How to get numbers with distinct digits within some range?
I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
0
votes
0answers
118 views
Solve recursion formula using Recursion Tree concept
I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea.
I will first write down the exercise and then I'll try to explain ...
1
vote
2answers
674 views
Runge-Kutta algorithm for a given ODE system
consider the system given by:
$$x'_{1}=9x_{1}+24x_{2}+5\cos t-\dfrac{1}{3}\sin t$$
$$x'_{2}=-24x_{1}-51x_{2}-9\cos t+\dfrac{1}{3}\sin t$$
with initial values $$x_{1}(0)=\dfrac{4}{3}$$ and ...
0
votes
3answers
58 views
Big-O compared to a new Operator
I'm trying to figure out a new operator compared to the Big O.
Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
0
votes
1answer
85 views
Multiplying Polynomials with fewer coefficient multiplications
Not sure how this works! Apparently it can be done in 5-6 multiplications
Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.
1
vote
1answer
138 views
Computational Complexity of Modular Exponentiation
The following was posted from a lecture:
"($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method.
$Z_1 = a \bmod N$
$Z_2 = (aZ_1) \bmod N$
$Z_3 = (aZ_2) ...
3
votes
1answer
261 views
Solving a recurrence relation using back substitution.
This is related to analysis of algorithms (divide and conquer), but since it's mostly math, I thought it would be better to post here instead.
I'm trying to solve a recurrence relation using back ...
0
votes
1answer
80 views
Showing a recurrence is $\Theta$(n)
Specifically how do you go about showing that
$$
2T(n/2)+1 =\Theta(n)
$$
Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in ...
1
vote
2answers
90 views
Sorting Algorithm analysis on a list of 0 and 1 element.
I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only.
a) Heapsort
b) Quicksort
c) MergeSort
d) ...
0
votes
1answer
451 views
How to solve the recurrence $T(n)=3T(n/2)+n$
The exercise stated that i have to solve the recurrence using the Recursion-Tree Method.
I have already finished the base part, which is $\Theta(n^{\lg3})$
But for the recursive part I'm having ...
0
votes
0answers
53 views
Is this a correct translation from recursive function to math notation?
I have this recursive function, written in Java. Assignment is to translate it to mathematical notation.
...
1
vote
1answer
51 views
What do we mean by 1. and 2. order difference and what can this be used for when making lines and shapes?
So, I got this assignment I'm working on and one of the questions sounds like this:
What do we mean by 1. and 2. order difference and what can this be used for when making lines and shapes?
I ...
3
votes
3answers
159 views
Working out an algorithm for finding out whether a point is in or outside of a 2D closed polygon
I'm having a bit of an issue with the following problem:
Write a brief (1/2 page) design specification document (including pseudo code for the algorithm itself) that describes your approach to ...
3
votes
1answer
50 views
Show that we can compute the product $n = \Pi_in_i$ in time $O(len(n)^2)$ for given integers $n_1,…n_k$ with each $n_i> 1$.
Show that we can compute the product $n = \Pi_i\ n_i$ in time $O(len(n)^2)$ for given integers $n_1,...n_k$ with each $n_i> 1$.
I know that we can compute $ab$ in time $O(len(a)len(b))$ courtesy ...
7
votes
1answer
124 views
Put a mouse to the last cell
We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.
At each step, we can do one of two operations:
$\mathbf{P}$: Put only in the first cell $C_1$ 2 mice.
$\mathbf{M}$: Move ...
2
votes
3answers
150 views
Multiplying exponents, solving for n
When solving for n in this equation I get stuck.
Question: What is the smallest value of n such that an algorithm with running time of $\ 100n^2 $ runs faster than an algorithm whose running time is ...
5
votes
3answers
104 views
Understanding this summation identity
I'm currently reading a book in which part of the solution to the problem involve this identity:
$$\sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j-\sum_{j=1}^{i}j$$
Which I cannot derive myself. The only thing ...
2
votes
2answers
123 views
What's the recurrence relation to this problem?
A machine can perform $3$ types of operation $A$, $B$ and $C$. The memory is initially $0$. A Program $P$ is a series of these operations. If the machine does $A$, it will add $1$ to the memory's ...
2
votes
1answer
64 views
Interval scheduling by minimum spanning tree
This is a homework and I'd like your feedback on whether I'm on the right track. Thank you.
Problem:
There's a project to build a railroad to connect $n$ cities. The railroad that connects any two ...
0
votes
0answers
154 views
Algorithm for Gram-Schmidt orthogonalization process
Let $f$ be a continuous function on $\mathbb{R}$ with compact support with exactly one maximum. Form the functions
$$
f_{m,k}(x)=f^m\left(x-\frac{k}{2^m}\right), k \in Z, m>0.
$$
Fix $m$. How ...
0
votes
0answers
115 views
Gram-Schmidt orthogonalization process for Hermite functions
I am trying to do Gram-Schmidt orthogonalization process for functions. I need to use this process on [-1,1] for the Hermite functions with n=1,2,...40: $$
h_n(x)=(-1)^n\gamma_ne^{x^2/2} ...
1
vote
1answer
101 views
Sum in tree nodes - algorithm
I've got one very hard problem.
Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes.
...
0
votes
1answer
130 views
What is the sum of this?
What is the sum of this
$$ \{n,n-1,...,3,2,1\}, ...... \{5,4,3,2,1\}, \{4,3,2,1\}, \{3,2,1\},
\{2,1\}, \{1\} $$
I am learning Data Structures and Algorithms now, I want to calculate the ...
0
votes
0answers
63 views
Does a Minimum Spanning Tree entail minimum cost between 2 vertices?
In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks
0
votes
1answer
83 views
how to prove this scheduling problem
I need some hints for proving the correctness/optimality of the below homework problem. It is a task-schedulding problem with deadlines and penalties. There are n tasks, each of which has a deadline ...
3
votes
1answer
83 views
Determining position at some point in time
I try to solve the following problem.
On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
2
votes
2answers
133 views
Turing reduction
I'm learning algorithm theory. Homework question is:
Are $A$ and $B$ possible so that $A\not\le_{tt}B$ (impossible to reduce using tt),
but $A\le_T B$.
But I can't think of any example..
0
votes
1answer
61 views
Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?
A algorithm require one second to resolve a problem of size $1000$ a local machine.
How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
0
votes
1answer
327 views
Improving Gift Wrapping Algorithm
I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points.
...
1
vote
1answer
134 views
Combinations of lego bricks figures in an array of random bricks
I have an assignment where a robot should assemble some lego figures of the simpsons. See the figures here: Simpsons figures!
To start with we have some identical sized, different colored lego bricks ...
