All Questions

0
votes
1answer
7 views

Constant factor of an array

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 ...
0
votes
0answers
8 views

What kind of list or array would use the least space to implement a queue that will never have more than 10 elements. Why?

I was reading that circular array is fit for queue with few elements but not sure about if it also uses the least space.
-2
votes
0answers
9 views

MAXIMUM SUBARRAY [on hold]

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 ...
1
vote
0answers
10 views

How do we know $\neg \neg LEM$ isn't provable in MLTT?

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 \...
1
vote
0answers
10 views

Any barrier result for this kind of (non-relativising) technique?

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 ...
1
vote
1answer
18 views

Simple property of DFAs

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, ...
-1
votes
2answers
34 views

Why do we still use a Von Neumann Architecture in modern computers?

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 ...
0
votes
2answers
16 views

Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

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-...
0
votes
0answers
7 views

Memory addressing

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? ...
1
vote
1answer
13 views

How to check if DFA is actually a correct model of the intended system?

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 ...
0
votes
0answers
17 views

What do computers “think” objects are? [on hold]

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 ...
2
votes
1answer
14 views

Merging rectangles into rectilinear polygon

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

Finding recurrence relation for running time of an algorithm

I am pretty new to this, consider the following algorithm: ...
4
votes
1answer
243 views

Asymptotics question

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!
2
votes
2answers
24 views

Least common multiple of a list of numbers

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. ...
1
vote
1answer
27 views

Path between two vertices in directed graph without cyclic vertices

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 ...
-2
votes
0answers
25 views

Is A.I. through computation possible? [on hold]

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 ...
0
votes
3answers
23 views

Program counter in a CPU

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 ...
0
votes
0answers
24 views

Deterministic Finite State Automata - Benefits of using DFA to typical software coding and testing [on hold]

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 ...
1
vote
1answer
24 views

Undecidability of emptiness of LBA

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

How do i find the feature tracks for triangulation?

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 ...
0
votes
0answers
7 views

What is the minimun type of logical system that allows to determine if formalized sentence is well-wormed formula or not boolean type?

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 ...
0
votes
0answers
16 views

Question on preventing k from reducing too quickly during KMV intersection

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 ...
1
vote
1answer
25 views

What is the equivalent of the integers symbol Z for n bit only integers?

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, ...
0
votes
0answers
21 views

How do I solve the part (a), of the following question?

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!
0
votes
1answer
17 views

Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler

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 ...
0
votes
0answers
14 views

Which book or books are being used in these lectures on Distributed Systems?

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 ...
-1
votes
1answer
39 views

Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?

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)...
0
votes
1answer
26 views

Can a NP problem be reduced to another NP problem?

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 ...
0
votes
0answers
48 views

Alternative proof of the fact that heapify can be linear-time

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 ...
-1
votes
0answers
20 views

computer network : network layer [on hold]

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 ...
0
votes
0answers
42 views

How to quickly solve a linear equation for 7000 times?

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 ...
0
votes
2answers
108 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

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. ...
1
vote
1answer
37 views

Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

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 ...
0
votes
2answers
21 views

Address bus and memory

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 ...
1
vote
0answers
28 views

How to reduce number of move operations in an array?

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 ...
0
votes
0answers
6 views

Memory interfacing problem [duplicate]

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 ...
20
votes
4answers
3k views

What does Turing mean by this statement?

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 ...
1
vote
1answer
52 views

Given an array of size n, create a sub array with given conditions using dynamic programming

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 ...
0
votes
0answers
11 views

Finding percentage memory utilization in pipelining architecture

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

Proof that type does not have decidable equality in Agda

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

Finding the shortest path for synchronized pawns in a maze

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, ...
0
votes
0answers
25 views

Understanding the rules of parsing table construction

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 ...
0
votes
0answers
20 views

Relational Algebra with only one operator?

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 ...
11
votes
2answers
1k views

What is the meaning of 'breadth' in breadth first search?

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-...
1
vote
1answer
20 views

Complexity of set partition generation while equivalence relation is given

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 ...
0
votes
0answers
10 views

Java Source Code for Constrcuting Buchi Automata from LTL formulas [on hold]

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) ...
1
vote
0answers
86 views

Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

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 ...
0
votes
1answer
15 views

List of all possible reasoning tasks - satisfiability and theorem proving only?

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 ...
0
votes
0answers
23 views

ILP representation of the number of maximal 1 sequences in a row

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

15 30 50 per page