Antimatroid, The

thoughts on computer science, electronics, mathematics

Archive for August 2008

Tree Drawing: The radial tree

leave a comment »

Although not as interesting as a sunburst diagram, the radial tree view can hold its color against a number of more primitive information visualizations. A radial tree view places the root at the center of the screen then fans out each child node. Each child node then fans out its children within a restricted span and continues on until each leaf is reached. The strengths of the technique allow for any easy to digest depiction of the structure behind the data in a compact space. A common application is visualizing computer networks. It is worthwhile to examine the algorithm behind the technique because it is an exercise in identifying simplicity.

While in college, I would have approached this problem by trying to identify the location of nodes in terms of (r, \theta) after all, I want a radial tree view- makes sense to sprint out the gate with a polar system right? While possible, this is a bad path to head down, as you end up drowning in a sea of extraneous details. Rather, it is better to think in terms of (x,y) and then map to (r, \theta). To clarify that position, let’s think about how we’d go about drawing the run of the mill tree view as in the figure below:

radialtree_normal

First some observations:

  • Every node at a given depth lies on the same line.
  • Every child at a given depth is given an equal share of horizontal space independent of necessity relative to the space owned by its parent.

We can construct a simple recursive definition for drawing the tree if we think about these two facts. Given a node, we want to center the node at the top of a region then carve up a region into the number of child nodes where each sub region is equally wide and the same height as the parent minus a layering distance, then draw a line from the parent node to the child node. Continue doing so until all of the nodes have been drawn. All that remains is mapping this tree to the radial tree view below:

radialtree1

To achieve this last step, we want to map each node at (x,y) to a point \hat{C} + r \cdot(cos(\theta), sin(\theta)) Where \hat{C} is the center of the display area. The radius is simply the node’s present y coordinate. \theta can be determined as the ratio between the node’s present x coordinate and the display width times 2 \pi. And thus, the mapping is complete.

Written by lewellen

2008-08-31 at 6:05 pm

Posted in Computer Graphics

Tagged with

Solutions to some Microsoft interview questions

with one comment

A couple of weeks ago, someone on reddit posted a link to a collection of Microsoft Interview Questions. As someone who interviewed with them while in college, I was curious to see what kind question they were asking folks. After reviewing the list, I thought I’d work out a few that looked interesting:

Imagine an analog clock set to 12 o’clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?

\displaystyle \text{Let } \theta_{h}(t) = \frac{2\pi}{43200}t , \theta_{m}(t) = \frac{2\pi}{3600} t \in \mathbb{R} \to \mathbb{R}, t \in [0, 86400)

\displaystyle \lvert \theta_{h}(t) - \theta_{m}(t) \rvert \equiv 0 \pmod{2\pi} \Rightarrow \frac{39600}{155520000} 2\pi t  \equiv 0 \pmod{2\pi}

\displaystyle \Rightarrow t_{k} = \frac{43200}{11} k, k \in [0, 22)

Thus*: 12:00:00 AM, 01:05:27 AM, 02:10:54 AM, 03:16:21 AM, 04:21:49 AM, 05:27:16 AM, 06:32:43 AM, 07:38:10 AM, 08:43:38 AM, 09:49:05 AM, 10:54:32 AM, 12:00:00 PM, 01:05:27 PM, 02:10:54 PM, 03:16:21 PM, 04:21:49 PM, 05:27:16 PM, 06:32:43 PM, 07:38:10 PM, 08:43:38 PM, 09:49:05 PM and 10:54:32 PM.

* Floor the conversion from t to hour, minute and second of day.

Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no ‘prime triples.’

Assuming:
\text{Let } n, r \in \mathbb{N}
p = 6n \pm r , r \in \{ 0, 2 \} \Rightarrow 3|p
p = 6n \pm r , r \in \{ 3, 4 \} \Rightarrow 2|p
p = 6n \pm r , r \in \{1, 5 \} \Rightarrow 1|p \wedge p|p
\therefore (\forall p > 3) \in \mathbb{P}, p = 6n \pm r, r \in \{1, 5\}

Twin Primes:
\displaystyle \text{Let } p = 6n - 1, q = 6n + 1 \in \mathbb{P}
\displaystyle n, r = \frac{p+q}{2} \in \mathbb{N}
\displaystyle\Rightarrow r = \frac{6n - 1 + 6n + 1}{2}
\Rightarrow r = 6n
\therefore 6|r

Prime Triples:
\displaystyle \text{Let } u = 6n - 1, v = 6n + 1, v = 6m - 1, w = 6m + 1 \in \mathbb{P}
\displaystyle n < m \in \mathbb{N}
\displaystyle 6n + 1 = 6m - 1 \Rightarrow m - n = \frac{1}{3}
\displaystyle \frac{1}{3} \notin \mathbb{N}
\displaystyle \therefore \not \exists u, v, w \in \mathbb{P}

There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman’s pace.

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what’s the other way?

One way:

  1. Woman 1 and 2 Cross, woman 1 returns. 3 minutes total.
  2. Woman 3 and 4 Cross, woman 2 returns. 15 minutes total.
  3. Woman 1 and 2 Cross. 17 Minutes total.

Other way:

  1. Woman 1 and 2 Cross, woman 2 returns. 4 minutes total.
  2. Woman 3 and 4 Cross, woman 1 returns. 11 minutes total.
  3. Woman 1 and 2 Cross. 17 minutes total.

If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

  1. Fill 5 quart pail with 5 quarts of water from source.
  2. Fill 3 quart pail with 3 quarts of water from 5 quart pail.
  3. Empty 3 quart pail.
  4. Empty 5 quart pail containing 2 quarts of water into 3 quart pail.
  5. Fill 5 quart pail with 5 quarts of water from source.
  6. Fill 3 quart pail with water from 5 quart pail.
  7. 5 quart pail now contains 4 quarts of water.

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

f(A) = \displaystyle\sum_{k = 0}^{|A| - 1} A_{k} -\frac{|A|(|A|-1)}{2}

public int duplicateNumber(int[] A) {
	int count = 0;
	for(int k = 0; k < A.Length; k++)
		count += A[k];
	return count - (A.Length * (A.Length - 1) >> 1);
}

Count the number of set bits in a number. Now optimize for speed. Now optimize for size.

\displaystyle \text{Let } m = \sum_{k = 0}^{\infty} A_{k} 2^{k}, A_{k} \in [0,1], m \in \mathbb{N}_{0}
\displaystyle f(n) = \sum_{k=0}^{\infty}A_{k}
\displaystyle f(n) = \begin{cases} \left( n - n \oslash 2 \right) + f\left( n \oslash 2 \right) & n \neq 0 \\ 0 & \text{otherwise} \end{cases}

public int bitsUsed(int n) {
	int count = 0;
	while(n != 0) {
		count += n & 1;
		n >>= 1;
	}

	return count;
}

Written by lewellen

2008-08-24 at 6:00 pm

Reimplementing arcade classics

leave a comment »

Arcade games are a fun exercise in trying out different techniques that ultimately yield the same result: a responsive graphical interface where an agent is controlled by the user’s keyboard. I’ve had a chance to design a few applications in a couple of languages and thought I’d go over the design decisions of each. Plus a little variety never hurts in tuning your skill set.

Tetris was a simple game pushed by Nintendo to fuel sales of the Game Boy in the early 90s. I wrote a variant awhile ago that uses n \times m blocks rather than tetrominoes to cut out unnecessary complexity. This C# implementation revolved around the .Net WinForms and falls under the umbrella of Object Oriented and Event Driven designs. A one dimensional array keeps tabs of how deep a block can fall along with a list of fallen blocks. Any time a block lands on top of another block or the user hits a key, an event handler processes the event and causes the screen to be repainted. This design felt forced but otherwise worked as needed. I hope to refine this approach in future applications.

Pacman was the iconic flagship of 80s arcade armada. During college I wrote a simple version of Pacman in C that relied on the prototypical input, logic and draw loop. In this implementation, an array is kept that represents the inanimate actors: nothing, reward and walls. In addition separate cursors are kept to keep track of Pacman and each of the ghosts. Design-wise, this worked out really well. Input was parsed and applied to Pacman, each of the ghosts move towards Pacman, termination conditions are checked and finally the array and animated actors are painted on the screen. Out of these designs, this one felt the most versatile.

Snake, also known as Nibbler or Nibbles was a classic game that used to get put onto cell phones (when phones used to come with games for free…) where you have a snake that grows as it consumes rewards. The snake moves around a torus (represented as a 2d surface) and the game is over when the snake covers the surface or when part of the snake crosses over itself. This implementation went with C# relying purely on the Console. The snake is represented as a linked list where every node holds a direction and location. As each loop passes, the direction and location of the head is passed onto the next segment and so on until the tail is reached. If the snake is on top of a reward a new segment is appended to the tail. The design is the same as my Pacman implementation, however there is no underlying array to maintain.

If the comments call for it, I’ll post more implementation details on any of the above.

Written by lewellen

2008-08-17 at 8:06 pm

Posted in Projects

Tagged with , ,

The ring of Gaussian Integers

leave a comment »

I recently started taking a foray into Complex Analysis as a means of filling in the gaps of my undergraduate mathematics knowledge. After reading about holomorphic functions, the Cauchy-Riemann equations and how to model ideal fluid flows I decided to take a break to digest it all. During this period I was reflecting on what I had done with Number Theory the previous summer and the question popped in my head: what is the complex equivalent of w \equiv v \pmod{z}? Or for that matter, are integer primes also primes in the complex domain (and vice versa)? And, are all complex z = \displaystyle\prod_{k = 0}^{\infty} p_{k}^{e_{k}} factorizations unique?

After looking around the internet for a while I came across a rather well written paper [pdf] by Assistant Professor Keith Conrad of the University of Connecticut that answered all of the questions brewing in my head along with the ones that weren’t. I’m going to surmise the basic ideas behind the solutions Conrad wrote about, if you have the free time it’s worthwhile to read the original text in its entirety.

If we consider the set of complex numbers of the form n + mi and restrict n, m \in \mathbb{Z} we have the set of the Gaussian Integers \mathbb{Z}[i]. If we take two values z, w \in \mathbb{Z}[i] we can say that z|w only if w = zu where u \in \mathbb{Z}[i]. Thus, \displaystyle\bar{z}w = \bar{z}zu \Rightarrow u = \frac{\bar{z}w}{\bar{z}z}. With this last step we’ve reduced the problem to satisfying two conditions: \displaystyle\bar{z}z|\Re{\bar{z}w} \wedge \bar{z}z|\Im{\bar{z}w}. For example let z = 1 + 2i, w = -5 + 10i \Rightarrow \bar{z}z = 5, \bar{z}w = 15 + 20i which satisfies the conditions 5|15 \wedge 5|20 \therefore z|w. For the congruence w \equiv v \pmod{z} with w,v,z \in \mathbb{Z}[i] to hold true, it must be the case that w = zu + v \Rightarrow z|(w - v).

Under \mathbb{Z} any integer m that is divisible by any integer other than a unit \pm 1 or unit multiple \pm m is said to be composite, otherwise m is said to be prime. The same definition holds in \mathbb{Z}[i] but our units are now \pm 1, \pm i and our unit multiples are now \pm z, \pm zi. As one might have guessed all primes in \mathbb{Z} are primes in \mathbb{Z}[i] however, the converse does not hold. For example 5 is prime but can be written as (1 + 2i)(1 - 2i) and is thus a composite number under \mathbb{Z}[i]. It is also useful to mention that if \bar{z}z \in \mathbb{P} then z is prime. By way of the Fundamental Theorem of Arithmetic, every composite integer can be written as the product of prime integers, this is also the case under \mathbb{Z}[i] and each factorization is unique.

The mechanics of finding the prime factorization of m \in \mathbb{Z}^{+} can be na├»vely done by trial division from n = 2 to \sqrt{m}. Once n|m reset n = 2 and m_{k} = m_{k - 1} / n and continue this procedure until m_{k} = 1. That is all well and fine for \mathbb{Z}^{+} but it isn’t immediately useful for doing the same under \mathbb{Z}[i].

For example, let’s consider z = -1395 - 12410i, since we are uncertain about how to factor z, lets think about how to factor \bar{z}z as we already know how to factor under \mathbb{Z} and see where that takes us. \bar{z}z = 155954125 = 5^{3} \cdot 61 \cdot 113 \cdot 181 We went from \mathbb{Z}[i] \to \mathbb{Z} so we’d hope that we could go the other way around by finding p = (n + mi)(n - mi) for each of the prime factors of \bar{z}z. In other words, we want to know p = n^{2} + m^{2} which will produce four Gaussian primes n \pm mi, m \pm ni. Thus, we find 5 = 1 + 2^{2}, 61 = 5^{2} + 6^{2}, 113 = 7^{2} + 8^{2}, 181 = 9^{2} + 10^{2}. Now, according to Conrad we should be able to pick any one of the four possible Guassian primes for each of the prime factors and multiply each Gaussian prime across, in doing so we get z = (2 + i)^{2} (2 - i) (6-5i) (8 - 7i) (10 - 9i). Now that’s pretty damn cool.

The general procedure for factoring a Gaussian Integer z into it’s prime components is to find the integer factorization of \bar{z}z and for each prime factor find p = n^{2} + m^{2}. Next, explore the Cartesian space formed by each factor’s four Gaussian primes until you come across a product coordinate that equals z and output said coordinate. As one can image this is a woefully poor algorithm for find the prime factorization of z. If anyone has ideas or knows of more efficient methods post them in the comments.

There is clearly much, much more to be said about Gaussian Integers, but this feels like a good stopping point. If you want to find out more about how some of the traditional Number Theory constructs are defined under \mathbb{Z}[i] you’ll want to read the entirety of Conrad’s paper or jump on Google and see what’s out there.

Written by lewellen

2008-08-10 at 8:05 pm

Posted in Number Theory

Tagged with

Tree Drawing: Sunburst diagram

with one comment

Information Visualization is an interesting subject for me because it is the aesthetics of displaying large amounts of information into an easy to digest vision that depicts metrics of interest. One branch of this subject deals with methods for visualizing hierarchical information such techniques as tree maps, hyperbolic tree views, et al are typically deployed. Of these methods, one less common is the sunburst diagram.

A sunburst diagram is essentially the polar form of a Tree icicle visualization. At the core is the root of the tree, each concentric ring represents the child nodes and is partitioned by the metric of our choosing to represent the percentage a node consumes relative to its siblings. Sunburst diagrams are ideal for displaying any kind of tree data where nodes have weights and the totality of the nodes represents a whole.

While there are certainly several existing software solutions out on the market that utilize this information visualization technique, I feel that the majority of which are too focused on solving one specific problem rather than stepping back to identify the general problem that sunburst diagrams solve. As a result, I find it appropriate to develop my own software solution.

I want to try and incorporate some of the following features that I feel are lacking in other applications:

  • Ability to visualize any XML document by way of import and option to export
  • Choose to visualize metrics based on the attributes defined on each node of an XML document
  • Capacity to search and filter information in the document
  • Freedom to navigate the tree in an intuitive manner
  • A clean and sharp looking user interface that is easy on the eyes

This project really boils down to a Swiss Army knife of simple data analysis tools. Depending on my schedule this project may or may not become a reality but could turn out to be useful for a variety of problems. As the project grows and matures I’ll try to post updates as appropriate.

Written by lewellen

2008-08-03 at 6:00 pm

Posted in Computer Graphics

Tagged with