All Questions

Filter by
Sorted by
Tagged with
-1
votes
0answers
4 views

Prove the Droid Trader Problem is NP-complete

This question is from Algorithms Design. A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $n$ different types of droids ...
2
votes
3answers
15 views

Can a Non-Deterministic Pushdown Automata recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $ such that • The alphabet of the machine is {, a, b, x}. • The symbol x will never appear on the input a. • The contents of the tape at completion may be anything. • The head ...
2
votes
0answers
7 views

Algorithm to separate single contour of glyph into several strokes?

A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve). Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point ...
1
vote
0answers
11 views

Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ ...
0
votes
0answers
11 views

Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

For example, if it is a $ O(2^n) $ algorithm that loops through 0 to $ 2^n - 1 $ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-...
1
vote
0answers
9 views

Proof that $(L_{all})^C$ is not recursively enumerable

The problem: We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$ Hence, $L_{all}$ is the set of all encoded Turing machines (the $\...
0
votes
1answer
18 views

Simple algorithm to code

I am new to programming. I have an algorithm which i cannot code, it may be very simple but i am a little bit confused. I will be pleased if you answer. Here's the algorithm; We have a raw sausage, we ...
0
votes
0answers
6 views

Automatically input URL and scan webpage for matching information [closed]

I'm going through a website that connects to a database, and its URL is in this type of format: www.abc.com/list.aspx?ID=3000001 www.abc.com/list.aspx?ID=3000002 www.abc.com/list.aspx?ID=3000003 and ...
0
votes
0answers
7 views

In Markov Decision Processes, why does R0 get skipped?

I'm in the process of learning the MDP, and a pretty small thing is bugging me. Everywhere I look, I see the order of things go in this order: $S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \ldots, A_{t},...
0
votes
0answers
8 views

Confusion about analysis of lenght of lists in Hash Table with chaining under SUHA

I am working on to prove that the maximum length of any chain in a hash table of length n which gets n elements added to it is $O(\frac{\log n}{\log \log n})$ (Assuming uniform hashing). Let $X$ be ...
0
votes
2answers
10 views

How to make single cycle processor pipelined?

I was asked that how can one make a single cycle processor pipelined on a CS course without any specifications regarding the design. I suppose, that I should answer that what should be changed on ...
1
vote
1answer
14 views

Given a set of sets, what is the largest common intersection between them?

Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to ...
0
votes
0answers
7 views

Question on Cache Size

I'm having trouble understanding this particular problem. So given that: Cache size in bytes = 4096 The number of cache lines = 64 The cache block size in bites = 64 The number of main memory ...
0
votes
0answers
26 views

What's the problem of Learning Algorithms used for Automated Theorem Provers?

I've googled a lot but I haven't found an automated theorem prover/problem solver able to solve problems like a human. I am interested in a specific type of prover: the learning ones, like Support ...
-1
votes
0answers
8 views

Path with least max-weight, in an undirected connected graph

The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city ...
1
vote
0answers
13 views

Getting rid of negative-cost edges in min-cost max-flow algorithmically

I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
2
votes
0answers
31 views

Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
0
votes
1answer
15 views

CTL formula for “for every computation it is always possible to return to the initial state”

In the book 'Principles of Model Checking' by Christel Baier and Joost-Pieter Katoen they state that the CTL formula for " for every computation it is always possible to return to the initial state" ...
0
votes
0answers
21 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
2
votes
1answer
35 views

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n. $$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
2
votes
1answer
48 views

Converting connected graph to disconnected graph by removing minimum vertices

How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?
2
votes
1answer
15 views

Finding maximal cardinal independent set given oracle

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
1
vote
1answer
10 views

Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...
1
vote
1answer
31 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
1
vote
1answer
26 views

Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...
2
votes
1answer
77 views

How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
0
votes
0answers
11 views

Git Merge Lowest common ancestor problem

How does Git find the 'merge base' of two branches in a commit graph? From what I understand, this reduces to finding the lowest common ancestor of a directed acyclic graph. After reading up on ...
1
vote
1answer
23 views

doubt in pipelining

I am not from cse but trying to learn computer architecture on my own. Please clarify the following. In case of pipelining, each stage or subcomponent or subtask is assumed to be done in 1 CPU ...
0
votes
0answers
18 views

File Systems (Operating Systems)

The figure below depicts the structure of a simple inode-based file system. Each rectangle represents a disk block of some fixed block size. In respect to this diagram, I am asked: (a): Does this ...
0
votes
0answers
12 views

Adding two 4 bit binary numbers into 2 7 Segment LED up to 30 [closed]

I am trying to build a 2 bit binary adder into 2 7 segment LED's up to 30 and I'm having trouble getting passed nine as I believe there need to be an overflow but I am not sure. Was hoping to get some ...
2
votes
2answers
23 views

Knapsack with a fixed number of weights

Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
0
votes
0answers
15 views

Associative mapped cache, word addressable

I have an associative mapped cache with 10 tag bits and an offset of 7bits. What is the size of each main memory block in words(word addressable) and main memory size in words? i worked it out as: ...
1
vote
1answer
14 views

Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
1
vote
0answers
23 views

Decidability Turing Machine [closed]

If I have the code of a TM as $\omega$ with $\Sigma=\{0,1\}$, is it decidable that $\omega$ is the code of an TM? I would say yes because there is a finite number of codes of all TMs and i can create ...
3
votes
1answer
99 views

Regular expression for strings not starting with 10

How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
-1
votes
1answer
22 views

Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
-1
votes
0answers
34 views

“Character placeholders” in a text field

The following question is asked to understand if this question can even be answered. Say we have a data field to which a stream of one or more characters could be inputted (say as a string or as a ...
3
votes
1answer
22 views

Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
-2
votes
1answer
31 views

How to find an solution set of subset sum when given an oracle to subset sum problem [closed]

The Subset Sum Problem: Input: a finite subset S of integers, and an integer t. Question: does there exist a subset A ⊆ S such that the members of A sum to t? Suppose you have access to an oracle that ...
1
vote
1answer
41 views

Proving NP-Complete problem by reduction of subset-sum

My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is ...
1
vote
0answers
18 views

Show that SQUARED-SUM-PARTITION is NP-complete

Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$, and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ ...
0
votes
0answers
21 views

What are the errors in the following program?

Consider the following C code: ...
4
votes
0answers
20 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
0
votes
0answers
14 views

When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for perfmance

When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for performance gain ?
1
vote
1answer
23 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
27 views

Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
4
votes
0answers
48 views

Assign n people to m rooms of different sizes, such that noone is alone

I'm looking for an efficient way to assign n people to m rooms in a very specific way. INPUT: The program receives two sets of people (set of males and set of females), as well as a set of available ...
5
votes
1answer
62 views

Minimum edge weight k-exact cover with triangle inequality

Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in ...
1
vote
1answer
29 views

NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...
1
vote
1answer
39 views

How do I use message passing to find the maximum of all values in a grid?

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...

15 30 50 per page