All Questions

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

$ \# 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 ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?

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

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

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

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

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

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

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

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

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

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

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

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

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

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)^*$?

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

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

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

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

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

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 $\{ ...

Consider the following C code: ...

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

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

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.

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.

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

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

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

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