All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
2 views

Find effective memory access time in a system with TLB as well as physical address cache

The problem statement: I have a simple paging system with a TLB and a Physical Address Cache. Here's the flow: CPU generates logical address=(p,d) Given "p", CPU seeks in its TLB cache if ...
omnamah shivaya's user avatar
0 votes
0 answers
2 views

Looking for references that can teach me some of the fundamentals of computer science (from Peter Norvig's TYPITY page)

I am looking for resources/books/blogs etc from which it can tell me "how long it takes your computer to execute an instruction, fetch a word from memory (with and without a cache miss), read ...
noobman's user avatar
  • 11
0 votes
1 answer
7 views

Picking from a categorical distribution such that the selection is stable

Let's say I have a random variable $V$ which takes values from the finite set $V = \{v_1, v_2,...,v_N \}$. I want to pick one value randomly based on given probabilities $p_i = \Pr(V=v_i)$. Let's call ...
Hamed's user avatar
  • 101
-1 votes
0 answers
7 views

How to find Broadcast ID

Suppose i have an IP address 192.168.1.0/26, the subnet mask for this IP will be 255.255.255.192 with 64 hosts and an Network ID of 192.168.1.0. The broadcast ID in the solution is 192.168.1.63 for ...
Big Head's user avatar
0 votes
0 answers
14 views

why i am able to access private member of inner class with object of main public class,i am new can somebody please tell me

public class Encapsulation { public static class Enc { private int x; ...
munish's user avatar
  • 1
2 votes
1 answer
25 views

Vertex cover approximation: what's wrong with max-degree heuristic?

For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
Kye W Shi's user avatar
  • 121
-1 votes
0 answers
8 views

Sliding Window Subarray Question - TLE

Question: Given an integer array arr[] of size n. Your task is to count the number of good subarrays of the given array arr. Here any subarray arr[l ... r] is considered to be good if it satisfies the ...
Rithik Gundeti's user avatar
-2 votes
0 answers
12 views

Let A be the language of strings such that every character in an even position is a 0 [duplicate]

Let A be the language of strings such that every character in an even position is a 0. Give a regular expression for A.
chris's user avatar
  • 1
0 votes
0 answers
14 views

Best Search Algorithim

In Microsoft Power Bi there are formulas that can be used in visualizations called measures. These measures can be used within the formulas of other measures. As a result, a measure can have a complex ...
John Summit's user avatar
5 votes
3 answers
324 views

Accelerating semidecision of halting problem

There is a naive semidecision algorithm for the halting problem: simply simulate the program and see if it halts. Is there an algorithm that is asymptotically faster? More precisely, suppose the naive ...
Trebor's user avatar
  • 220
1 vote
2 answers
62 views

Why can one define a Turing Machine by its "description"?

I read Sipser's "Introduction to the Theory of Computation" a while ago. I am confused that in the book it is stated that a Turing machine can be defined by its "description" such ...
KatsuragiCSL's user avatar
0 votes
0 answers
12 views

Why is it not possible to recognize a self-complementary graph just by searching for a self-complementary graph on $8$ vertices?

From the paper by Gibbs (1974) it is known that every self-complementary graph on $4n$ vertices has $n$ disjoint induced $P_4$ subgraphs. Let's call the collection of these subgraphs a $P_4$ cover. ...
rus9384's user avatar
  • 1,781
1 vote
1 answer
24 views

Clique Covering - Does it help knowing a graph can be partitioned into equal-sized cliques with known representatives?

I have a class of graphs which have the following property: Let $G$ be a graph from this class. I know for this graph exists, for a known $n\in ℕ$, a partition of its vertices $V(G)$ into $n$ groups $...
ConnFus's user avatar
  • 113
1 vote
0 answers
31 views

Fast data structure for disjoint intervals

Over the years I've worked on a few applications that needed to model time intervals that are disjoint. For example, there's some kind of equipment available and time slots are booked out. For a data ...
grovesNL's user avatar
  • 111
2 votes
1 answer
49 views

How to show that $M$ is not finitely axiomatizable in the following case?

Problem: A set of formulas $M_0$ is an axiom system for a set of formulas $M$ if $\{A |A \text{ is a model for }M_0\} = \{A |A \text{ is a model for }M\}$, where $A$ is an assignment, or valuation. $M$...
The_Eureka's user avatar
2 votes
1 answer
87 views

Counting number of assignments restricted by implications

Suppose we have $n$ boolean variables, $x_1, \dots, x_n$. Some boolean variables can have implication relationships, e.g. $x_2 \implies x_5$, which means that if $x_2$ is true $x_5$ must also be true. ...
orlp's user avatar
  • 13.8k
4 votes
0 answers
75 views

Polynomial time algorithms for graphs and cycles

For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
Abel's user avatar
  • 41
1 vote
1 answer
21 views

Livout analysis of control flow graph of a program

I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc ...
edamondo's user avatar
  • 111
1 vote
3 answers
1k views

Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

I need some clarification regarding if computer scientists say a program like: ...
J Kusin's user avatar
  • 135
2 votes
1 answer
53 views

How to prove a problem is EXP hard

Summary of the problem: Given an alternating time turing machine ($M$), a polynomial $p(.)$ and a string ($w$), is it EXPhard to find if $M$ accepts $w$ using not more than $p(|M|+|w|)$ space? My ...
Nehul Jain's user avatar
2 votes
1 answer
39 views

FSA for 'closure' of a language; how to represent?

Is my interpretation of this correct? I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA. In order to do so, would I draw a new edge from the ...
mike's user avatar
  • 77
3 votes
1 answer
611 views

Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff

Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...
DaniDin's user avatar
  • 33
-1 votes
1 answer
41 views

Why is ot returning TRUE in first case and FALSE in the second?

I understand 0.3 does not have an accurate binary representation. Suppose I run the following code: Why is the answer "True" in the first case and "False" in the second? Shouldn't ...
Golden_Hawk's user avatar
0 votes
0 answers
14 views

What is the data management file system? [closed]

ILE C++ is a C++ compiler that is created by IBM . The compiler has a function called “SRCFILE()” that is described by IBM like this : “The name of the file that you reference on the #include ...
Ehsan Farahani's user avatar
1 vote
1 answer
46 views

Non-deterministic TM with an oracle to $R$

Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$. I'd ...
Mařík Savenko's user avatar
2 votes
2 answers
65 views

Is there an NP-hard problem that becomes polynomial when the inputs are at most $2^n$?

Let Q be a computational problem that accepts as input some $n$ non-negative integers. Is it possible (assuming $P\neq NP$) that Q is NP-hard in general, but can be solved in polynomial time when ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
13 views

Calculating the most influential set of source nodes on a target node when a source node's signal is propagated

I am mainly posting for guidance, as I don't know where to start looking in order to solve the following problem: Given a directed graph G with edge weights between 0 and 1. As well as a set of ...
arg3t's user avatar
  • 1
3 votes
1 answer
48 views

Stuck reading "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums"

I am reading the paper titled "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums", and I am stuck on theorem 2.1, I believe it is wrong, the proof has a wrong ...
Cecilia Chen's user avatar
1 vote
0 answers
22 views

Equivalence of two approaches for sparsity

I am trying to understand whether the following two ways to achieve a sparse matrix are equivalent in Pytorch. Let me add some context: I am training Sparse Neural Networks with a specific structured ...
Abhishek Tyagi's user avatar
0 votes
0 answers
19 views

Acceptance of n length word that is accepted by Turing Machine in m steps

let x a word with length of n an it is accepted by Turing machine in m steps. I think that if m<=n, there would be infinite number of words (all the words that starts with x) that are accepted by ...
Minseo Kim's user avatar
1 vote
1 answer
46 views

Relaxed form of the graph isomorphism problem?

Let $G_1=(L_1,R_1,E_1)$ and $G_2=(L_2,R_2,E_2)$ be bipartite directed graphs and let $\lambda:L_1\to L_2$ be a bijection between the $L$ vertex sets of the graphs. If I wanted to determine whether $...
Cromack's user avatar
  • 255
1 vote
0 answers
23 views

Sliding-window string/substring algorithm based on endpoints of substring

While there are various known algorithms to check if a string contains a substring (with the simplest but least efficient one being a brute-force sliding window, and one of the most efficient but ...
Cade Bryant's user avatar
3 votes
0 answers
48 views

Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
pabloealvarez's user avatar
2 votes
1 answer
38 views

Proof for Gas Refills on Circular Route Problem

The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
user171958's user avatar
0 votes
0 answers
54 views

How many states does a 2-symbol turing machine need on average to compute a N bit number?

The busy beaver problem asks what is the largest number computable by a 2-symbol N-state Turing machine, however, most numbers however are not re-presentable by a smaller program. For a sufficiently ...
mousetail's user avatar
  • 166
1 vote
0 answers
11 views

Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?

It is known that decision variants of these problems on perfect graphs are decidable in polynomial time. But is counting the number of maximum cliques or optimal colorings $\#\mathsf P$-hard on ...
rus9384's user avatar
  • 1,781
0 votes
0 answers
19 views

Is my characterisation of KVM and QEMU accurate?

I usually write essays on topics I am studying to help my understanding. Below are excerpts from my study of Virtualisation. I would like comments from real professionals on their accuracy. KVM is a ...
bonecrusher's user avatar
1 vote
0 answers
22 views

Help required for an example of a restricted 3,3-SAT problem instance?

"Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable. We prove the 3,4-SAT result to be the strongest possible and show that 3,3-...
TheoryQuest1's user avatar
0 votes
0 answers
32 views

Minimum unsat core and generalization

I have a problem that has been in my head for some time, it might be already well known but i cannot find ressources on something similar : The idea came from the will to identify the minimal unsat ...
user171915's user avatar
2 votes
1 answer
63 views

Interactive Proof for Graphs with No Non-Trivial Automorphisms

I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}$. I am interested in a method similar to the interactive ...
user171912's user avatar
1 vote
1 answer
53 views

Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
Aland Ameer's user avatar
-1 votes
1 answer
22 views

Knapsack problem with at least 1 item of two categories, no boundary on total items, unique items

Let's say we want to maximize the caloric intake of a person. One person MUST pick AT LEAST ONE steak and AT LEAST ONE vegetable (no limit of how many steaks or veggies he can pick, as long as they ...
Гого Зукед's user avatar
4 votes
1 answer
51 views

Are these two definitions related to strong NP-hardness equivalent?

Let $P$ be a computational problem whose inputs are integers. Consider the following properties: (a) There exists a polynomial-time reduction from some strongly-NP-hard problem $Q$ to $P$. (b) $P$ is ...
Erel Segal-Halevi's user avatar
-1 votes
1 answer
47 views

What is the the maximum and minimum amount of nodes in a heap

The title of my question says all that is needed. Some may argue that this is a duplicate question, because some years ago, this same question was made, but I couldn't understand the explanation, then ...
HaveMercy's user avatar
2 votes
0 answers
41 views

Decomposing a general polygon into simple ones

This is a question about splitting a very general kind of polygon into a list of simple polygons. Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit ...
Jürgen Böhm's user avatar
4 votes
3 answers
2k views

Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
releseabe's user avatar
  • 141
3 votes
2 answers
88 views

Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$

I am trying to prove that $T(n)\in\Theta(n!)$ for the following recurrence using the master theorem: $\qquad T(n) = 16T\left(\frac{n}{4}\right)+ n!$ My attempt We have that $f(n) = n! \in \Omega(n^{\...
z..'s user avatar
  • 133
2 votes
0 answers
58 views

Calculating minimum area annulus in O(n)

So given n points on a plane, I'm trying to find a pair of concentric circles so that all the points are between the circles, and that area is as small as possible, in linear time. What I'm thinking ...
K. Stuhl's user avatar
1 vote
0 answers
22 views

Recovering Examples Tanner Code Constructions

I've been trying to understand how the construction of Tanner codes works. The only example that I've found is in Tanner's original paper. However, I can't recover the claimed code parameters, and I ...
DaftWullie's user avatar
2 votes
1 answer
40 views

Question regarding definition of dIP

I was self-studying Interactive Protocols from Introduction to Computational Complexity by Arora, Barak. Initially, we define when we say a language $L \subset \{ 0,1 \}^*$ is a k round deterministic ...
Rishabh Kothary's user avatar

15 30 50 per page
1
2 3 4 5
979