All Questions

2
votes
1answer
17 views

Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...
2
votes
1answer
42 views

Construct a DFA from the regular expression (a)*+(aab)*

I've broken down the expression into two simpler DFAs but right now I'm stuck. I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
0
votes
1answer
27 views

Speed Up Access to Fractal-Like Array

I'm trying to speed up the following function in c++: ...
4
votes
0answers
36 views

Algorithm for Unique Selections

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set. A selection is unique if there's one and only one way it can happen—that is, one and only one ...
2
votes
0answers
21 views

Algorithm to select elements from a ranked list of lists

I have a list of lists of objects. Each of the lists of objects is ranked according to a numeric field of the object. The big list is ranked according to the highest numeric value of the field of all ...
2
votes
1answer
23 views

Minimize sequence storage by overlapping prefixes

I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
1
vote
1answer
27 views

Recognizably turing machine question (reject / loop)

The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way? Give a deterministic TM D that recognizes L such that ...
2
votes
1answer
28 views

Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?
0
votes
0answers
21 views

Translating java code into mathematics expression/formulas [closed]

I would like to convert my Java code into mathematics expressions/formulas and algorithm pseudocodes, just like ones in computer science research papers. Is there any tool does that (e.g. Eclipse ...
0
votes
0answers
15 views

Cat Dog classifier in tensorflow, fundamental problem! [closed]

I am trying to build an image classifier for a set of images containing cats and dogs. I am very new to the dark art of creating Neural Network models. I have had success building models with Keras in ...
3
votes
1answer
25 views

Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows: "On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to ...
2
votes
2answers
16 views

Confused about 3rd rule of CFG pumping lemma

Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL) Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the ...
2
votes
1answer
55 views

Conditions for a binary tree being balanced

Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced. If you disprove, the counterexample should consist of an infinite ...
1
vote
0answers
9 views

Approximate Matching - two plane geometries with n points

I'm trying to do approximate matching of one plane geometry with n points to a big set of other plane geometries. The aim is to get the closest shape (rotation and scale agnostic) My idea would be to ...
0
votes
0answers
17 views

Is using British accent dataset helpful while training American speech recognition? [closed]

I'm training a robust speech recognition system with as much data as possible. The target recognition speech will be American English, but I found some free British English datasets also. Now the ...
2
votes
1answer
27 views

Does Google's PageRank count as a sorting algorithm?

Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?
0
votes
0answers
21 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
2
votes
1answer
22 views

Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
2
votes
1answer
12 views

Proving a language comprised of 2 languages is regular(with suffix and prefix)

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular: $$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
1
vote
1answer
43 views

How does dynamic memory-allocation exactly work?

I have wondered about profane code. Assume we are running this code on any modern System like Unix/Linux/Mac/Windows. This code is C, but it should work with every language which is close to the ...
0
votes
0answers
12 views

When to choose each machine learning method? [closed]

I am currently taking a machine learning course , and I am having a difficulty to decide when should I use neural network, and when to use random forest, and why?
0
votes
1answer
43 views

Advantages of Lambda calculus over Turing machine and vice versa [closed]

What kind of advantages does Lambda calculus have over Turing machine, and vice versa?
5
votes
1answer
228 views

Data structure for selection of K elements and taking sum

The problem: We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ ...
4
votes
1answer
28 views

How to construct an ordinary matching from a fractional matching?

Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $. My question ...
0
votes
0answers
16 views

How to solve Hoare's problem when precondition contains meta symbols?

This is the proram for which I have to prove correctness using Hoare's Axioms: {X = |x|} if(x<=0) x:=-x; else skip; {X=x} This is my solution so ...
4
votes
1answer
17 views

Proving a language comprised of 2 languages is regular

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it. The question: $L_1$ and $L_2$ are regular languages over the ...
3
votes
1answer
33 views

Quantum vs classic in NP-hard problems

Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
0
votes
1answer
13 views

Using python function in c++ [closed]

I have written a function in python, but I want to use it in c++. It is a function that does some image processing and returns a vector back. I want to use this function in an Arduino project. How do ...
1
vote
0answers
14 views

Randomized Quick Selects' time complexity dependence on k - the index to be selected

I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected. The time complexity dependence on n ...
0
votes
0answers
25 views

Choosing algorithms and/or data structures at runtime based on input characteristics

I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
2
votes
1answer
124 views

Algorithm for fewest number of moves with artificial minimum

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum. To summarize, I built an undirected graph with edges ...
2
votes
1answer
20 views

NL-Hardness of Target

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve: $ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
1
vote
0answers
16 views

What's the difference between Acfg and ALLcfg

In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
5
votes
1answer
45 views

Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How ...
1
vote
0answers
19 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
1answer
78 views

Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
0
votes
0answers
14 views

Multiple inputs for the same parameter [closed]

I would like to know what are my options for handling multiple inputs for the same field from a different user. I guess that is a BigData\probablity&statistics question. A link to read on such ...
-1
votes
0answers
27 views

Is it possible to do forward-chaining in Prolog?

Prolog (or any logic programming system) actually acts as SAT solver, that returns the valid values for the variables that are mentioned in the query. It can also be used as theorem prover if one does ...
0
votes
0answers
24 views

Analysis of Basic Recursive Functions

I'm trying to understand the contrast between run-time for this function ...
1
vote
0answers
23 views

How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
1
vote
0answers
35 views

Is it possible to write a fully-decidable type system for the J language?

I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL). It is unclear to me whether ...
0
votes
0answers
13 views

Analysing data from amazon textract - python [closed]

I am creating a piece of software for my company where I need to check the math on invoices we receive from companies. The pdf invoices vary from 20-100 pages. The invoice we receive from each company ...
1
vote
0answers
8 views

About logarithmic cost model and bit complexity model?

So I heard that there are such models for finding time complexity of an algorithm as logarithmic cost model and bit complexity model. But from the information I have found in the internet, I cannot ...
-1
votes
0answers
16 views

Is multi-theory approach the only way to do “higher-order” logic programming?

Lets consider logic program: likes(John, Vincent) loves(John, Ann) lusts(John, Tom) is_good(likes) is_good(loves) ~is_good(lusts) This program has 6 statements, ...
3
votes
1answer
64 views

Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges. Because the HC has an extra edge we could say that in general, the weight of every ...
1
vote
0answers
12 views

Log-space reduction from $USTCON$

Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
1
vote
1answer
99 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
-1
votes
0answers
35 views

Are all uncomputable problems, undecidable?

Is there a proof that shows that: "A problem is uncomputable iff it is undecidable"?
1
vote
1answer
19 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
1
vote
0answers
31 views

Design considerations of datatypes in early programming languages like C

Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very ...

15 30 50 per page