06.21.08
Posted in General, Thoughts at 2:36 am by Nick
Why does this always happen?
It has been many months. Almost a year, actually, since it has ever been like this. Not since the I lived with the guys. Dwayne and I used to sit out on the porch for entire nights just talking. I’d go on walks with Paul and discuss things. I’d go on midnight walks with Lisa, and sometimes we would bring other people. And we would actually talk about meaningful things. But that all went away…
Tell me, is it true that it is better to have loved and lost then to have never loved at all? To have a taste of love is enchanting, and enlightening. But no one tells you that you can’t go back. You will miss it if it goes. If you never love at all you can’t miss it, but you don’t know how to fill that void within you.
I’ve wondered what I will miss the most. It hits me hard every time I go to McDonalds or Panera, and every time I talk to my coworkers. The evidence is everywhere. I may miss being in a relationship and having someone to hold onto, but there is something I miss more, and it takes me by surprise quite often. I miss being a dad. I miss doing stuff as a small family unit. Sure, it isn’t always fun, but its hard to find that type of satisfaction anywhere else. I will miss the little kids growing up around me. I will miss watching them learn new things. I will miss laughing and playing with them. It is yet another example of me rushing into life and being completely disappointed when it doesn’t move as fast as I would like. I have a feeling my own dad often feels this way, and this knowledge makes me deeply hurt and sad. Time only moves one direction, and thus, we move away more and more.
With that comes another realization: the faster I move the faster I get towards the end of the line. Back when school was in session I had a freshman ask me how I knew so much more then him even though we were the same age. I proceeded to tell him it was a difference of time, priority, and life events. As I think more and more, I realize the advice I give is only applicable to people like myself. I may tout many ways to get ahead in financial security, college, or other future goals, but what am I sacrificing? I know now that I would sacrifice my knowledge if it would send me back in time and give me a normal life these past few years. Talking with the other interns only makes me realize how much I have truly missed out on life in many respects.
I can’t help but wonder constantly now. It has been a while since I’ve been this curious and this thoughtful. Three hundred sixty three days together. And now… now its all over. What’s more is that the decision was made while I’m two hundred miles away from home, three hundred away from family, and isolated in a new town with a new job.
It occurred to me when I decided to buy some cigarillos and take them up to my watching post in the park – I am far along the journey back to who I used to be. Shifting from ENFJ to INTJ, the need to make sense out of everything… I don’t know if that is good or bad. I can’t help but feel that even though I am in the midst of civilization, with large towns on the horizon, people of all backgrounds and races coming and going over head, that I am alone here. There is no girl waiting for me back in Cedar Falls. There is no family there… just many friends who have slipped away in the steam of life. I have many friends at work, and a lot of resources to draw on, but when the work day is done I return to my home only to figure out what I should eat – alone. What I should do with my time – alone. I’ve never had so much time for myself.
I’m not complaining. It merely baffles me to have such a sudden abrupt change to my lifestyle. It’s the weekend and I’m at a loss. There is no computer for me to jump and check Facebook or other networking tools. I can’t call anyone to do anything. I’ve lost my interface with the world. I can sleep in, read, program, and explore. However, I don’t know where to go from here.
Something is missing. When feelings revert to this state it is obvious that something is missing. One stage of life has completed and another is beginning. I’m in transition from one meaningful experience to the next. I know this feeling. It is me being lost and losing my resolution of the future. It is me pondering existence and wondering what life will be like in a few years. Most importantly, it is me looking for something to fill this chasm I feel. I need to do something that means something to me. I’ve been thrust back into the wandering slipstream and I’m looking for something to hold on to. I watch so many people do so many great things, and I can’t help but want that as well.
I think, perhaps, when I get back to CF for good I will do two things. One, I will actively participate in more clubs. Computer Club sort of died last year, but I hope it will come about this year. I also hope to get more involved within the Economics Club. More importantly, I think I will get involved in the Big Brother, Big Sister mentor program (or its equivalent). I think it will help me evolve more as a person, and perhaps do someone else some good as well. And maybe, just maybe, it will satisfy my parental angst.
I do have some bigger decisions to make, however. I like it here, and it makes me wonder if I should work on completing my Computer Science degree as fast as possible. Dropping my second major would be a big deal, but it might be worth it. It is hard to say at this point. I’ve also considered transferring to the University of Minnesota, but that would never really happen. Most days I wish I could just work here full time and finish my degree eventually at the U of M.
Another day. Another dream.
Permalink
06.11.08
Posted in Internship at 9:18 pm by Nick
Wow. How time flies when you are working. I finally got onto the net and I already have to go. Here is a small recap before I’m booted from Panera.
Monday:
Orientation. I got there on time and with a full stomach, and thank goodness I did! I was moving, talking, and reading non stop the whole day (minus lunch). I got to meet my team mates, manager, and have a lot of orientation time with Wayne Dahmes (HR Manager). I am the last intern to join, so I was going through it all one on one, which made it far more interesting and amusing. I thoroughly enjoyed myself.
The only problem was the night before all of this. I had slept in too long on Sunday, and when it was around 11:30pm I was not tired. Instead, I was bursting with energy. I had put off running all weekend because I didn’t have the gear for it, but I had gone to Kohl’s and gotten shoes and what not. I went running (and walking 
). I explored a lot. I did find a good spot in the park relatively close to where I live that I can go sit and the end. Its great. I got back around 1am and I still couldn’t sleep. I think I fell asleep around 2:30am, which left me very tired on my first day. Luckily Lockheed Martin is a pretty high energy and fast paced work environment (at least one day one).
When I got home I had planned on going out to buy more work clothes (because I felt far more dressy then I needed to be and because I didn’t have many things to wear). Instead I passed out and slept for four hours. I then woke up and decided it was time for food. I drove southwest of my residence to McDonalds. I decided to take a road to see where it led me and around 11:15 I realized I was twenty miles NORTH EAST of my residence, and I had found Verizon, which I couldn’t find when I was actually looking for it. I didn’t get back until 11:30pm or so, and again I went to bed late.
Tuesday/Wednesday
I was finally in enough of the system on Tuesday to learn about the fantastic learning experience of compliance training. LM requires every new hire/intern to take certain courses within their first week, two weeks, 30 days, etc. And this goes on for every employee for their entire time at the company. Wayne was telling me about the training he still had to do (some of it is renewable annually). I managed to get done with eight compliance training tests (which are easy, but time consuming and quite uninteresting). I’ve been lucky enough to be put under the wing of a co-worker, Paul. Each day has worked out to (roughly) having meetings in the morning and/or perusing the Common ARTS lab to learn things and get to know my team (Ricky and Paul anyway) and then in the afternoon I actually sit at my desk and do compliance training or various setup/required things.
Their computer system, while silly at times, is better then UNI’s in general. Your active directory password gets you into everything, and the TSS Portal (which gets you basically everywhere) is automatically known for your ID when you log in on the intranet. The only things that require other passwords are the timecard system and any passwords you require for lab machines / work assignments. Its wonderful not having one for email/web access, one for timecards and work functionality, one for my active directory (AD) work account, one for my AD school account, and probably others I’m forgetting.
I have also been lucky enough to start on a short week. Here in Eagan we have Flextime 9/80, meaning we choose our hours with our manager (I chose standard 8-5:30pm) and we work 9 hours, then we receive every other Friday off. I also found out we are payed weekly, which will greatly alleviate some financial burdens (I earn as much in one week as I used to during a whole month during school).
I’ve been getting more sleep. I’ve been eating more. I’ve been exercising. And, best of it all, I get up and look forward to working for the next nine hours! It is great fun, though the programming bit hasn’t really kicked in. The code surely is manageable, the only thing I’m worried about is learning the system enough to be a capable bug tracker, and then learning the CRAZY processes required for logging the errors. I think it will come together nicely.
I like it at Lockheed. Though this is still week one. But how can I dislike it when I get my first Friday all to myself? I don’t even know what I’ll do with myself…. laundry and other mundane things I suppose.
Well, hopefully I can stay awake long enough to drive home and crawl into the bed. I’ll try to update more this weekend.
Permalink
06.08.08
Posted in Internship at 2:31 pm by Nick
Sad start again today. Woke up at 8:30, went back to sleep. Woke up at 10:30, went back to sleep. And I proceeded to do so for every half hour until my stomach finally decided enough was enough, nearly 24 hours without food was unacceptable. After randomly moving around, I finally got the will to get up and drive around. I know my way around most of Eagan that I care to explore. There are only a few vital roads. Still, it was tricky to wind my way into Brueger’s parking lot. In the process I did discover where the Eagan Transit Station is,which will probably come in handy at least once (even if I just get on to ride it around for the hell of it).
Brueger’s has better wireless. Not nearly as many people and its faster because there is no web filter. They are only open until five, so I expect this will be a short post. Still on my list of things to do are pay Verizon a visit, buy some decent shorts at Kohl’s, and hop on Panera’s wireless (or maybe the Best Westerns) to see if I can’t take advantage of the rest of AV weekend on World of Warcraft.
I spent much of last night programming, and it went well. However, I realized that without the web I was without any real good PHP reference (even though I brought two books on it) so I was, for quite a while, running into many strange errors that were simple to fix but hard for me to figure out. Luckily I’ve gotten it down. Sadly the read line functions don’t remove line endings by default, and I can’t seem to find any other function that will do it for me (it seems like trim should be able to do it, but I guess \r and \n aren’t considered whitespace?).
Hopefully tomorrow will go well and I’ll have some interesting things to talk about. It will be interesting to see what my first day at Lockheed Martin brings.
Permalink
06.07.08
Posted in Internship at 6:04 pm by Nick
Exploration!
Sadly I didn’t get up until noon. I didn’t get to sleep as early as I would have liked (but I did read my -ENTIRE- intro packed and know far more about the benefits salaried employees receive then I should, and I’m pretty sure I signed my soul to the devil on one of the hundred forms I signed). It might have been because I was in a new place. I’m not really sure. But as soon as I fell asleep I was definitely out like a light.
I didn’t really feel the motivation to get out of bed and explore, but it was pretty necessary. Once I got out and about I started feeling better about it and was enjoying just moving around outside. I plan to do more driving around too, but I couldn’t pass up my chance to hit the net when I found Panera. After my usual poking around I couldn’t decide what to do exactly. I had picked up a MicroSD card for my cell phone to see if I could get some music on it only to waste an hour finding out I need (surprise surprise) Verizon’s special kit to get it to work. I plan to pay them a visit, because I’m not buying music from VCast and I wan’t music for running (and since my phone supports it, it will save me ~$150 for the same amount of space). Luckily my laptop has a n SD card reader. This technology is new to me and it is amazing! Up to 4gb on such a small chip. It makes me wonder so much about how it stores every thing. I wont even be mad if the Verizon kit comes with a MicroSD chip because that will enable me to use this one for other things. Its smaller and even more efficient then USB flash drives, though not every computer has a card reader (such as my computer at home). I also decided to play the DVD given to me by Lockheed Martin (LM), only to find WMP was missing the decoder and there was no real easy fix for it since it wasn’t an MPEG2 encoder. I originally found it annoying that LM had produced an relatively incompatible DVD for its interns, but I found it more and more amusing that it was almost like an unintended introductory challenge. If the intern couldn’t view the DVD then certainly they don’t have the problem solving capabilities required for the job. After a few minutes of work (that would have been impossible without the web) it was fixed. The DVD was inspiring, but kind of a let down. It had a lot of cool graphics based on their accomplishments though.
I realized last night during my unpacking that I was running low on just about all of my essentials (shampoo, toothpaste, etc), so I decided to visit WalMart as well. It is beyond backwards from ours (not to mention it isn’t of the “Super” variety), but the staff looked very studious and well trained, always making sure to direct people to their registers if they were not busy or standing at stations to help direct people. It gets far more traffic then ours does.
I’m not sure what I will do tomorrow. I’m sure I will come to Panera and use the wireless, but I don’t have too much else to do. I guess now would be a good time to get started on making up Microecon, and there is a lot of work to be done there. Tonight I will finish my incomplete in PHP programming.
Anywho, I think I’ll play some WoW in the mean time. I’m hoping these posts will become slightly more exciting as I start work, but I have to keep in mind too that I’m allowed to say almost nothing about what I’m working on. I’m curious what security clearance I actually received…
Permalink
Posted in Internship at 5:47 pm by Nick
I didn’t really come up with the idea to log my experience here in Minnesota until today, but I will write about the happenings yesterday. As I do not have broadband access (and I will not succumb to the horror of dialup), my entries will probably be infrequent (depending on how Panera feels ).
—-
The last two days were pretty insane. I feel like I could have done more, but I’m happy with the amount of things I accomplished before leaving for Minnesota. For the unknowing, I will be a software engineer intern for Lockheed Martin Transportation and Security Solutions in Eagan, MN. I start June 9th, will be working 9 hour days (but I have every other Friday off) and I won’t be back until August.
I was to leave Thursday but my employment package did not come. I postponed leaving until about 6:40pm on Friday, which was a blessing and a curse. Spending some time in my freshly cleaned apartment was great, but then of course I had to leave it only to drive 3 hours and 20 minutes or so. I drove it in one sitting since I was not hungry, I didn’t have to go to the bathroom, and I wasn’t tired. Even the weather was good. So instead of ruining my groove I just did the driving in one fell swoop.
The place I live is great (minus the fact that is lacks broadband internet). I’m trying to view the lack of internet as a good thing since it means when I leave the place that has internet, I will be cutting my computer connection with the world. This should leave me more time for reading, sleeping, and offline activity (Panera is my wireless hub of choice, but they close at 9pm). I also live just down the road from a park, so I’m hoping to get back into exercising.
Eagan is a great place. It ranked #12 on Money’s list of top 100 cities to live in in 2006 (Apple Valley ranked high in 2007, and it is just a ways to the south). I am located in between St. Paul and Minneapolis, just across the lakes from both the international airport and the Mall of America. I’m guessing this is how Cedar Falls will look when it gets up to ~60k people. Every road is four lanes with turning lanes, and its easy to get everywhere because the roads are easy to follow (and the speed limit is 45 everywhere it seems). That said, Yankee Doodle road will take me to WalMart, Kohls, and a slew of other shops on its south side, and on the north side is another plaza with my Panera that I plan to visit regularly. Target isn’t far away either. There is a lot of culture and a thousand possible things to do (not to mention the possibilities for entertainment that the twin cities present).
I don’t plan to take advantage of the entertainment too much though. I will go on intern outings, but other then that I plan to get into a nice routine of sleeping a lot, running, eating a good breakfast, working, interneting/dinnering, and then returning home for some peace and quiet. But not too quiet. I miss having my fans, but I live next to many busy high ways and the airport, so there is plenty (but not too much!) background noise to keep me happy.
Permalink
03.06.08
Posted in School, College, Computer Science, Thoughts at 5:50 pm by Nick
In recent times it has been very hard for me to attend class and get things done. This is due mainly to a troubling and complex family and living situation. Thus, I have decided to withdraw from two of my classes and work harder towards not marring up my academic record then I have already. Along with this, I am going to be moving during spring break.
However, I must say I am absolutely unimpressed (and disappointed) with some parts of my education. I know it may feel like an attack, but it should probably be heard. It is no news to the Computer Science program at UNI that enrollment is down and there are many people who switch majors. After talking to -many- CS majors (mostly freshman), I have decided it has little to do with the course content. If I could choose, there would be many things I would change based on my personal experience and feedback.
The first thing I would change would be our introductory courses. I know this is talked about and debated a lot. But what we have taught recently, Ada, C/C++, and Java, is a terrible choice. It is no reason our majors are running away! None of these languages are terribly user friendly for beginners. To exacerbate the problems, we thrust our students in without ever telling them what it will be used for, how it will be used, or why we use those particular languages. We don’t mention other alternatives. Why is this? Why do we not teach introductory classes with dynamic typing, like PHP or Ruby. I have never heard more complaints then about students who have no idea what the different between certain data types are. In C/C++ there are all kinds of exceptions, like using char’s as small integers, unsigned and signed, and C-style strings vs. C++ string data type. How are the students supposed to figure that all out? Ada is a language designed initially for embedded systems by the Department of Defense. That line alone is enough to scare freshman. There is nothing simple in these languages. So why do we teach them in our introductory courses? Our degree program already requires an extra Comp Sci general class. Why not save these industrial languages for them?
Students need to learn the simplest things first. These languages were not designed to be simple. Yes, if you know how to use them they are not as complicated as they first seem. But there is no reason to think a freshman in computer science, with no previous programming background, will understand the concept of passing the address of data to a function. I know several good programmers who still do not completely understand pointers. To teach the simplest thing possible, we need the language with the least amount of baggage. Something you can get using quickly, and without a lot of quirks. In C++, you need includes, a main function, knowledge of data types and operators before you can do anything. In dynamic typed interpreted language, you need basic operator knowledge, and that is all.
And yet I fear we cannot change our introductory languages because we have our two full professors teaching our introductory courses. Never mind the fact that the C/C++ students learn C, not C++. C++ comes later and is merely brushed on. I understand better then most the overlap between the languages, but there are some huge differences. I think students in the C++ section should be taught about C-style strings (that is, character arrays) but they should be taught about the more commonly used (and far more useful) STL string data type.
I strongly believe our faculty grew up when computer science was brand new. They all have fantastic and interesting stories. But this age is different. Our upcoming CS students are different. The times have changed. Computer science is no longer ‘new’, it is now ‘young’. The students will not spend all of their nights up late, huddled over their computer attempting to fix a broken program. That type of dedication is gone. It is the zeal of the new and unexplored. While there is plenty to explore in CS still, freshman will no longer be the ones doing it. We have a new computer science generation, and our program needs to realize this. We will continue to see low enrollment and a high drop rate if something doesn’t change. You cannot scare away all of the students by making them feel dumb and inferior because they cannot remember complicated syntax and expect your academic program to live.
Our introductory courses need to teach different things. Never, in any class I have taken at UNI, has a professor started out a class by mentioning why we should learn what we are learning. They have never mentioned it’s use or importance. In our introductory courses we jumped right in, delving into logical algebra and programming methods, but no one said what we needed to learn the algebra or methods for. I was lucky enough to know how to apply my skills already. Most students don’t. They have no drive because they are merely frustrated by everything they are learning. And who wants to walk up to a professor and admit they have no idea how to compute square roots using for loops? No one. And that is a big problem. I think we should promote a different way of learning. Students find it extremely hard to take program specifications and write a program from scratch. It is hard, and advanced programmers do it. Not new ones. We should develop programs for our freshman to modify, so they can see why code works and how their changes will reflect it. We should promote programming in small steps. If you write a program from scratch, it won’t work the first time. It never does. Maybe because it was late and you initialized your data wrong, or perhaps you thought through your packet filling the wrong way. Whatever the cause, if a student writes it from scratch and it doesn’t work, it is a moral failure. They aren’t used to it. They don’t understand that even the best programmers don’t write bug-free code.
Our students are not motivated. As I listen to classes, people, and friends talk about computer science, they are NEVER talking about what cool project they are working on. They don’t talk about things they are looking into, nor are they talking about things they aspire to make. They talk about how they failed to complete the homework because they had no idea where to start. They don’t have the time to work on something they are actually interested in because they spent four hours trying to fix a program that was probably never going to work the way they wrote it in the first place.
There are two things that bother me the most:
One, the fact that our major is long and requires so much math. Yes, I understand math is great. Yes, I understand we have a science degree and it will not be short because it requires training. But our degree provides no flexibility. If you want to reasonably complete it, you will work your ass off or take a more sane five year plan. I’m still unsure what is with the emphasis on math. I understand it -was- the foundation of our program. And I know it can help understanding, or expand thinking. But seriously, the last math class I technically completed was Geometry. My family life went to hell during Advanced Algebra and Trig, so I never completed the second semester, and I got a C in the first. I am not ashamed to admit this. It proves you do not -NEED- math to succeed in computer science. In fact, apart from simple arithmetic, math is largely unneeded unless you are working on math related problems. Discrete structures is a great class and very applicable. But you don’t need calculus to do it. I got an A- in it, merely missing the A by a percent or two. As a software engineer I’m pretty sure you will rarely deal with real math problems. So what is the math portion of our degree really for? Why not dump and is strongly encourage mathematics minors? If you do the courses just right, our major is only one or two classes away from a math minor. But, of course, there is no real time to take those classes to get it if you want to graduate in four years.
And two, you never have time to work on projects that matter to you unless you are completely uninvolved on campus and jobless. Most (not all) professors are not flexible enough to allow freedom in their homework. Rarely can I think of times when I could pick homework that was interesting to me. I have gotten more then most, that is for sure. In our introductory classes, students may not know what interests them programming wise. But they certainly will not be interested in mundane examples. Not all students will want to write stuff on their own. But we should encourage them to pick homework that will relate to the topic at hand and help them do it. Everyone knows and can enjoy tic-tac-toe, and it is not hard to program, even for beginners. It demonstrates many programming techniques, such as input/ouput, array manipulation, or potentially AI or even OOD. Yet never has gaming been brought up in any of my classes, except for AI where game playing as part of the curriculum. In fact, in many of my classes, gaming is frowned upon. Never mind the fact that gaming is perhaps the easiest way to relate the material to the current students, and demonstrate any technique, be it lists, trees, arrays, classes, or OOD.
This all bugs me to the point of wanting to switch majors. I won’t, but it seems like a damn good idea. Economics is simple. They take the core of what you need and give it in eighteen hours. Then you choose eighteen more hours of education, putting what you want to learn in your hands. This gives you room in your degree to deal with bad classes, or explore things you are interested in. While I’m not saying computer science can be simplified to thirty six credit hours, I think the BS could provide far more flexibility then it does. Since we do not offer Software Engineering, nor anything else as a major, there is very little point in requiring students to pick an emphasis beyond Foundation courses. Let students take what they are interested in. They will look for jobs they are interested in, and then they will know more of what they need to know for their jobs. I have no real special interest in Information Science, it just seemed like the lesser of all of the evils that are our choices. I wanted to learn about databases, but none of the other courses seem interesting. I think the foundation courses are a good idea, but they should be expanded. Perhaps take a primary course from each section (Info Storage and Ret, Software Engineering, Networking) and put it in the foundations, then remove the emphasis requirements. This would require students to fulfill a requirement and pursue whatever path they would like without punishing them if they decide to change. Maybe students want experience in Real Time Embedded Systems, but have no interest in testing or project management. Currently, students will probably not pursue their desire to learn about real time embedded systems because they will be devoting their emphasis to something they only have one real interest in.
Note: This IS a first draft and WILL be revised.
Permalink
11.30.07
Posted in Programming, Computer Science, Computer Science III at 1:45 am by Nick
While researching Red-Black trees during my original coding homework sometime ago I stumbled upon the Arne Anderson (AA) tree. Looking back I don’t see why I didn’t push off the Red-Black trees and go with AA Trees. Who knows? Here is an analysis of my work with AA Trees:
AA Tree’s are very similar to Red-Black trees. They add one rule in addition to the traditional Red-Black tree rules, and that is that a Red node may only be a Right child. This eliminates a substantial amount of special cases, making this algorithm far easier to implement. Interestingly enough, AA trees perform as well as Red-Black trees. Since the AA algorithm is simpler, it takes less time to compute, but since it makes more rotations then Red-Black trees the performance evens out. Due to the nature of the algorithm (which shapes the tree), AA trees also tend to have better retrieval times then Red-Black trees. For those unfamiliar with the tree (which is probably most people), there are only two operations required for maintaining the tree (compared to the red-black tree’s five). A right rotation occurs when an insertion or deletion creates a red left child; this is known as a Skew. Split’s perform a (conditional) left rotation when a function creates two red links in a row.
My program implements a string to integer map using AA Trees. As an example, it counts word frequencies in a file. The string handling is rather rudimentary (converts to lower case and tosses out punctuation), so some of the words are kind of funky looking, but it works pretty well. I was surprised at how fast this program ran. I didn’t time it exactly, but it scanned a 11.7MB text file full of text in less than 30 seconds.
During my coding I hit several roadblocks. Coding the algorithm went well, but when I was programming my insertion function it all went screwy. I rewrote it three or four times only to realize that my initialization in my constructor was wrong (while cascading assignments for pointers I forgot the NULL at the end). While stepping through the program for an hour using GDB, I was rather clueless as to what was going on. Everything was wrong. None of the pointers were right, none had key data stored, and it crashed randomly. After fixing this I ran into an error with Skew running on my root pointer, which should never happen. Once I got passed these problems all remaining changes were pretty cosmetic.
I would love to package this up using templates and reuse this tree implementation elsewhere. It is pretty applicable, but again, the STL has a very good built-in map class.
About the code:
I did not flesh this code out much. The tree lacks a deletion function, and I show no examples of how to retrieve a word’s count using Lookup, though it is pretty straight forward. I use Lookup primarily as a wrapper for Insert (and for clarity), differentiating the names for their intended use within the code. There is also a large amount of pointer manipulation in this code, which I tried to document, but it may still be confusing to those new to pointers. Interestingly enough, while the algorithm itself contains a significant amount of references to red and black nodes (which this algorithm is based on), there is no reference to such in the code. The code assumes all Right links are red nodes, and instead everything is based off of the “level” of a node, which is the number of left links that must be taken to reach a NULL pointer.
It comes with a few text files as well. Data.txt is a smaller text file I used to test, being about 500KB or so, which resulted in out.txt. The file test.txt was a small test, and bigout.txt is the result of scanning the whole 11.7MB file.
Code -> http://ew.xidus.net/download/cs3/tree
Note: A wonderful summary, analysis, and comparison between some of the most common efficient data types can be found at http://www.upgrade-cepis.org/issues/2004/5/up5-5Mosaic.pdf. I recommend at least a glance at the diagrams. It is obvious that AA trees are outperformed on many levels, but they hold steady and beat data types on various challenges. Considering the simplicity of the algorithm and ease of implementation compared to the others, I’d say its far more useful.
Permalink
11.26.07
Posted in Programming, Computer Science, Computer Science III at 11:31 pm by Nick
It was interesting reading about a data type I had been using ever since I began coding. Little did I know that SMAUG and SWR made use of sequentially linked lists! Experimenting with lists has been fun and interesting. Once I got into programming it was hard to stop adding features. Lists are very easy to manipulate, and once the basics are in its easy to add things.
What I ended up with after this assignment was a class that replicated most features of STL’s built-in list class. It is templated to allow for any data type, and given a couple tests it seemed to work well. I purposefully avoided the use of any STL data types to drive the class, as that would be counter productive in the learning and showing of knowledge about lists.
I experienced many oddities with lists while I programed. After, again, fighting with template syntax, and I had an initial implementation I realized I was indeed missing a vital feature of a list data type: the ability to traverse it. When I gave the Element class the ability to cough up its pointers, it broke all list class functions that needed to set them since that data was now private. I am not totally happy with this implementation because it gives everyone the ability to modify a given elements pointers, not just its data. This is not good since anyone using those functions could potentially screw up the list, and things like that can be very, very hard to track down (nothing like spending hours stepping through a program to evaluate pointers at every step).
However, this was a very vital feature, so once I added it I found I was able to do quite a bit more with the list. An interesting side effect of my implementation is that you can add and remove things to the list without adversely affecting any current iteration (supposing some pointers are handled correctly). I demonstrate this slightly in the example programs provided by inserting an element into a list when a certain point is reached (and then that element is eventually processed like the rest).
When implementing the ability to traverse the list I found it made the code far more obscure. Lines that were already strange looking, like:
x->next->prev = x->prev;
became
(x->GetNext())->SetPrev(x->GetPrev());
And that, as far as readability of code, is very bad. However, its fairly simple to reason out, and with comments I feel no need to separate it into multiple lines of code. Also, each member function of the class is pretty specific and short, and they would normally appear multiple times within code, so each function is inline. I have no real way to tell if this is faster then outline code (is that even what its called?), but it seems reasonable that it should be inline.
Note: The code below is separated into different files for readability. It should be noted that all the code in list.h and list.cpp -NEED- to be in whatever file they will be used by. Therefore, all of the test files (main_int.cpp and main_string.cpp) would need this code copied and pasted into them to work. This has to do with the nature of how C++ uses templates and the code must be present in the source file it is used by. Due to the way I program this is awfully inconvenient, as I love my larger number of smaller file type projects. Also, the output from the two given test programs is provided in text format for examination.
Code -> http://ew.xidus.net/download/cs3/list
Permalink
11.20.07
Posted in Programming, Computer Science, Computer Science III at 4:53 pm by Nick
While I am in the midst of Thanksgiving break from school, I find myself not taking a break at all. I’m working, and when not working I’m attempting to get school work done, as I have much to do (as always).
In any event, I decided to jump into hashing, and hash tables more specifically. Hash tables are something I’m very used to because when I started programming with SMAUG it had a hash table built into it (if you have a thousand instances of a mob it is an awful waste of space to allocate the same string a thousand times). So I learned the in’s and out’s required to use it, but like all of my knowledge at the time, I knew how to make it work without knowing -why- it worked. That has changed.
Data Structure Techniques by Thomas A. Standish had a lot of good information on hash tables. It taught me many things, even with my preconceived notions of what a hash table did and what its purpose was. I never even considered adding a key by a method other then division (modulo). His text on the multiplicative method is very interesting, though it seems a little too narrow to be useful in a large number of instances.
I initially had trouble testing my different hashing functions for one very simple reason: my computer. Since my last computer bit the dust (the eMachine lasted 5 years with no problems, I’d say thats pretty good quality), I’ve finally invested the money into a -real- computer (more on that here). Simply put, with the original test cases my independent, worst-case variable, the list structure, performed so fast I had to come up with another solution.
As I was in node mood to figure out and implement the use of a high performance timer (known as QueryPerformanceCounter on Windows), I merely used google and grabbed an easy implementation (doesn’t get easier then one structure!). After implementing that, I increased the number of items hashed by about 100 fold, bring most of the searches up to 15 million items. This gave a sufficient look at the differences between hashing functions and their performance compared to a list.
To compare hash functions, I went to Wikipedia (I think) and grabbed a recommended hash function, which happened to be Jenkin’s One-At-A-Time Hash. I then implemented two more very basic hashes. One was based off the SMAUG version, which hashes a string based on its length. The other is based on the first letter of the string. Oddly enough I named that CaseHash, when really it has nothing to do with the case of the first letter, but the letter itself.
The data was rather astounding. Jenkin’s hash almost always performed as well as or better then all other methods. Sometimes it would take a little longer (we are talking less then hundredths of a second longer though), but almost always was the top performer. Note in the final screen shot how it outperforms the other has functions, or performs as well. When doing a particularly hard lookup it would perform much, much better.
Provided via the link below is the source and a couple of screen shots (some have different output because I was busy tinkering). The first time is provided using the time() function, the second time is using the performance timer (with a precision of 15).
Code and screen shots -> http://ew.xidus.net/download/cs3/hash
Notes:
1) I intended for this hash table implementation to be far more flexible, but after fighting with templates for quite some time I decided to merely call it quits and hard code the strings in.
2) In screen shots 1,2, and 3 it appears to be sorting numbers. These are not numbers, but in fact strings that contain incrementing numbers. This was the product of the program I used to generate the data.
3) The programs I used to generate the data are also included in the link above. They are small and simple.
4) All code listed above is public domain. Use it as you like, or don’t use it. Your choice.
Permalink
10.08.07
Posted in General at 9:33 pm by Nick
I’ve often heard things come in three’s, which has left me scared out of my mind for one reason lately. After sitting through the agony of Vacancy and The Tomb, I cannot stand another crappy movie!
Vacancy looked like a relatively promising, albeit somewhat unoriginal movie. With Luke Wilson and Kate Beckinsale, I thought it couldn’t be too bad if it was, at least they had two quality actors. Wow. I was so, so wrong. The best part is at the beginning when Luke Wilson maneuvers the car in a 180 degree turnaround to avoid hitting a raccoon. Yup, this movie is that lame. Luke and Kate fight through the whole movie, which I guess counts for plot development. However, if I wanted to listen to a married couple bicker I’d just take off my head phones while using my computer. I don’t want to pay money to watch other peoples paltry problems. The movie is predictable and unexciting. If you can, avoid watching this movie. On the other hand, if you have easily scared girls on hand, chances are they will still get freaked out by this movie, so if they want to rent it go ahead and let them.
The Tomb was quite possibly worse. It is supposedly based on HP Lovecraft’s book, which is why I thought it might be interesting. In short, it wasn’t. Two people are trapped in a warehouse with apparently no way to escape. Nothing tries to kill them, or hurt them. They find people who die within minutes of talking to them, apparently all having axe wounds that enable them to live for fixed periods of time. The end doesn’t make sense, and the main bad guy is repeatedly seen riding a horse. Whats the riddle? He wants them to guess his name! As far as I can tell, it has nothing to do with HP Lovecraft except that the main bad guy is supposedly obsessed with Lovecraft’s book. After seeing this movie, I have determined I must read The Tomb and see if there is any relation at all to this crappy movie. There is no excitement or drama, and any action is very lame. For a Lionsgate film, I was absolutely 100% disappointed. Whoever wrong this script was an idiot, and whoever decided to produce this film, let alone direct it, was insane.
Luckily these crappy movies were followed up by Apocalypto. This movie was very well done. The scenery is beautiful, the story incredible, and overall was a stunning (and brutally truthful) movie.
I think I’m done being a movie critic.
Permalink
« Previous entries ·
