1
vote
1answer
15 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
1
vote
1answer
76 views

What kind of recurrence relations has p < 0?

By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real. I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?
1
vote
0answers
29 views

Cycle of length k with no repeated edges

I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with ...
0
votes
0answers
5 views

Invariant For Nested parallel.for Loop in Matrix Multiplication Program

I m making my semester thesis about proving correctness of program for parallel multiplying 2 matrices using Sequential matrix logic. For doing this, I need to generate the invariant for nested loop ...
0
votes
0answers
12 views

Find a path in a complete graph with cost limit and max reward

I'm looking for an algorithm to solve this problem. I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot ...
0
votes
1answer
9 views

Why we need tagbits when we already have indexbit and offset?

I was watching a lecture and got confused at one point when professor said that to distinguish between two addresses having same values of offset as well as index bit we need tag.Why we need tag ? for ...
2
votes
2answers
36 views

Languages of cardinality higher than $\aleph_0$

I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or ...
-1
votes
0answers
12 views

How to print all the Permutations of array elements in CBMC?

For eg: i have an array, int array={1,2,3}; I need to display all the possible permutations which will be {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1} etc. all n! possibilities. From an Algorithmic ...
0
votes
0answers
13 views

Forbidden Positions for circular arrangements

N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
1
vote
1answer
38 views

Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain ...
1
vote
1answer
11 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
-1
votes
0answers
18 views

Number of nodes to be expanded for DFS, BFS and Iterative-deepening search

I was wondering given depth d and branching factor b and maximum depth m, what would be the minimum and maximum nodes to be expanded for BFS, DFS and iterative-deepening search with cut off d with ...
4
votes
3answers
64 views

Why is the CPU Involved During Keyboard Echo?

I'm currently studying for a computer science exam, and I've come across a concept that has me somewhat stumped. When one types a key on the keyboard, an ASCII character is transmitted to the CPU. ...
0
votes
2answers
42 views

Fast implementation of basic addition algorithm

Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being ...
2
votes
0answers
36 views

Mathematical model for a webpage layout?

Getting layout right (even if only a structure is considered) with HTML5/CSS3 is still more like an art or black magic. On the other hand, there are other GUI systems (like wxWindows and Tcl/Tk) and ...
1
vote
0answers
27 views

Universal algorithm testing framework [on hold]

Currently I'm working on my thesis. I'm writing about subgraph isomorphism problem and various algorithms, solving this problem. One of my task is to integrate that problem in a testing framework, ...
0
votes
1answer
16 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
6
votes
0answers
30 views

Determining the minimum number of edges to add in order to be 3-connected

A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a ...
0
votes
1answer
29 views

Why do heuristic functions only approximate the real value of the cost?

As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?
1
vote
0answers
22 views

Overlap between fields in CS

I hope this isn't too meta. I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, ...
-3
votes
1answer
26 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
0
votes
1answer
16 views

Hamming and BCH codes

Why are Hamming codes the best 1-error-correcting codes? I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?
1
vote
1answer
23 views

Using A* search with different heuristic values

I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length ...
1
vote
2answers
41 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
0
votes
2answers
40 views

How to learn computer science the right way [on hold]

I looked through the sites and this seems to be the best place to ask this question. I am sure it has been asked 10000 times but I am looking for a tailored answer to me and my situation. I currently ...
-1
votes
0answers
32 views

Determine if the following family of hash functions is universal [on hold]

Let $H = \{h_1,h_2,h_3\}$ be the family of hash functions defined below, each mapping $\{a,b,c,d,e\}$ to $\{0,1,2\}$. Is $H$ universal? A family of hash functions is universal if $\forall ...
2
votes
1answer
22 views

Greedy proof: Correctness versus optimality

I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same ...
0
votes
0answers
4 views

Do programmers often use SDLC Methodologies for making a System? [on hold]

My instructor told us that some programmers are not using SDLC Methodologies for making a system. Because in our project, we used one of the methodologies. If we will not use one of them ......may be ...
1
vote
1answer
22 views

Why the analysis of Aloha protocol uses Poisson distribution?

Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial ...
3
votes
1answer
55 views

Knapsack problem is NP-complete - Exact cover

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
4
votes
3answers
715 views

Is order of bits in byte really not of concern?

What I can't wrap my head around is sentence repeated everywhere I look, that order of bits in byte is not important(not of my, as a programmer, concern). My question then is if there is possibility ...
0
votes
1answer
26 views

Understanding Instruction Cycle?

A basic instruction cycle consists of these 5 stages. Instruction Cycle IF - Instruction Fetch RD - Instruction Decode and Register Read EX - Execute MA - Memory Access WB - Write ...
0
votes
1answer
77 views

How can I learn about CS? [on hold]

I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient ...
2
votes
1answer
48 views

The number of maximal independent sets

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that you can not add any vertex. I want to know if the number of all ...
-1
votes
1answer
39 views

Operation with same asymptotic cost on hash tables and lists

Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function. Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?
1
vote
2answers
23 views

Calculating the number of unique BST generatable from n keys, why is my number so large

I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3) Here's my solution: In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3*2*1 = 6 ways ...
4
votes
2answers
78 views

Do all greedy algorithm produce just the first solution, no matter how bad it is?

In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the ...
4
votes
1answer
228 views

Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property: For any cycle C in the graph, if the weight of an edge e of C is larger than the ...
3
votes
0answers
52 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
0
votes
2answers
76 views

What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ [duplicate]

What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$ I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be ...
1
vote
1answer
20 views

Are all languages generate by Turing machines countable?

Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
0
votes
1answer
14 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in ...
2
votes
1answer
41 views

Time complexity of solving a set of 2-sat instances?

Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?
1
vote
1answer
70 views

Are all adjacency matrices represented by 0 and 1s?

Are there any cases when adjacency matrix should have entries other than 0 and 1?
1
vote
0answers
15 views

What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements. Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
3
votes
0answers
31 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
1
vote
2answers
23 views

Does amortized complexity always equal to worst case complexity divided by n?

Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n? I'm confused because this statement is so simple and ...
1
vote
0answers
17 views

Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). ...
2
votes
1answer
16 views

Measure two qubits, one from entangled pair, in Bell basis?

In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta_{00}\rangle$ Sell state. Then, if Alice wants to teleport a quibt ...
1
vote
1answer
20 views

The significance of bounded parameters in complexity

A lot of complexity results are given with respect to bounded cases where results are more favourable. For example, the graph isomorphism problem — which is GI-complete in general — is known to be ...

15 30 50 per page