# All Questions

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 ...
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$?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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, ...
16 views

### What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
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 ...
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?
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, ...
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 ...
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?
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 ...
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 ...
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 ...