# Tagged Questions

32 views

### Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
32 views

### Is complexity change when multiply with some number

The power operation with modulo operation $a^b \mod n$ has time complexity $O(\log n)$. what happen when it is multiplied with a number $p·a^b \mod n$, it can be read as $(p \mod n)(a^b \mod n)$. Is ...
31 views

### Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
37 views

### Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
41 views

### How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
15 views

### (Algorithm complexity) Find properties of ≪ relation

I got a exercises related to algorithm complexity analysis as below ...
24 views

### Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
11 views

### Polynomial-time reduction and complexcity sets P and NP.

hello I am having difficulties to understand the topic of P,NP and Polynomial-time reduction. I have tried to search it on web and ask some of my friends , but i havent got any good answer . I wish ...
One of the problems that has been a roadblock in my understanding of ideals has been how one would find them. One way of finding an I of some ring R would be to say $\forall x \in I, \forall r \in R ... 2answers 66 views ###$O(n^{\log(n)}) $time algorithms Is$O(n^{\log(n)}) $time algorithm considered of exponential time ? Is it applicable ? 1answer 31 views ### Generalization of Jacobi symbol for higher powers? Let$n$be an odd positive integer of unknown factorization, and let$x$be relatively prime to$n$. The Jacobi symbol$\left(\frac{x}{n}\right)$gives me partial information on whether$x$is a ... 0answers 53 views ### Calculating time complexity of algorithms written in pseudocode. Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem$X$there is an algorithm with running time$O(n^3)$we try to break ... 1answer 74 views ### Mixed Q horn SAT I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ... 1answer 87 views ### Questions about a computer science field I would like to have some information about the computer science field, " Algorithmic and Systems Analysis ". Is this a field of theoretical computer science? What subjects are related with this ... 1answer 47 views ### Prove that$\log n = O(\log^2 n)$Trying to solve this, but I can't seem to figure it out. Its fairly straight forward. 1answer 29 views ### Why$T(n) = 2T(n-1) + O(1)$is$\Omega(2^n)$? I was told that the complexity of$T(n) = 2T(n-1) + O(1)$is$\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ... 0answers 26 views ### Algorithmic Complexity of Linear Independence Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ... 0answers 38 views ### Prove that (x+1)! is not O(x!) Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ... 1answer 44 views ### Relation of encryption to P, NP, and NP-Complete After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ... 2answers 58 views ### I want to know an estimate of$a_{i, j}$Let $$a_{ij} = \begin{cases} -1, & \text{if i = -1 and j = -1} \\ 1, & \text{if i = -1 and j \ne -1} \\ 1, & \text{if i \ne -1 and j = -1} \\ a_{i-1, j-1} + ... 1answer 61 views ### Do there exist polynomials not computable in polynomial time? Motivation: Computing a problem in k memory slots Do there exist polynomials in R = \Bbb{Z}_p[z_1, \dots, z_k] that can't be computed in time polynomial in k,p? Thanks... Good luck! Edit. I ... 1answer 26 views ### Any problem computable in k memory slots can be computed with polynomials. Let our memory slots be represented by elements of \Bbb{Z}_p for a prime p. k memory slots would be k copies of the ring: R = (\Bbb{Z}_p)^k. Suppose that for a problem f : X \to Y, ... 1answer 31 views ### Is there a way to compute if(i < j) k := (a + b)c with polynomials over \Bbb{Z}_p? Let p be a prime and let all variables be in \Bbb{Z}_p. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial k := ... 0answers 13 views ### Are these computational models equivalent? Let f : X \to Y be a problem that you want to compute. Say we have an O(1)-computable maps, \phi, \psi, such that X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y. After all, ... 1answer 57 views ### Existence of a det. poly-time algo for problem f: X \to Y. f : X \to Y is a deterministic polynomial-time algorithm for problem inputs x \in X and problem outputs f(x) = y \in Y \iff there exists a polynomial P_f \in \Bbb{Z}[x_1] such that C\cdot ... 0answers 29 views ### Can cuts of size 2 be detected in linear time in an undirected, unweighted graph? I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ... 1answer 111 views ### Minimizing Height of a Table This optimization question popped into my mind while working with latex tables: Suppose we have a table with m rows and n columns, and for each 1\le i\le m,1\le j\le n we are given T(i,j) ... 1answer 69 views ### The complexity of counting solutions to x_1 + \dots + x_m = N in non-negative integers under constraints Consider the equation$$x_1 + \dots + x_m = N$$where x_1,\dots,x_m \ge 0 and under the additional constraints x_k \le a_k for k=1,2,\dots,m. I'm interested in knowing whether the number of ... 0answers 26 views ### Why 17T(n/16) + n \log n satisfies the case 2 of the Master Theorem? Using the Master Theorem, we have that 17T(n/16) + n \log n is \theta(n^{log_{16}17} log^2 n) My question is, why n \log n = \theta(n^{\log_{16}17} \log^1 n), being \log_{16}17 approximately ... 0answers 45 views ### How to convert a subgraph isomorphism problem to subset sum problem Let's say you want to solve a subgraph isomorphism problem using a subset sum solver. What would be the right steps to convert SGI to SS? 1answer 60 views ### From programming to mathematics I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let \mathcal P be the main program, and \mathcal P \in O\left(\varphi(n)\right) with ... 2answers 32 views ### Sum of a sum [algorithm design and analysis] I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ... 3answers 45 views ### Help making the distinction between polynomial and exponential time I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = \{\langle G,s,t \rangle | G is a directed ... 1answer 23 views ### What is the sum of recursive logarithms? I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form:$$ O(n \times (\sqrt n)^2 + n \times (\lg \sqrt n)^2 + n \times (\lg \lg \sqrt n)^2 + \space ... + ... 3answers 61 views ### How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number Given: $$X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1}$$ $$z \in \mathbb N$$ Wanted result: $$Y = \left\{ y_1, y_2, \ldots , y_n ... 1answer 81 views ### Calculating run times of programs with asymptotic notation When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ... 1answer 66 views ### A Matrix Optimization Problem Given an n\times d matrix Y, I am looking for an algorithm to find an n-vector \mathbf{v} (0\le \mathbf{v}_i\le 1 for all i) that minimizes \sum_{i:X_i<0}X_i, where X:= \mathbf{v} ... 1answer 84 views ### Efficient Verification for Travelling Salesman Problem Through reading popular mathematical literature, I have learned the following two facts about computational complexity theory: The complexity class NP is the set of problems for which a candidate ... 0answers 72 views ### What is the difference between the Big O and Big O star (asterisk) operator? I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant ... 1answer 38 views ### Calculating algorithmic complexity Given the following bit of code, how would I calculate the complexity? ... 1answer 50 views ### Complexity of factoring non-squarefree numbers Consider the two numbers N_1=p_1\cdot p_2 and N_2=p_1^2\cdot p_2, where p_1 and p_2 are primes. Is there any factoring algorithm that can factor N_2 faster than the asymptotically fastest ... 1answer 28 views ### Adding a point to shortest path If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ... 1answer 28 views ### Correctness of complexity analysis of recursive algorithm Given following recursive equation:$$T(n) = T(n-3) + \Theta(1)$$Is it correct that this equation is O(1)? 1answer 60 views ### Question Understanding Simple Algebra With Regards to Computational Complexity Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ... 3answers 53 views ### Best Sum of Three Elements in a Sequence I encountered the following problem: Given an integer sequence \left(s_1,s_2,\dots,s_n\right) and an integer l, find$$\min\left|s_i+s_j+s_k-l\right|,$$where$i\neq j\neq k\neq i$, and return ... 1answer 48 views ### Union Find Program Prove By Induction Consider the program below for building a union-find data structure. Prove by induction that if the method build_union is called starting with each vertex in a component by itself, that the ... 0answers 86 views ### A question on the computational complexity of Boruvka's algorithm One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ... 1answer 58 views ### Finding missing two edges in a MST in O(m) time I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ... 1answer 58 views ### Do this algorithm terminates? Let$x \in \mathbb{R}^p$denote a$p$dimensional data point (a vector). I have two sets$A = \{x_1, .., x_n\}$and$B = \{x_{n+1}, .., x_{n+m}\}$. So$|A| = n$, and$|B| = m$. Given$k \in ...
Given a trivariate polynomial $A\in\mathbb{R}[x,y,z]$, a direction $\vec v\in\mathbb{R}^3$ and a point $p\in \mathbb{R}^3$, what is the fastest way to compute the directional deriviatives ...