All Questions

4
votes
1answer
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-...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
-2
votes
0answers
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 ...
0
votes
0answers
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' ...
-4
votes
0answers
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 ...
2
votes
1answer
21 views

Is $T(n^2) = Ω(n)$?

According to this link: We need the notation for the lower bound. A capital omega $\Omega$ notation is used in this case. We say that $f(n) = \Omega(g(n))$ when there exist constant $c$ that $...
2
votes
1answer
28 views

Is it possible for a network to have a negative cycle that is not found by the Bellman–Ford algorithm?

I'm struggling to think of such a network. According to the definition I'm working with: Given a network $(V, A, w)$. For all arcs $(u, v) \in A$ : $\quad$ If $d[u, |V| - 1] + w(u, v) <...
2
votes
1answer
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-...
1
vote
0answers
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 ...
-2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
-3
votes
0answers
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 ...
1
vote
2answers
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)$. ...
2
votes
1answer
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, ....
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
-3
votes
0answers
26 views
1
vote
1answer
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
26 views

Algorithm for the following graph transformation

Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$: For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$ For every $(...
1
vote
0answers
20 views

Is the preprocessing process using the tfidf vectorizer really useful for model learning?

I am a student who is studying machine running alone. As far as I know, the Tf-idf Vectorizer is a function that combines the Count Vectorizer and the Tf-idf Transformer. I was wondering if the Tf-idf ...
0
votes
0answers
18 views

Winnow2 Algorithm

In the Winnow2 Algorithm, how is the alpha value obtained? I have found a handful of papers and sources (included below), but none explicitly call out how to decide on the alpha value... http://www....
1
vote
1answer
31 views

Uniformly random iteration of subtrees

I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $...
2
votes
2answers
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, ...
2
votes
2answers
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 ...
1
vote
1answer
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....
0
votes
1answer
85 views

Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's

The following question on the theory of computation is GATE 2019 CS question 24: For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
1
vote
0answers
38 views

Address of the Last Byte of Installed Memory

I'm a university student currently taking an Assembly and Computer Organization class. On last weeks lab we were given a question: Suppose that you buy a 32bit PC with 16 MB of Ram. What is the 8-hex-...
0
votes
2answers
79 views

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
3
votes
2answers
82 views

How to prove the equivalence of two CFG for balanced parentheses?

Given two CFGs for balanced parentheses. $S \rightarrow SS \mid (S) \mid \epsilon$ $S \rightarrow S(S)S \mid \epsilon$ How do I show that they are equivalent? I have been able to show $ L(2) \...
1
vote
0answers
45 views

Finding the best state for chain graph with cycles

I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
2
votes
1answer
40 views

2-opt vs 3-opt comparison

I have a question regarding performance of 2-opt and 3-opt algorithms. I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%. ...
0
votes
0answers
28 views

topology representation through graph [closed]

Is there any way to represent indoor topology of a house through graphs or trees and calculate similarity or dissimilarity between them?
1
vote
1answer
24 views

Learning a perceptron from stream data

I want to train a Perceptron using stochastic gradient rulefrom the stream data. I have very limited amount of memory and i can store only $N$ examples. Suppose my population consist of point as ...
3
votes
2answers
104 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
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 ...
0
votes
1answer
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?
1
vote
1answer
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)?
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
48 views

Successive shortest path without reduced costs

The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows : Successive shortest path (for minimum-cost flow) : while all flow is not ...
1
vote
2answers
46 views

Pseudo Code optimization

Summary: I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip. Detail So far I have written following: What I do not like ...

15 30 50 per page