Problem Detail: Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far. In AlienTiles you have a board with $N times N$ tiles, all coloured Read More …
Blog
[Solved]: How many zeros should be in front of two’s complement model?
Problem Detail: The Problem Convert 256 to its 2’s complement representation. My Work I know that 256’s representation in unsigned binary is 100000000. What I know from working with two’s complement model is that the most significant digit represents the Read More …
[Solved]: Maximum non-intersecting subset of circles
Problem Detail: We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$. I want to Read More …
[Solved]: Concatenation of languages in NP
Problem Detail: I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn’t imply that each of the languages for themselves are in NP. I talked with my Prof about the Read More …
[Solved]: Find longest path between two disjoint sub-sets of vertices $V_1, V_2 subset V$ of a Graph
Problem Detail: I have a homework question which I would appreciate some help with: Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to be the maximum length between Read More …
[Solved]: How do you go about designing a vector processor architecture for the sum of matrix products?
Problem Detail: The following equation is a matrix expression where $B_i$ and $C_i^T$ are $ntimes n$ matrices and k is a positive integer: $$P = sum_{i=1}^k B_i C_i^T $$ So $P = B_1 C_1^T + B_2 C_2^T + cdots +B_k C_k^T Read More …
[Solved]: What are logical addresses and where do they actually reside?
Problem Detail: While studying about memory management, paging and segmentation there is a lot of usage of phrases like CPU generates logical addresses and logical addresses are converted to physical addresses etc. I know that the term physical address refers to Read More …
[Solved]: Using FFT to solve pattern matching problem with don’t cares
Problem Detail: I’ve studied about $FFT$ and it’s use in string matching, but there are several issues that bother me. First I’ll describe the problem and the solution I’ve seen in class: Suppose we have alphabet $Sigma = (a, b, phi)$ Read More …
[Solved]: Designing a DFA for binary strings having 1 as the fourth character from the end
Problem Detail: I came across someone else’s old post here Designing a DFA that accepts strings such that nth character from last satisfies condition And decided to try it. Apparently it was a homework problem but it was from 2013 so Read More …
[Solved]: How to find all shortest paths between two nodes in a weighted undirected graph?
Problem Detail: How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes. I want to find all nodes that can be on a shortest path. For example: Read More …
