# All Questions

29,195 questions
45 views

### Type system and language that implements type constraints?

Occasionally when writing programs in a statically typed language, e.g. some ML, I find having to write code for cases I know will not happen. This is because I know e.g. that a function on some data-...
21 views

### Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
70 views

### Is the language of words that contain a square regular or context-free? [duplicate]

$L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
23 views

### How would be a query where its operators are NOT worth to execute in parallel?

I would like to have an example of a query for database or a dataflow program in spark (or any stream processing system) that is not worth to parallelize at least one of its operators. The insigth ...
110 views

### Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help. $A$ is an $n$ items array from an ordered set, in which every item is at most $\log n$ indices away from its position in the ...
12 views

### College project using Microservice architecture for an Android app and Website [closed]

How can I build a website and an android app for a complaint system using microservices architecture for my college project? I want to use java spring boot and AWS. What other technologies and ...
13 views

### FXGL gradle issues: unable to derive module descriptor for Kotlin-reflect [closed]

I'm trying to get working with FXGL in Eclipse, but right away nothing will run for me at all. The project is made with gradle. In my build.gradle I have added compile 'com.github.almasb:fxgl:0.5.4' ...
139 views

### Need for Speed: Parallelism [closed]

Parallelism sometimes called parallel execution divides a task among multiple processes so that instead of doing all the work by one process in a query, many processes perform part of the work at the ...
21 views

31 views

### Find a minimum-weight perfect b-matching, where b is even

How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b? A minimum-weight perfect b-...
19 views

### Converting (reverse-engineering) Turing machine into program or most concise algorithm?

It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to ...
36 views

### How to find the definition of Computer Architecture terms in Compter Science? [closed]

To find the meaning of computer architecture terms in Computer Science do I need to use a Computer Science book? Do I need to find the computer architecture terms in a Computer Science Dictionary or ...
26 views

### Find a minimum-weight perfect 2-matching

How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V? A minimum-weight perfect 2-matching of a graph G is a ...
64 views

### Is Language $L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b}$ and $|w|_{b} \not\equiv |w|_{c} \}$ context free?

$L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b}$ and $|w|_{b} \not\equiv |w|_{c} \}$ I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
21 views

### How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

The theorem states that $$H(P)\leq\mathrm{MinACL}(P)<H(P)+1$$ where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word ...
29 views

### What is a location in Random Acess Memory [duplicate]

I tried going on an English dictionary in google called dictionary.com to find the definition of Location in RAM. I really do not understand the definition of the word location. Tell me which English ...
33 views

### Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$?

I am reading Introduction to Algorithm CLRS (3rd ed.), Chapter 4 (Divide and Conquer), page 78, and am not sure why the explanation of why SQUARE-MATRIX-RECURSIVE algorithm takes $Θ(n^3)$. ...
46 views

### Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
47 views

### State-elimination on FSA, after epsilon-removal construction

I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression. But there are already some epsilon ...
26 views

### Determining whether Turing machine halts on input: primitive recursive?

In Elements of the Theory of Computation by Lewis and Papadimitriou, the authors use a specific function for proving that application of unbounded minimization on a primitive recursive function need ...
77 views

### Doubt over the index value used in dynamic programming

I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string. After seeing the brute force(recursive solution), I went ...
26 views

### In what complexity class is the problem of checking whether two NFA states are equivalent? [closed]

That is, check if two NFA states accept the same language?
14 views

### Trouble understanding theory for error detection and correction in repetition code

Question 1 Consider a repetition code to detect $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always ...
37 views

### Maximum matching using linear programming

In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
40 views

### How to evaluate dynamical conditioning/pseudo code

I am having a hard time even to formulate my question, so here it is: I have an application that the user can go in and define on a webpage the logic one wants to evaluate for the student to comply ...
26 views

52 views

### Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal. I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
32 views

### Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
28 views

### Proving existence results

I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties: (i) For all x ∈ A, |x| ≤ 5. (ii) Every DFA that decides A has more than 8 states....
85 views

39 views

### List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
36 views

### How fast can all nth roots of an integer be computed?

I mean that for every $i$ from 2 to $\lceil \log_2n\rceil$ I want to know $\lfloor \sqrt[i]{n}\rfloor$. Could this be done faster than computing the roots one by one?
37 views

### Solve the recurrence relation T(n)=3T(√n)+lg(n) [duplicate]

Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem. So, how I will find Θ of T(n)?
18 views

### Inverse kinematics step

I am working on an implementation of inverse kinematics using the jacobian transpose method. The implementation seems to be working as it does find the "theta" vector, although sometimes it might take ...
37 views

### How to efficiently specify a MILP constraint with nested AND and ORs

Let's say I want to set x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0 All of the xs are binary ...
19 views

### NPDA transitions to different states by taking same input and popping same top element of a stack

Suppose i have some NPDA and there is some transition functions defined as: $\delta(q_{1},a,A) = (q_{2}, A)$ $\delta(q_{1},a,A) = (q_{3}, Z)$ Is it allowed? I understand, that since the NPDA is ...