All Questions

In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41: Insertion into a full array can be handled by resizing, i.e., allocating a new array with ...

I was reading that circular array is fit for queue with few elements but not sure about if it also uses the least space.

I recently tried the maximum subarray problem on Hackerrank. I tried to come up with an O(n) algorithm. When I submitted my answer, 4 of the 5 test cases get correct answers, but 1 test case fails. I ...

I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions: $$LEM \equiv \prod_{A : Type} \neg A \vee A$$ $$DNE \equiv \prod_{A : Type} \neg \...

We think that non-deterministic machines are more powerful than deterministic machines, by giving an oracle access to $P\subseteq L\subseteq NP$, it seems reasonable to expect there's some $L$ that is ...

Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)? Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...

The Von Neumann architecture was first created in the mid 40s for use in a computing system known as ENIAC for research into the feasibility of thermonuclear weapons. To this day the Von Neumann ...

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem. My understanding is that we have to perform a reduction from Hamiltonian Path-...

What does the following sentence mean? "The 8085 micropressor has the capability of addressing 64KB of RAM?" In general, what is the meaning of a CPU's ability to address a given amount of memory? ...

Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind? For example, say I have DFA ...

When the compiler for, say, Python, reads the source code, what does it translate the object to in memory? If you have an object with a bunch of internal constants attached, do those get copied every ...

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?

I am pretty new to this, consider the following algorithm: ...

Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$? I am really stuck and I tend to believe it's true, but I don't know how to prove it. Any help would be appreciated!

I'm trying to learn computer science by doing some challenges. One is the following. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. ...

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...

As far as I know, all contemporary electronic computers, or even the future quantum computers, follow the Turing machine model in the essence. But it seems none of them can achieve the computational ...

I know that the CPU has a program counter which takes instructions that are required to execute a program, from the memory, one by one. I also know that once the first instruction is executed, the ...

Suppose I have modeled the behavior of my system by Deterministic Finite Automaton (DFA) A, and I need to check if it satisfies a safety condition. I have created another DFA S, which represents the ...

How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?

I have multiple cameras that records the 2D pixel coordinates of the features each camera sees. After some searching, I came across this paper with a method to calculate the 3D coordinates of the ...

This question has two parts. On the other hand I'd like to get a clarification what kind of theoretical and logical framework is required to implement a system that has propositional and predicate ...

This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data. The way it does it is to first map the stream of data to a space that almost ...

We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...

The problem I'm facing is how do I know whether the mapping is "1-way set associative", "2-way set associative", "4- way set associative", etc. Please help!

In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link. On page number 5. please describe this line If the original string $S$ is of the form $Z^p$ for ...

Kindly take a look at these lecture materials. The instructor is suggesting to study books of Tanenbaum along with his supplied reading list. But, I am not finding any similarity of the content ...

The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...

I have three related questions which have been bothering me for a while now... Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I ...

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness. Firstly, I ...

how to different network create a secure environment? i found in net but im not sure is this correct?? Perform auditing and mapping. ... Keep the network up-to-date. ... Physically secure the ...

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...

If I have an address bus of 64K, i.e. it can access 64*1024 or 65536 locations, should I also have a memory chip with 65536 locations in it? What I'm trying to ask is that do all the 65536 locations ...

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...

I've learnt that the memory interfacing problem is used when we need to connect a memory that has lesser number of locations to a processor that has more address lines. For eg. Connecting memory chips ...

I encountered below statement by Alan M. Turing at here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original ...

I was solving problems from the exercise of the book "Computer Organization and Design" by Patterson. The problem reads like this: Consider stage latencies: ...

Can one create such function in Agda ? ℕ→ℕ-undecidable : ¬ ( (f g : ℕ → ℕ ) → Dec (f ≡ g)) ℕ→ℕ-undecidable = ? I am particularly interested in proof using ...

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...

I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules. Example grammer is like this S → ( S ) S | $\epsilon$ How can I derive like ...

There's a parlour game of inventing exotic operators for Relational Algebra, and thereby reducing the number of operators needed to be 'Relationally Complete'. A popular operator for this is 'Inner ...

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-...

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...

I am looking for a java implementation of constructing nondeterministic B\"uchi automata from linear temporal logic formulas. I tested several ones, but none of them worked for me. For example: 1) ...

Constrained Puzzle Generation: Let us say a sudoku puzzle is generated with the following procedure: Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$. Map $S$ to a $3 ...

What is the exhaustive list of reasoning tasks? As far as I can understand, then any logical reasoning reduces to 2 tasks only: 1) satisfiability problem (finding the assignment of the variables) and ...

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...