316 reputation
19
bio website cs.uiuc.edu
location Urbana, IL
age
visits member for 4 years, 2 months
seen yesterday

No, I am a meat popsicle.


May
13
comment Is this a sufficient condition for vertex and edge transitivity?
The statement is false if the graph can be disconnected. A connected (4,4)-graph can be constructed by drawing a grid on the torus. Consider the disjoint union of two such graphs with different numbers of vertices.
May
13
answered For any $r,g$, is there an $r$-regular graph of girth $g$?
May
12
comment How do you go about solving difference equations?
These notes might be helpful, especially Section 5.
May
11
comment Form or asymptotic behaviour of $T(n) =2T(n-1)+n$
Are you allowed to pick more than one option?
May
8
comment What are some examples of a mathematical result being counterintuitive?
But its volume doesn't change! (Connelly's Bellows Theorem)
May
8
comment How to deal with the temporary nature of my knowledge?
Close. I'm suggesting that you let/force yourself get caught in details, instead of only trying to see the "big picture".
May
8
comment How to deal with the temporary nature of my knowledge?
@Self_Learner: If your current school is too rigid, why not change schools?
May
8
answered How to deal with the temporary nature of my knowledge?
May
6
comment The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.
Even simpler: A binary tree with depth 0 has 1 node (the root), not 0 nodes. But check your source's definitions. If they define depth as the number of nodes on the longest root-to-leaf path, instead of the (more standard) number of edges on the longest root-to-leaf path, then their statement is correct.
May
4
comment What is the definition of a cross cap?
Then "cross-cap" is just a synonym for "Möbius band". Both are homeomorphic to $RP^2$ minus a disk.
May
4
comment What is the definition of a cross cap?
Do you mean cross-cap as a subspace of an abstract 2-manifold (a Möbius band), or do you mean cross-cap as a geometric feature of a self-intersecting surface in 3-space, or do you mean something else?
Apr
26
comment A “State Hierarchy” Theorem for Turing Machines?
@adcvvc: I believe this is a double-starred homework exercise in the first edition of Hopcroft and Ullman's automata-thoery textbook.
Apr
25
comment A “State Hierarchy” Theorem for Turing Machines?
With a lot more work, you can reduce the number of states to 2.
Apr
22
comment How to figure out the log of a number without a calculator?
To answer the title: Check the CRC Handbook or use a slide rule.
Apr
22
comment How many possible ways are there
Apparently the formula is "6". What is the general question?
Apr
17
comment Shortest path variation
"Note that if two paths use the same vertex $v_i$, the cost $C$ is only paid once." — This makes things complicated. If every path paid for every vertex it traversed, you could just replace each vertex $v$ with a directed edge $v^- \mathord\to v^+$ with cost $C$, and then replace every edge $u \mathord\to v$ with the corresponding edge $u^+ \mathord\to v^-$.
Apr
17
comment Shortest path variation
Is this homework?
Apr
17
comment Shortest path variation
@dtldarek: I don't think so. He's trying to minimize the cost of each $s\leadsto t_i$ path, not the total cost of all vertices and edges in the shortest-path tree. (Also, technically, Steiner trees are only defined for undirected graphs.)
Apr
16
comment Most general way of selecting 10% of set elements
What property? Once a magic black box emits a subset of elements, how can any property of that subset depend on whether the black box is deterministic? (Give me two different black boxes whose outputs always have the property you want. I'll build a bigger black box that chooses one of your black boxes by flipping a coin. The output of my bigger black box always has the property you want.)
Apr
16
comment How Many Three-of-a-Kinds in Standard Poker?
Please use LaTeX for math: $13 \cdot \binom{4}{3} \cdot 48 \cdot 49$, etc.