All Questions

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

Intuitive proof that all planar graphs are disk contact graphs

Planar graphs are graphs which can be drawn on the plane without edges crossing. Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. ...
0
votes
0answers
6 views

Turing Machine for Check Validity of Unary Multiplication (A=B*C)

I have a lot of difficulty with the turing machines. I understand the theory well, but I need help with a lab exercise... Design a SINGLE TAPE Turing Machine that accepts the language $a = > b \...
0
votes
1answer
11 views

Number of subsequence's with same values of bitwise and, or and xor

GeeksForGeeks We are given an array arr of $n$ element. We need to count number of non-empty subsequences such that these individual subsequences have same values of bitwise AND, OR and XOR. For ...
0
votes
0answers
9 views

I am preparing for Bank PO and I require suggestion for buying theoritical books

I am preparing for Bank PO exams and I require some guidance about books which contain topics like MS Office, Network Systems(Star ,Bus etc.) and also computer history(generations and all). I would ...
0
votes
0answers
6 views

Given a list of text strings (HTML file content e.g.) determine the "best template system" for them

I want an algorithm that takes a list of strings $X = \{ x_1, \dots, x_n\}$ over an alphabet $\Sigma$, and determines the smallest templating of the strings, where by templating I mean a string ...
0
votes
1answer
9 views

Same instances for different problems

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...
0
votes
0answers
11 views

What is related to the no of instructions a CPU can handle at one time?

A) 32bit word size B) 3GHz clock speed I think should be (A).2^32 instruction at one time ?
0
votes
0answers
3 views

How does merkle trees help in effecient verification in a system like IPFS?

I do not understand how Merkle tree can be used to efficiently verify data in a peer to peer, distributed network like IPFS. I mean I understand how the merkle tree is constructed: basically take a ...
0
votes
0answers
17 views

Reduction from clique to steiner tree

We know that maximum clique and minimum Steiner tree are NP-hard. I am trying to come up with a reduction from clique to Steiner tree. However, I have no idea, can anyone help me?
-1
votes
0answers
17 views

How ALU transistor count has scaled throughout evolution of central processors

The arithmetic logic unit, ALU, is where the computation takes place in a CPU, and the rest is registers and control unit. I have a hard time understanding how ALU would increase in proportion to the ...
0
votes
0answers
11 views

Minimizing total penalty from trips over all travel days

I would like to discuss with you please the following problem and it's solution. Setup: We are travelling with the following constraints: You can only drive in the daytime. On any given day, you can ...
3
votes
3answers
524 views

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
0
votes
0answers
21 views

Asymptotic Analysis of code that are unusual

We all know that the RUN Time of most of our program are Big O of linear time, quadratic time, cubic time or log time. But Can this be in unusual or uncommon poly time like $x^6-y$ or cosine function ...
0
votes
0answers
5 views

Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...
0
votes
0answers
17 views

Find balanced edge of a binary tree

What algorithm can be used to find a balanced edge in a binary tree? If we remove that particular edge, the tree is split up nearly equally. Each tree will have at most $ \ceil{(2n-1)/3}$
1
vote
0answers
18 views

Method for computing the similarity between two algorithms

Are there any methods for computing the "similarity" between two algorithms? Intuitively, selection sort and merge sort are more similar to each other than merge sort and radix sort. I want ...
2
votes
1answer
13 views

prove that 2 collection have the same VC-dimensions

I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand. The question goes like this: Suppose ...
0
votes
0answers
12 views

What type of neural network or machine learning technique would you apply?

I want to predict as many time steps of a variable (X) as possible. The more time steps forecasted, the more successful the solution proposed. To the best of my knowledge, applying LSTM neural ...
0
votes
0answers
8 views

Proof of lemma for competitive ratio on subsequence - Strip Packing

In this paper by Azar and Epstein in Section 4 they consider online strip packing of rectangles without rotation in a setting where when a rectangle arrives it has to be lowered monotonically ...
0
votes
0answers
16 views

What are the realistic benefits that ARM chips can bring to supercomputers?

Supercomputing is faced with the power wall challenge where the design of more powerful supercomputers has to ensure that their eventual operation is power efficient enough to be economically viable. ...
0
votes
1answer
35 views

Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language

Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ...
1
vote
2answers
21 views

What is the minimum pumping lemma length of $01^*0^*1$?

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
0answers
22 views

Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
3
votes
0answers
26 views

Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...
0
votes
0answers
5 views

What are the axioms in the Semantic Networks

The Professor has given us a Assignment and Has asked us to tell the axiom that is used to define the semantics of the semantic network of one Particular example, the issue is I have no Idea what ...
1
vote
2answers
32 views

Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
0
votes
1answer
17 views

Give an O(n^2) algorithm to solve

This is my homework question Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that A[i] + A[j] = α for a given value α. Give an O(n^2) ...
2
votes
2answers
42 views

Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
2
votes
0answers
9 views

Minimum number of registers for mutual exclusion

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...
-2
votes
0answers
23 views

Is $\{a^{2n} b^{3n} \mid n≥0\}$ a context-free language?

Is $\{a^{2n} b^{3n} \mid n \ge 0\}$ a context-free language? Also. I need to prove that $\{a^s b^t \mid s=t^2, s,t \ge 0\}$ is non-regular using the pumping lemma, and that $\{a^s b^t \mid s \neq t^2, ...
0
votes
0answers
17 views

Why the last elements of the array of heap is itself heap

If we represent a heap using array the 2nd half of the array will be represent the leaf nodes of the heap. But I can not understand for array of length n, all elements in range A[[n/2+1]....n] are ...
2
votes
1answer
35 views

Determines the smallest set of unit-length closed intervals that contains all of the given points

Question: Describe an efficient algorithm that, given a set $\{x1, \cdots, x_n\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given ...
0
votes
3answers
73 views

Can there be a computer without software (only hardware)?

Can there be a computer without software (only hardware) which can produce meaningful output? "Software" would be for example an operating system (whether in the level of "firmware&...
1
vote
0answers
16 views

Complexity classes and "local pre-processing"

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
-3
votes
0answers
22 views

need help with a project python

Description: In this work you will have to design the logic and implement the code in python language in order to display (real time) information about the weather in five areas of Greece: Athens, ...
0
votes
1answer
25 views

Algorithm to find the saddle point in a Binary tree

How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)
1
vote
1answer
25 views

Splitting a binary tree into two halves

I am looking to prove the following: Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes. I am not sure how to ...
0
votes
0answers
11 views

--Graphical Models-- Understanding blocked paths and conditional independence

I am quite confused by this slide from a course I found on the internet from UCL on Graphical Models. Here is the slide: I would like to confirm whether I have correct understanding: In the following ...
-4
votes
0answers
18 views

Loops converting into a for loop [closed]

Convert the following while loop into a for loop. Your code should be written so that the return statement does not need to be altered. You are allowed to change the code before the while loop proper. ...
0
votes
0answers
17 views

Varient of Traveling Salesman Problem

I am trying to solve a variant of the traveling salesman problem. In this variant, the nodes have a state which is required to go in order. Specifically, first is order food, second is give food, and ...
0
votes
0answers
6 views

Discrete Event Simulation: modeling entity arrivals

I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...
-1
votes
0answers
15 views

Given a balance sheet find name of person to whom you owe the largest amount [closed]

So I came across this question and I would like to know if I am on the right track,if not I would like it if someone could give me tips on how to approach the following problem. "You have a ...
1
vote
1answer
46 views

Why don't we recognize Python as a compiler-based language?

I just read this Why doesn't Python need a compiler? I know that Python isn't absolutely compiler or interpreted but it is both of them it's maybe an interpretive, high-level, and all-purpose ...
0
votes
0answers
7 views

Hand Landmark Coordinate Neural Network Not Converging

I'm currently trying to train a custom model with tensorflow to detect 17 landmarks/keypoints on each of 2 hands shown in an image (fingertips, first knuckles, bottom knuckles, wrist, and palm), for ...
1
vote
0answers
21 views

Minimizing number of MxM squared tiles in an infinite grid covered by any part of a shape

Without restriction (e.g. continuity or convexity are not guaranteed), we're given an W x H raster-based shape that needs to be placed on an infinite tiling of <...
1
vote
1answer
19 views

Las Vegas vs Deterministic in one-way communication complexity

I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte ...
1
vote
1answer
29 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
0
votes
0answers
13 views

The expected total reward of an Epsilon-Greedy algorithm

I have acknowledged that the $\epsilon$-greedy algorithm does exploration and exploitation with probability $1-\epsilon$ and $\epsilon$. Is there a way to simply express the expected total reward $\...
0
votes
1answer
30 views

What is wrong with this "proof" of $coNP = NP$? [duplicate]

I am wondering why the following "proof" of $coNP = NP$ does not work: $\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides ...
0
votes
1answer
26 views

Is it true that $P = coNP$?

I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an ...

15 30 50 per page
1
2 3 4 5
846