0
votes
0answers
2 views

Examples of decidable/undecidable languages

I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples. What are some examples of a decidable language? Of an undecidable ...
0
votes
0answers
2 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = ...
0
votes
0answers
3 views

If graph isomorphism yields a polynomial time algorihtm

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
1
vote
0answers
12 views

A coding question

We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus ...
0
votes
0answers
4 views

number of balanced binary trees [duplicate]

How you can find the number of balanced binary tree knowing only the number of nodes? Is there a method better than generate all possible balanced trees and if not how can i generate those trees based ...
1
vote
1answer
7 views

Greedy algorithm for submodular optimzation

In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to ...
1
vote
0answers
4 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
0
votes
0answers
12 views

Is function application actually a memory manipulation algorithm?

I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually ...
0
votes
0answers
6 views

Raspberry-pi2 connection problem

When I try to connect my raspberry pi to my laptop via Ethernet, it is not assigning any dynamic IP to my laptop(windows 10) though my laptop is set to obtain dynamic IP. I didn't even make the IP ...
-1
votes
0answers
15 views

Why CPU needs to be cooled?

CPUs are made of Silicon and conductivity of Silicon increase with temperature, so why there is a need of cooling CPUs.
0
votes
0answers
8 views

How to determine agreement between two sentences?

A common Natural Language Processing (NLP) task is to determine semantic similarity between two sentences. Has the question of agreement/disagreement between two sentences been covered in NLP or other ...
0
votes
0answers
5 views

Which languages (apart from the list below) can do Howard Curry type checking at compile-time?

The Howard-Curry correspondence is enormously powerful. I'd like to use it, but I'd like a choice other than Haskell and Scala. The languages that I can see that support the Howard-Curry ...
0
votes
0answers
16 views

How to calculate virtual address space from page size, virtual address size and page table entry size?

I try to solve an exercise, unfortunately without any success yet. From the following given information, the virtual address space should be calculated: Page size is 16 KB Logical address size is ...
3
votes
2answers
65 views

About randomness and minmax algorithm with alpha beta pruning

Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order? Here's the pseudocode with my addition marked with ***. ...
2
votes
1answer
14 views

Winning strategy of Nim game when picking from multiple piles is allowed

I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in ...
0
votes
1answer
34 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
-1
votes
0answers
19 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
1
vote
1answer
79 views

Why IS is not in NL, only in NP?

All we need to do is guess $k$ vertices. We look at vertex $v_1$, and make sure $v_1$ is not connected to $v_2...v_k$. Then, we "throw" $v_1$, and look at $v_2$. We do this to all vertices. Meaning ...
0
votes
0answers
26 views

2-thread consensus impl. with single FIFO queue and atomic read/write registers

I need to implement a 2-thread consensus with a single, initially empty FIFO queue and atomic read/write registers. If deq() is called when the queue is empty, then a special EMPTY token is ...
1
vote
0answers
16 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
3
votes
1answer
34 views

Where Can I Find DFA Practice?

Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so ...
2
votes
0answers
11 views

How does a recurrent connection in a neural network work?

I am reading a very interesting paper on genetic algorithms which define neural networks. I am familiar with how a feedforward neural network operates, but then I came across this: Where node #4 ...
1
vote
1answer
13 views

Algorithm to convert rendered number back into symbolic form

If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools: 1- ISC 2- wolframalpha and the answer is $\sqrt2+\sqrt3$ I am ...
0
votes
0answers
15 views

IS $L=QMA$ an open problem?

Having read several chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions: ...
1
vote
2answers
21 views

Hough transform: difference in cartesian to polar equation

According to Wikipedia and most other resources on the internet, the relation between cartesian coordinate and polar coordinate parameters are described by the equation ...
1
vote
1answer
19 views

TSP Edge Removal

Are there any papers/algorithms for finding edges in a graph that can be removed with affecting the graph's optimal TSP tour length? For instance, in a Euclidean TSP instance, many edges could be ...
2
votes
0answers
9 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
0
votes
1answer
11 views

Using Headpose Vector and 2D Points to Compute Distances

I have a frame taken from a video. The frame contains a face and I have the (x, y) locations of the features (corners of lips, edge of eyebrows, etc.) and the headpose vector (pitch, yaw, roll), which ...
0
votes
1answer
21 views

The range of significance in Type Theory

What exactly does "Types as ranges of significance of propositional functions. In modern 
terminology, types are domains of predicates" mean? I understand that because of the Curry-Howard ...
5
votes
0answers
47 views

Origin of the concept of types

About the state of art that I'm running ahead of Type Theory I have the these question all related between them. Where did the idea of type come from? (It seems that all start when Russell and ...
-3
votes
0answers
22 views

Maximum data rate of a channel for noiseless 3KHz binary channel is?

When I was preparing for entrance exam this question arised.
0
votes
0answers
36 views

How many more edges can be added to a graph while keeping it acyclic? [migrated]

If I have a connected, directed graph with n vertices and m edges, is there some sort of formula that describes how many more edges can be added to the graph while keeping it acyclic?
0
votes
0answers
17 views

Flocking Algorithm Problem [on hold]

I'm currently in the process of implementing the cohesion method of the Craig Reynolds Flocking algorithms, but have encountered a problem i just cannot understand (I'm super new to Java btw xD). ...
0
votes
1answer
28 views

Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
1
vote
0answers
16 views

Using consensus for atomic commits

I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus ...
-2
votes
1answer
27 views

NFA with epsilon transition

I need to understand the epsilon transition for NFA, for example I have an NFA with four states q0, q1, ...
10
votes
3answers
764 views

Can any finite problem be in NP-Complete?

My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ...
-1
votes
0answers
39 views

Develop a dynamic programming approach for the generation of a minimum spanning tree T

I have the following problem: Develop a dynamic programming approach for the generation of a minimum spanning tree T of a connected undirected graph G = (V, E). Describe the algorithmic ...
2
votes
1answer
19 views

Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
-3
votes
0answers
29 views

Backtracking algorithm applications [on hold]

What are some of the core computer science applications that can be implemented using backtracking? In which scenario is backtracking essential?
2
votes
0answers
13 views

In instruction pipelining, can we forward an operand more than one clock cycle?

Most operand forwarding examples that use the standard 5-stage MIPS pipeline forward operands from EX or MEM by ONE clock cyle to a later instruction. Is it possible to do so for more than one (from ...
-1
votes
0answers
19 views

What are the most useful subjects in Information Science and Engineering to study Machine Learning? [on hold]

I am doing engineering in INFORMATION SCIENCE and i am very much eager to learn more about machine and its internal working. Thank you
0
votes
2answers
29 views

get time slots available in any of workshop

I have a list of Workshops, each having open_days (Monday, Tuesday etc.) and open_time and close_time (which will be same for each day). Now, Based on the current time, I need to find out next 7 days ...
4
votes
2answers
50 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
4
votes
2answers
45 views

Lambda Calculus inductive substitution definition

I'm reading Lambda-Calculus and Combinators: An Introduction, and there's the following definition of $\lambda$-substitution: $FV(P)$ stands for the set containing all free-variables from $P$. I ...
0
votes
0answers
14 views

Construct a semi decidable but not decidable set using the diagonal argument

Not using anything other than the definition of SD and D I know if A is SD, then there exists a TM M such that A = L(M), and A can be enumerated, and if A is decidable, then everything in A can be ...
-1
votes
0answers
16 views

can we have a virtual destructor in a class? [on hold]

what are different uses of virtual constructor and virtual destructor in a class? can virual constructor or virtual destructor to be u/sed in class?destructor cannot return any value.Are they ...
-3
votes
0answers
15 views

Oracle Database [on hold]

n an Oracle database with standard configuration, if transaction T1 is reading a row of data, and transaction T2 wants to read the entire table (the table that includes the row T1 is reading), T2 ...
2
votes
1answer
12 views

minimize $l_1$ distance between vectors

Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal. In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$. How ...
-1
votes
1answer
21 views

On intersection of classes [on hold]

Consider classes $\mathcal C_1$ and $\mathcal C_2$ of problems both of which are $\mathsf{NP}$-complete. Does it mean $\mathcal C_1\cap\mathcal C_2$ of problems is $\mathsf{NP}$-complete?

15 30 50 per page