# All Questions

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 ...
2 views

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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ***. ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
22 views

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

When I was preparing for entrance exam this question arised.
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?
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). ...
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 ...
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 ...
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, ...
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 ...
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 ...
19 views

### Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
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?
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
### 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 ...
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?