Problem Detail: Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned. Is there an algorithm which, when given a ratio a/b, divides the plane with a straight line, so Read More …
Category: Uncategorized
[Solved]: How to prove “The power set of a countable set must be uncountable”?
Problem Detail: I’m not sure if this statement is correct, but my friend said so. The problem arose from this T/F question: Let $F={f: f$ be a primitive recursive function from $mathbb{N}$ to $mathbb{N}}$, then $2^F$ (Power set of $F$) is Read More …
[Solved]: How to optimize a function by maximizing 1 variable and minimizing another?
Problem Detail: Problem I want to implement an optimization algorithm for my file transfer program. The program buffers data in a local file before uploading to central server periodically and it compresses the files before transferring. I would want the program Read More …
[Solved]: Check if adding an edge to a DAG results in a cycle
Problem Detail: On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can’t provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest Read More …
[Solved]: Facts about internal and external path lengths of binary tree
Problem Detail: While learning binary tree’s properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some facts about these as follows: $S_n=1+frac{U_0+U_1+…+U_{n-1}}{n}$ For large $n$, $S_n=2 log_en$ Read More …
[Solved]: Family of types in type theory
Problem Detail: Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a “family” ? I understand index by a value (n length Read More …
[Solved]: regular expression: sum of positive fixed point decimal numbers
Problem Detail: I need help with this exercise. Indicate the regular expression for the following Languages. Explain your expression in one sentence and indicate the basis form of the alphabet. Indicate also every assumption you make. i) Sums of positive fixed-point Read More …
[Solved]: Difference between edges in Depth First Trees
Problem Detail: I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after reversing). Several DFS trees are created during this Read More …
[Solved]: Minimax algorithm when all the options are the same
Problem Detail: tl;dr What does the Minimax algorithm do when all its options are the same? Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize) (Source: Myself) Imagine this is the tree for a game (tic-tac-toe, maybe?). What Read More …
[Solved]: Are there more partially recursive functions than and recursive functions?
Problem Detail: Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ? Asked By : chgsilva Answered By : lPlant No they have the same cardinality. They have the cardinality $aleph_0$. Both Read More …
