I found myself recently explaining a few times how the data structure commonly called a stack works. The technical term for a stack would be a Last in First out Data Structure (LIFO). To practically repeat myself, this means that the last object to go into the structure is the first one which will come out of the structure.
I've heard plenty of interesting analogies for this behavior. All too often I hear this being described as a stack of plates. Plates can be added easily onto the top of the stack, and can be removed from the top of the stack easily. Working with any plates not on the top is difficult because there are other plates on top of them. This is basically how a stack works.
While explaining the push() and pop() methods of stacks, I came up with an analogy which I think is far more interesting. To my students I described the stack as a Pez dispenser. You load the dispenser from the top and unload it from the top.
When you get a candy from the dispenser it comes out of the top and you now have possession of it. With a stack you get the value from the top and you now have possession of it. When adding candy to the dispenser you will add it on top of any existing candy. With a stack you will add new values on top of the existing values.
One extra method available to a Stack is the ability to "peek" at the top value without removing it. This is often necessary when using a stack, and also in a Pez dispenser. When you lift the head of the dispenser a little bit you can peek in to check what color is on top. If it is not one you like, you can still close the dispenser without having removed the candy. The same can be done with a stack.
Stacks may be implemented easily with an array or a linked-list as the underlying data structures. When drawing a stack it is far more common to draw the array version. There is one pointer of importance with a stack. This pointer is usually called the "top" pointer. It is a pointer which updates every time a "push" or a "pop" occurs, because this pointer will always point to the top of the stack. This is the pointer used to get to the stack and work with it.
The Push and Pop Operations work as the following image shows.
Enjoy, and look forward to more blog posts explaining interesting Computer Science topics.
Some very surprising news has come from Scott Guthrie in a recent blog post he has made. Visual Studio 2008 and .NET 3.5 will be shipping with the source for the base class libraries. As with a lot of the recent technology coming from Microsoft, the source code is open and not hidden away.
In the past, tools like Reflector have allowed developers to see what is going on within those libraries. These tools will no longer be as necessary. This source code is being released under the Microsoft Reference License (MS-RL). It seems Microsoft has started a new trend for itself in releasing its source code.
Debugging will now become much much easier with this code being open source. In the past developers have not been able to step into any of the base class libraries. Now that the source is open for everyone to see, people are able to go in and step through this code. This should make debugging much easier and better.
I think this is great that Microsoft is releasing more source code to the general public.
Outside of SQL it would be quite easy to number the rows returned from query, but to do so inside of the SQL is a bit more difficult. I recently wanted to be able to number the rows returned from a query in a stored procedure. I am using SQL Server 2000, so I cannot use row_number().
I was going to ask my go to SQL guy, Gregg Stark, how to do this, but while in the process of asking him for a good method of doing this, I came up with the solution. My cool trick for numbering the rows returned from a query is useful because I don't actually want to return these rows to other code. I want to store them back into my database ordered differently than the numbering, and using a table variable will allow me to do exactly what I am trying to do.
First we need to create a table variable. We will define that table as having an identity column plus any other columns we happen to need. We then insert into that table all of the values returned from our query.
declare @t table (Rank int identity(1,1), UserName nvarchar(256), Points int)
insert into @t
select UserName, sum(PointsEarned) as Points
group by UserName
After running this part we have created a table variable which contains the information we want. We can then select data out of this as if it were a normal table. In this example I am able to obtain a ranking for my users based on their earned points. This lets me store that ranking without having them stored in ranking order.
It is obviously much easier to do this in SQL 2005, but this is a very cool trick for those of us using SQL Server 2000. Let me know what you think, and if you have any cool improvements.
An interesting question came up from a few of my students while teaching my class. Some of them discovered a bug in their programs which they did not understand. They were writing a program which was doing some calculations on currency.
Computer Programmers commonly use floating point numbers, but I am sure that not all of them really understand what is going on underneath the hood. As I am sure everyone reading this knows, all data is stored in binary format on computers. In base 10 as with all numbering systems with a base, each digit is a round number in the base. The fractional amounts are what is interesting and specific to floating point numbers and not to integers.
When using floating point numbers they aren't stored in a way which is intuitive to base 10 users. As an example I will use the fractional amount 1/4. To make seeing the conversion easier I'll say that it is also 25/100 or really 2/10 + 5/100.
In a base 10 floating point number we may represent this number as the following.
If we were to write that same number in binary format we should note that it is 1/4 or really 0/2 + 1/4.
You'll want to notice here that those two numbers are not similar, and as you can probably guess, some examples would not come out quite so cleanly.
The problem which the students came across stemmed from subtracting 10 cents from some amount of money. I'll use $100.00 as my example. When the students did the calculation it worked in the following way:
100.00 - 0.1 = 99.900000000000006
That seems to not make sense, but it does make some sense. There are numbers which in base 10 will have decimal places which will extend on, and we have to round them at some point. A good example of this is 1/3 which can be written roughly as any of the following
All of those are approximations of that fractional amount. In binary we have the same type of problem, because 0.1 cannot be represented correctly in binary. This causes a problem; it will round at a certain point, and because the number isn't represented correctly, the calculation is done incorrectly. In many other languages it hides away that inaccuracy, but Python allows you to see it.
It is important to know how your floating point numbers are working underneath. Be careful. The computer doesn't speak our language.
I recently started teaching a course for the Computer Science Department at Kent State University. I am teaching a course called Introduction to Computer Programming. It is a course teaching non-computer science majors the basics of programming.
In this course the students learn simple concepts and ideas behind programming, and along the way will learn to develop simple applications. The students who take this course come from many different areas: Technology, Education, Art History, Visual Communication Design, etc.
I am enjoying teaching the course, and it is beneficial not just to the students but to me as well. As I am teaching this course I am refreshing my memory on a lot of different areas of computer science which I believe are very important to software development.
Python is the programming language of choice for this class. It has been chosen for many reasons, but a few choice ones are: Python's being a very high level language, ease of use, quick development, works with Windows, Linux, and Mac OS. We have Mac, Linux, and Windows users in the class so it is nice to use a language which is easy to develop in and works well in each of the operating systems.
In an effort to start posting more to my blog perhaps I can post a few of the interesting concepts which are applicable to all programming not just Python.
Update (24 March 2008): Steve Smith found a more reliable solution to install the SQL Server Client Tools. Once in the tools folder open the setup folder and in there is a SqlRun_Tools.msi file. If you run that it should actually install SSMS.
When I recently installed SQL Server 2005 and SQL Server Management Studio on my computer it did not install SSMS or any of the other Client Tools. When running the installation of SQL Server 2005 I followed along with the instructions. I individually selected each component to install including the Client Tools for SQL Server. When the installation finished there was no SQL Server Management Studio.
Figuring this might be a difficult thing to Google for, I asked Steve Smith if he knew how to get the client tools. He told me that just about the only way to get SSMS to install was to sacrifice a chicken and hope for luck, because there is something weird which has to be done in order to get the program to install.
Upon scouring the folders on the disc, I discovered that the default setup file is coming from a servers folder. I tried using the setup file from the tools folder. This should have worked, but I had a slight problem. Since I had told SQL Sever to install the client tools from the wrong setup file it now believed I had them installed already and would not install them.
Since the installation defaults to the Servers setup file, I never even saw the tools install. There was also no reason to even suspect one since the primary setup file claimed to be able to install the client tools.
I had to uninstall and reinstall SQL Server without the Client tools and then the setup file from the client tools would install SQL Server Management Studio. This was quite a pain, and I don't understand why the client tools are listed as options in a setup file which cannot install them. I think this is a bit crazy, but at least now when I install it I don't have this problem anymore.
I recently needed to convert hexadecimal numbers into integer numbers. So for your benefit, and for mine when I forget how to do this, I will tell you a couple of ways to convert numbers of these types. Both methods are quite simple and easy to use.
string myHexNumber = "C4FFB716";
int myIntNumber = Int32.Parse(myHexNumber, System.Globalization.NumberStyles.HexNumber);
This will convert a hexadecimal number in string format into an integer number. You could also do the following.
string myHexNumber = "C4FFB716";
int myIntNumber = Convert.ToInt32(myHexNumber, 16);
In this case you have easily converted from a hexadecimal string into an integer. If you want to convert from a base other than 16 into an integer you can pass either 2 or 8 instead of 16 to this method.
(Yes, I am aware that those are terrible variable names. This is merely an example.)
I read every blog post Scott Guthrie writes, and I intend to keep it that way. In his most recent blog post he let me know about Silverlight's 1.0 release as well as the announcement that Silverlight will be formally supported for Linux. Silverlight has seemed quite impressive so far, and I had been disappointed about Microsoft's not supporting Linux as well. I am happy to learn that the project called "Moonlight" will be able to run on 3 different browsers in Linux; Firefox, Opera, and Konqueror. As a Linux user myself I am always disappointed in the lack of Linux support given by larger companies. Flash is not very compatible with Linux, so it is quite impressive to see Microsoft assisting in the development of Moonlight.
For those of you who do not know there is an implementation of the .NET Framework referred to as Mono. It is a project in the Linux world which allows .NET code to run in Linux. I've done some development using Mono, and I've even written ASP.NET pages in Mono. So far they've done well in replicating the features provided by for .NET developers.
I think many people are eagerly anticipating the Silverlight 1.1 release which has also been mentioned as the current project Scott Guthrie's team is working on.
I am happy to know that when I write code in Silverlight anyone on any of the main 3 Operating systems should be able to see the Silverlight. If Microsoft can get some big websites using Silverlight, most people across the Internet will have Silverlight very quickly.
I recommend checking out a lot of Microsoft's webpages. I've seen a few of them, and these new Silverlight sites are quite amazing.
I've just downloaded and started trying out windows live writer, and I think it is excellent. This has got to be just about the easiest and best program for blog writing I've ever seen.
Features I love
- View Web Preview - This view actually shows me what the blog is going to look like and it actually shows it with my blog there including the content from the left column and the previous blog posts beneath this one.
- The generated html is reasonably well formed.
- I can type in my tags without having to have added them to the blog in advance.
- Plug-ins, plug-ins, and more plug-ins. I haven't looked at it but I am assuming that it is easy to write plug-ins for Live Writer.
- Inserting Images, Tables, and Maps is incredibly easy.
- I have no trouble finding what I need in the toolbar even with my plug-ins installed.
- Auto-saving my blog posts as drafts as I type.
- Insert link has a button to select a previous post so rather than finding that post somewhere and copying the link I just found it in this application.
- I can also save my links from within the insert link window.
- Formatting is simple and easy (unlike other programs which I have used).
Ok I give up. I refuse to write any more about how great this program is. Now is the time for me to go and look at some more of these plug-ins. I recommend you go and download Windows Live Writer and blog away.
The .NET System.Collections.Generic.List class is not a linked list as non-.NET users might expect. This list class is actually more like an array list than a linked list. Because of this it has some of the benefits of arrays. Simply because of the array data structure which exists within the generic list class, the class is able to achieve a constant time Count function. The basic array data structure is a collection of objects which are stored contiguously in memory, and because of this it makes counting them easy. It also makes it quite easy to index into a specific location, because you can just jump straight to the correct location in memory. With a linked list one has to traverse the list. The advantage of the linked list is that it is held together using pointers, so if you want to add nodes it is simply an update to pointers. This means that adding a collection of nodes can take constant time.
I would highly recommend against the array list if you will be adding and removing objects from this collection often. Since there is an allocated amount of space in memory for the array this means that if you need to exceed this space then you will need to create a new list. Using Big O notation the AddRange function of list will take O(n) time to complete. The n in this case is the number of elements to add. This doesn't seem to bad, but when the allotted space is exceeded the array will need to move and recreate itself with more space. This is the big performance hit. For this operation it will have O(n+m) time, because you will have to do the regular n operations plus m operations for the original data in the array.
Removing an element from an array requires a little bit of work. One reason for this is that the array data structure should never contain an empty space. This means that first you will need to perform a linear search algorithm to find the element to remove. Stepping one by one through the list. Upon reaching the element to remove, it is removed, but then all the elements after that one must be moved forward in the array so no space exists. This causes the remove function to perform in linear time.
- Capacity O(1)
- Count O(1)
- AddRange O(n) or O(n+m)
- Remove O(n)
I am planning to write of series of little bits of stuff. If you catch any mistakes in any of this series please comment on the correction ASAP. I don't want to be passing along incorrect information.