All Questions
0
votes
0answers
1 view
how is computer capable of logicizing by using electricity and logic gates?
how is computer capable of performing logical operations?
All that i know is that electricity passes through some logic gates with specific sequence in order to execute a specific instruction. But how ...
3
votes
0answers
11 views
Breadth-first forest
I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, constructs a forest in DFS that includes all the nodes, whereas BFS only constructs a ...
1
vote
1answer
14 views
Total number of bits of storage for direct mapped cache
I have a homework assignment dealing with caches. We are asked to compute the total number of bits of storage required for the cache, including tags and valid bits. Then compute the overhead for the ...
0
votes
0answers
11 views
Determine what is the best order for running tasks
I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.
Assuming I got the tasks t1, t2, t3, ..., ti and a dataset. Each task have an execution time denoted ...
0
votes
0answers
13 views
Edge incident to cut-vertex not in perfect matching of a graph
Let G = (V,E) be a connected graph and a ∈ V be an articulation point of G. How can be proved that there is an edge e ∈ G incident with a with the property that e doesn't belong to a perfect matching ...
0
votes
0answers
11 views
How is parameter tuning done in real-world problems with very long run times?
I have a GA code that takes a very long time to converge(like 3-4 days), I want to know what is the best parameter tuning method for it?
I simply want to just tune population size, crossover and ...
2
votes
1answer
18 views
Random Walk on the Integer Line
Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next ...
0
votes
0answers
18 views
Running time of sparse matrix multiplication
Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
0
votes
0answers
12 views
Detect cycle in a directed graph - like undirected graph?
I know how to find a cycle in undirected graph by DFS: after the DFS finished if we find a back edge on the graph, we know that the graph have a cycle.
I wanted to know if I can do the same algorithm ...
4
votes
1answer
16 views
Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?
In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $...
0
votes
2answers
31 views
What is the Big O time complexity of this algorithm?
We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I ...
0
votes
0answers
25 views
Edge not in a perfect matching of a connected graph [on hold]
Let $G = (V,E)$ be a connected graph and $v_0 \in V$ be an articulation point of $G$ ("cut-vertex" : $G - v_0$ is not connected). Prove that there is an edge $e_0 \in G$ incident with $v_0$ with the ...
0
votes
0answers
21 views
How to optimise f(X) such that sum(X) = 1 using genetic algorithms [on hold]
I want to find the global minimum of $f(X)$ and I'm using real-valued GAs. The vector $X \in [0,1]^3$ has the constraint that $x_1 + x_2 + x_3 = 1$.
Currently, each $x_i$ is allowed to assume any ...
-2
votes
0answers
46 views
base change of n
Given some integer $N$, how many bases $b$ are there such that the base-$b$ representation of $N$ starts with a $1$? Ex.: $6$ has a leading digit $1$ in bases $2$, $4$, $5$ and $6$: $6_{10} = 110_2 = ...
1
vote
0answers
29 views
Time complexity ( $\Theta$ ) of function [duplicate]
Let f be the function with one argument - positive integer n
...
1
vote
0answers
17 views
Connected components at most n/2 problem
Let $G$=$(V,E)$ with $V=$ {$1,2,...n$} and $E$ = {$e_1$,$e_2$,...$e_m$}. On the set of edges we have a cost function $c : E → R$, with a property like if i $\neq$ j then c($e_i$) $\neq$ c($e_j$).
We ...
0
votes
0answers
11 views
Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)?
What are the exact assumptions behind the use of UPGMA? Can I use a non-Euclidean metric? This may result in a non-Euclidean distance matrix. What kind of bias may I encounter if I do so? References ...
-1
votes
0answers
19 views
How to make finite automaton for this language? [duplicate]
Consider the language
$$ L = \{0^p 1^q 0^p | p, q ≥ 0\}. $$
How to make a finite automaton for $L$? How to make a regular expression for $L$?
0
votes
1answer
29 views
Algorithm : Select maximum number of Boxes to lift from N boxes
There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to ...
2
votes
0answers
30 views
How to merge all 3-grams into smallest possible string?
There is a set of all possible letters: $A = \{ a, b, \ldots, z \}.$
Then the set of all possible 3-grams looks like that:
$A^3 = A \times A \times A = $
$\{$
$\;\;(a, a, a), $
$\;\;(a, a, b), $
$\;\;(...
-2
votes
0answers
14 views
What are the best books for learning C-advance and Java-Advance? [on hold]
Can anybody tell me all about the learning path about java-web concepts and c-language advance concepts and more about relates online courses and tutorials.
2
votes
1answer
18 views
How does universal calculator work?
As I understand, the concept 'computation' started dependent on hardware (like looms for instance).
The Hardware defines (physical cascades) what happens between input and output.
I think I saw in ...
0
votes
0answers
13 views
Equivalent formulas in LTL and removing/swapping out negation and distribution of until [on hold]
Given Theorem 13.31
$$
\models \square p → \lozenge p,\\
\models \circ p → \lozenge p,\\
\models \square p →\lozenge p,\\
\models p ↔\lnot \circ p\lnot \\
$$
And using the rules:
$$ \lozenge p ↔ ...
2
votes
1answer
60 views
There are n numbers. Find the maximal set of pairwise NON coprime numbers
I have to take input in an array(no. of elements in array <=10^5).
For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in ...
-3
votes
0answers
19 views
Multi tape Turing Machine
I need help in creating multi-tape Turing machine for the following language. {0^n1^n:n≥1}.
Any help would be appreciated.
Thanks!
5
votes
3answers
475 views
Lambda calculus didn't seem abstract. And I can't see the point of it
The underlying question: What does lambda calculus do for us that we can't do with the basic function properties and notation generally learned in middle school algebra?
First of all, what does ...
-1
votes
2answers
26 views
I/O bound processes over CPU bound processes
will an OS which favors I/O bound processes over CPU-Bound processes, experience less average waiting time? If yes, why?
4
votes
1answer
41 views
Definition of integers needs explaining
Zero and one are defined by the successor function.
$$
\begin{align*}
&0 ≡ λsz.z \\
&1 ≡ λsz.s(z)
\end{align*}
$$
But why? $λsz.z$ is irreducible to a value. If I call this function on some ...
4
votes
1answer
20 views
what is weak extensionality in $\lambda$-calculus?
I was reading the book lambda calculi , encountered an equality theory called "the rule of weak extensionality", which is shown as follows.
$\frac{M \, = \, N}{\lambda x.M \, = \, \lambda x.N}$
Yes,...
0
votes
1answer
27 views
NP-completeness of the exact distance problem
I am currently learning about NP-complete problems and I want to make sure my understanding is correct.
Here is a problem I am working on currently:
The exact distance problem is, given an edge-...
0
votes
0answers
7 views
What's the accuracy difference between the two versions gradient calculation? [migrated]
The following is Python code aiming to calculate the gradient of a given function f.
Version one (Solution)
...
3
votes
1answer
65 views
Is Graph 2-Coloring NP-Complete?
I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"?
Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete ...
-1
votes
0answers
26 views
Online scientific books [on hold]
i want to tell me if you could ofcourse where to find online books for computers.Ι care about theory only.I need to write the bibliography from books some definition and etc on my notes.Example,I want ...
0
votes
1answer
28 views
Reducing “multiple satisfiability” to normal SAT
I have to prove the NP-completeness of the following set:
QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}
My idea so far has been to reduce the problem to the normal ...
3
votes
1answer
37 views
Contingent sentences can always be true
I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions.
In a textbook I read that a sentence might always be ...
0
votes
0answers
28 views
Where to begin in studying computer science [duplicate]
As a young teenager, I don't have many options in going about learning computer science. I love working with computers, I'm experienced in a few programming languages and I'm doing a lot of studying ...
0
votes
0answers
14 views
Threads and Threading Library Type for General Purpose Operating System
suppose, for example, if you are designing a general purpose operating system for a common desktop user, which type of threads and threading library will you choose in your operating system ?
0
votes
0answers
22 views
Algorithm: Longest Increasing Subsequence in a subsection of an array
For an array size of $N$, I have to find longest Increasing Subsequence $T$ times between $T$ different values of $l$ and $r$ that are the starting point and ending point for which the sequence is to ...
1
vote
1answer
45 views
Determine whether a TM visits each of its states exactly once during computation
(Decidable or not?) Formulate the following problem as a language:
Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation ...
1
vote
0answers
25 views
Undecidable language problems [migrated]
Let $L_1$ and $L_2$ be two undecidable languages.
1) Is it possible that $L_1 - L_2$ is regular and $L_1 - L_2 \neq \emptyset$ ?
Well I know that if I let $L_1 = L_2$ then $L_1 - L_2 = \emptyset$ ...
0
votes
0answers
28 views
Kernel level or user level threading library? [on hold]
How can you check that the threading library you are using uses kernel level threads or user level thread?
0
votes
0answers
13 views
What is an Information system and how to use it on my subject [on hold]
Hello everyone its my first time here.I am not having knowledges from computer.I would like to tell me that i have many questions about information system.I have search on internet and find many ...
1
vote
1answer
42 views
does cpu time reflect BigO time complexity
QUESTION
does CPU time reflect Big O time complexity?
WHAT I MADE
I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative ...
3
votes
1answer
54 views
On computing the factor-free basis of a regular language
The problem is as follows.
Background: Given an alphabet $\varSigma$. If $u,v,w,x \in \varSigma^*$ and $w=uxv$ then $x$ is a factor (substring or infix) of $w$. A language $L$ is factor-free if, for ...
5
votes
1answer
45 views
Can we express the program to find last element of a list as a catamorphism?
So I've got a bit of category theory under my belt, and I am reading a few papers about calculating functional programs. I've expressed programs like summing a list as a catamorphism, and I've fused ...
0
votes
1answer
34 views
Two labelled transition systems feeding each other
Assume we have two LTSs, say DFA with labels over the transitions (though the question can be generalized to more sophisticated automatons), define the input to each system to be as usual just the ...
2
votes
1answer
67 views
PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it
I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$:
$$
\begin{align*}
&S→AB∣BA \\
&A→a∣aAa∣aAb∣bAa∣bAb \\
&B→b∣aBa∣aBb∣bBa∣bBb
\end{align*}
$$
I ...
1
vote
0answers
52 views
Correctness of Dijkstra's algorithm
This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).
The proof makes a case that considering path $...
0
votes
0answers
29 views
What Are Some Ethical Issues in Computer Science? [on hold]
So far, forms of engineering have very specific ethical guidelines and professional organization. But since most software is decidedly not engineering in this sense, this model doesn't make sense for ...
2
votes
2answers
59 views
Proof that the language $ww^R$ is not regular without using the pumping lemma
I am breaking my head over this. Let the alphabet $A$ be given by
$A = \{a,b,c\}$ and let
$$L = \{ww^R \mid w \in A^* \}.$$
Prove that the language $L$ is not regular without using the pumping ...
