The Windows Registry contains settings and configuration information for computers running Microsoft Windows. It's stored as a hierarchy which resembles organization similar to folder structure. However, instead of having folders they are called keys. If you run "regedit" on any windows machine you will be presented a window that allows you to view the registry keys. Under 'Computer' generally there will be displayed five root keys. The root key we will be looking at is 'HKEY_CURRENT_USER' which stores information about the currently logged in user.

In C# to start we want to make sure the following is specified at the top of our code:
using Microsoft.Win32;

Using the registry key class we can open and close keys, get and set the value of keys, or delete and create new keys. To open HKEY_CURRENT_USER we simply do the following:
RegistryKey key = Registry.Users;

From there we can access any of the subkeys under HKEY_CURRENT_USER, for example if you wanted to access Control Panel\Desktop in order to view the current user’s desktop settings so we could see what the user’s current wallpaper was.
// The true here means that we open it as writable
RegistryKey key = Registry.CurrentUser.OpenSubKey(@"Control Panel\\Desktop", true);
String wallpaper = key.GetValue("Wallpaper").ToString();
key.Close();
Console.WriteLine(wallpaper);

Notice that we need to pass the key value to a ToString method in order to get a string as a result because by default it will return an Object. Also when we are done with our key we should always remember to close it. Setting the value is just as simple if we wanted to change someone’s wallpaper to AdorableCuteKitties.jpg the code would simply be:
RegistryKey key = Registry.CurrentUser.OpenSubKey(@"Control Panel\\Desktop", true);
// note that the path to the wallpaper should be an absolute path here
key.SetValue("Wallpaper", "AdorableCuteKitties.jpg");
key.Close();

Creation and deletion is just as simple. By using the CreateSubKey() and DeleteValue() methods. It’s important to note that if you are deleting a key with child subkeys that DeleteSubKeyTree() should be used.

Using this method to modify user information I created a simple program in C# that would toggle the current user's screensaver enabled and disabled for when I watch TV or movies on my machine. It was made to work on Windows 7, which is why there are a few things a bit odd about the code. The ScreenSaveActive key in Windows 7 will always contain a value of 1 no matter what the state of the screensaver. So to get around that the key that stores what screensaver to use is first checked to see if it is active and to disable it the value from that key is temporarily stored in a dummy key (named Dummy) and the screensaver key is deleted. When it is re-enabled the screensaver key is restored based on what data is kept in the Dummy key.

The source and executable for the screensaver toggler can be downloaded: here.
The executable alone can be downloaded: here.

Andrey Markov is known for two things being a Russian Mathematician and having amazing facial hair (well probably not the latter, but I'd love to think so). A Markov chain is one way of describing data in such a way that we can determine the future state of the world by looking at the current state of the world.

Consider a world filled with zombies, vampires, and humans. In this world humans can become zombies, vampires, or stay human. Zombies can become humans by a drug created by Dr. Zork or stay zombies. Vampires can become zombies if they feed on zombies or stay human. In a Markov chain we want to consider the probabilities of each of these things occurring. Humans have a 0.50 chance of staying human and a 0.25 chance of becoming a zombie and a 0.25 chance of becoming a vampire. Zombies, on the other hand, have a 0.15 chance of the cure actually working and becoming human again and a 0.85 chance of staying a zombie. Vampires have the highest chance of staying the same at 0.95 and only a 0.05 chance of stupidly feasting on zombie.

What we end up with is a Markov chain that looks something like Figure 1. As you can see there are 3 nodes for the 3 possible states and transitions from those nodes to other possible states. It's very important that the transitions out of a node sum to one, because we are dealing with probabilities. We can represent this information in another way. Figure 2 shows the matrix for this data. This matrix can be used to calculate what the future will look like based on the current state of the world. For example if we start out with 100 of each type of living thing in our world we can do the matrix multiplication using the matrix and we get the calculation shown in Figure 3. The result shows that in the future there will be 65 humans, 115 zombies, and 120 vampires.

I decided to use Markov chains in order to generate random English sounding words. The program reads in a file containing words and generates a matrix that contains the transitions from one letter to the next letter in the word. Additional transitions are added to consider which letters begin a word and which letters tend to terminate a word. Then to generate a word a random starting position is selected and the transitions are followed until a word is generated.
Example runs of the program: 
$ python randomWord.py 
Source file: words.txt 
chaner

$ python randomWord.py 
Source file: words.txt 
wer

$ python randomWord.py 
Source file: words.txt 
drumire 

The source and input file can be found here.


Andrey Markov image from Wikimedia Commons.

Dynamic Programming was developed by Richard Bellman while he was working for The RAND Corporation in the 1950’s. During this time The RAND Corporation was employed by the Air Force. In his autobiography Bellman describes his reasoning for the name dynamic programming; the Secretary of Defense at the time, Wilson, “had a pathological fear and hatred of the word, research” [sic]. As a result the name was picked to shield what Bellman was doing within The RAND Corporation. In 1979 Bellman was awarded the IEEE Medal of Honor for the creation of dynamic programming.

Dynamic Programming is the process to solve a problem based on overlapping sub-problems, and it can be either top-down or bottom-up. Top-down approach to dynamic programming breaks down the main problem into sub-problems and will solve the sub-problems to get the solution to the main problem. A top-down solution makes use of recursion and memoization. Memoization is remembering of solutions to certain sub-problems, often in an array, so they do not need to be solved again. Comparatively a bottom-up solution is when all sub-problems are solved in advance and later used to form solutions to larger problems made up of those sub-problems. Top-down starts with the main problem and will work “down” towards the sub-problems whereas the bottom-up approach starts at the sub-problems and works to the “top” main problem.

An example of a problem that can be solved by using dynamic programming is the Roaming Zombie problem. A zombie is in a city and is hungry so he wishes to find a brain. Zombies are slow and in order to get to the brain as fast as possible the zombie must follow the shortest path he can to reach the brain. Figure 1 shows a directed acyclic graph (DAG) of the possible ways the zombie can reach the brain. Using a bottom-up approach in solving this problem we start at the brain and work backwards to the starting point. From each point we find the shortest path to the brain from it. For example from the point brain to brain the shortest distance is zero with the path of nothing because we are already at the desired ending point. From B to the brain we only have one option of going to the brain which gives us a distance of four. Continuing backwards we are at D and we wish to go to the brain. We can either go from D to B or from D straight to the brain. From D to B we travel a distance of two plus the total distance from B to the brain which we already determined was four giving a total of six. From D to the brain we travel a distance of seven. As six is shorter than seven we note that the shortest distance from D to the brain is six and that the path to take is D → B → Brain. Building upon the previous sub-problems we can build a solution to the entire problem.

Figure 2 shows the solutions to the sub-problems. Continuing to work backwards from where we left off node A has only one option for which path to take so we take the solution from B and add it to A → B to get seven for the optimal distance and a path of A → B → brain. From C we also only have one option. So we take the optimal path from D and add the distance of from C → D to it. The distance in this case is ten. The path is C → D → B → brain. Looking at this you can see that the shortest path from the starting position to the brain is from start → A → B → brain and that the distance traveled is fourteen. Each node contains above or below it the optimal path and distance that the path would cover. Where there is more than one option for the path to follow, as in the case of the starting position, we look the two options and see what the optimal path in each case is and pick the minimum of the two.

Another problem that can be solved using dynamic programming is The Pirate Chest problem, a variation on the common Knapsack Problem. This problem can be solved by using a top-down approach to dynamic programming. The pirate Captain Kidd is the only pirate known to have buried his treasure. Captain Kidd has N types of treasure of varying cost and size and a treasure chest that can hold a capacity of M. All items not put in the treasure chest will be spent immediately or split up amongst the other pirates. We need to find a combination of items so that Captain Kidd can maximize his savings.

Figure 3 shows the items that Captain Kidd has to choose from for his treasure chest as well as the size and value of each item. The items have been given names A, B, C, and D for simplicity.

Rather than selecting items just to maximize the usage of the area in the treasure chest we need to select items that utilize the most area while getting the most value for that area. Figure 4 shows the solution for the problem. Note that the sub-problems in this case are the items that are available to choose from. Starting with using only A’s then A’s and B’s then A’s, B’s and C’s and finally all four possible items. The values written in the table is the maximum value that can be stored in the treasure chest.

The algorithm to find the solution is to first note the largest sized item in the current grouping. In the first row of Figure four there is only one item so the size to keep in mind here is three. If the size is less than the size of the item no items can be stored so our first two columns in the first row are zero. Once we hit a number over our item size we can finally start storing items. We cannot store partial items so from size three through size five we can hold one A giving a value of two. Once we hit a size of six we can start storing two A’s for a value of four. Our program has no way to evaluate the problem in the same way that the human mind would, so another way of knowing this is to examine the size that it can carry, in this case 6, and subtract the size of the largest item (three) to get a value of three. We look in our matrix under three to find that the left over space can hold a value of two. The addition of the value of the largest item plus the value the left over space can hold will give us the total value the current size is able to hold. If we simplify this statement into an equation we have:
Value(Size) = Value(Size – ItemSize) + ItemValue, where Value(Size) will give the value using all available items at a given size and ItemSize is the size of the largest item we are able to use. We also need to check the value of the column in the row above the current row. The algorithm is as follows:

int treasure(int[] size, int[] value, int n, int m){
   if(n==0)
     return 0;

   if(m - size[n] < 0)
     return treasure(size, value, n-1, m);
   else
     return max(treasure(size, value, n-1, m), treasure(size, value, n-1, m - size[n]));
}


The function treasure takes four values: size, value, n, and m. Size and value are both arrays containing the sizes and values for each of the items. The integer n is the item number in our case we would map A, B, C, and D to 1, 2, 3, and 4. The integer m is the size of the treasure chest. If we modify the above code to remember the values of previously solved sub-problems using memoization we can prevent the program from doing work repeatedly. This can be done by creating an array of the sub-problems and their values and adding a check in the beginning to see if the solution to the sub-problem exists in the array.

A problem that can readily be solved by using dynamic programming and the application of memoization is the Fibonacci sequence. The problem becomes a little more interesting when you add in the concept of population growth. In our first example we saw a zombie coming for a human brain now we are going to look at how these zombies multiply. We have learned in “Dawn of the Dead” and other Hollywood movies the zombies multiply by biting humans.

Figure 5 shows the population growth of zombies over time. As you need to start with one zombie in order to make more, the population at day one is one. At day two our population is still one because he got lost in a DAG and was unable to find any brains to eat. On day three our first zombie finally goes and makes another one to give us two zombies. Day four our new zombie creates another one so we have three. On day five our two new zombies create new ones to give us a total of five. We can simplify the model of the population growth of the zombies by the statement the total of zombies on any day is the sum of total of zombies the two days before it. However, on days one and two our first zombie is alone so it is important to note that the total will be one on those days. Mathematically put:
Total(Day) = Total(Day-1) + Total(Day-2) if Day > 2, otherwise Total(Day)= 1. When shown as a statement to this a recursive method is easy to see and we get the following code:

int total(int n){
   if(n == 1 || n == 2)
     return 1;
   else
     return total(n-1) + total(n-2);
}


The above code has issues with it, sure it was the easiest to see of the solutions to the problem of finding zombie population on a given day, but a lot of work is done multiple times. To find the size of the zombie population at day five we need to find the size of the population at days four and three. To find the population on day four we need to find the population on day three and day two. Then later on in finding the solution we need to find the population for day three again. By adding memoization to the above problem we can save time and thus have more time to prepare for the coming zombie apocalypse as at this rate the population will grow very fast. The following code has the addition of memoization to prevent repeated work.

static int[] memo = new int[MAX];
int total(int n){
   if(memo[n] != 0)
     return memo[n];

   int pop;

   if(n == 1 || n == 2)
     pop = 1;
   else
     pop = total(n-1) + total(n-2);

   memo[n] = pop;
   return pop;
}


We start out with an array outside of the function that will store sub-problems that we have already solved. When we first enter the function we check if we have done the work already, if we have then we return it. In cases where we have not done the work already, we do it and then we store it in our array and return the discovered value. This eliminates all repeated work.

As we have seen in the above examples dynamic programming takes larger problems and breaks them up into easy to solve pieces to build up a whole. The two approaches to dynamic programming allow us to work with a problem in a bottom-up fashion or a top-down fashion. In the three examples we have seen how different problems can be solved by using the idea of dynamic programming. We have also seen that recursive solutions to these problems often benefit from the usage of memoization. Since its creation nearly 50 years ago dynamic programming has affected how we approach solutions to problems.

References

1. Bellman, Richard. Eye of the Hurricane. Singapore: World Scientific Publishing Company: 1984.
2. “Richard Bellman, 1920 – 1984.” IEEE.<http://www.ieee.org/web/aboutus/history_center/biography/bellman.html>. archive
3. Sedgewick, Robert. Algorithms in C++. Massachusetts: Addison-Wesley Publishing Company,1992.

You may have noticed something a little different up in the tab bar in the latest release of Firefox. Something that looked a little bit like this:

Maybe like me you found yourself looking through the options to find a way to turn it off just to find that none exists. Never fear! There are two ways to remove this completely pointless button (who doesn't use ctrl+t?).

The first is best for people who really don't want to mess around with files and it's a small Firefox add-in called Remove New Tab Button. Though, for those of us that think it's silly to install an add-in just to be able to remove the button there is a way.

You can create a userChrome.css file in your profile-directory/chrome. If you are using Vista you can find this at:
C:\Users\{username}\AppData\Roaming\Mozilla\Firefox\Profiles\{some value}.default\chrome
If you don't already have a userChrome.css file simply copy the userChrome-example.css file and rename it to userChrome.css. Open this file up in a text editor and add the following:

/* remove New Tab button */
.tabs-newtab-button {display:none!important}

Save your file and the next time you start up Firefox the completely pointless button will be gone.

Programming is art, and like a lot of new forms of artistic expression it struggles to define itself as such in the community. However, as Donald Knuth suggests in his series of books ‘The Art of Computer Programming’ the crafting of code is an art form. It is often thought of as being tied to heavily into Mathematics to be considered an art, but anyone who has ever looked at a fractal can tell you that there is a certain amount of beauty in math as well.

The empty file is the programmer’s blank canvas. The planning done ahead and comments throughout the code are sort of the sketch lines that form the basis for the piece. The code itself is the paint that gives the entire thing body. It’s not just as simple as a painting analogy. The process of coding is in itself a very creative process. There is not one way to approach a particular problem and each programmer has his or her own style; from the way that they indent, where they place their braces, when they comment if they do at all.

In some ways this explains the anger of programmers when they are forced into code conventions in the working world. They have their certain style and an outside style is being forced upon them. It’s like da Vinci being forced to paint in the style of van Gogh, it at first looks and feels unlike the code that you are not used to writing. The creative aspect also tends to explain why programmers have a tendency to make programs more difficult for themselves in the corporate world. They are looking for a challenge and for some way to be creative and often this causes horrible (yet creative) monstrosities.


The Demoscene is an example of what happens when programmers try to capture the true creativity and accept programming as an art. Amazing collaborations of graphics and sound pushing the limits of what the hardware is capable of doing. Originally starting on the commodore 64 and showing just what creative programmers could do with large hardware restrictions. The Demosceners were able to make the Amiga do things never seen before.
Putting a bunch of lines of code together and being able to visualize the end result takes a massively imaginative mind. Unlike many other jobs what really makes a programmer great is tons of practice. No amount of schooling alone can turn a novice programmer into a guru.