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 it and strongly encourage a 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 is 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
Posted in Programming, AI at 9:18 pm by Nick
For a while now I’ve questioned if I wanted to do programming or Computer Science type stuff for a living. I always get very restless with the present and usually try to make bigger and better plans. Well, I can say that after a period of time with no programming, I’ve fallen in love with it again.
What has made me rethink so much? AI. The topic, and my class. The homework and topics are just so interesting, so mentally stimulating. And, better yet, the homework is interesting, and often challenging. It leaves me feeling accomplished at the end, has me boggled in the beginning, and drives me forward during the process itself.
I’ve developed two very nice programs for this class so far. One uses a variety of uninformed search techniques to solve a jewel puzzle. The other uses Minimax to give the optimal move for a tic-tac-toe variation where you can place an X or an O each move. You can find the code and extensive readme files below:
Jewel Game - http://ew.xidus.net/download/ai/jewel/
Tic-Tac-Toe variation - http://ew.xidus.net/download/ai/ttt/
Permalink
09.05.07
Posted in Programming, DBMS at 11:41 pm by Nick
I sat down tonight to work on my first programming assignment for a class this year. I was excited merely to be coding again. This assignment was a bit of a refresher of C and some of its oddities (and pains due to string handling). It was nice to have something manageable and rather non-time consuming to kick things off. As I wrote I could tell how rusty I was, not recalling the arguments for some standard file manipulation functions. I rewrote one function two or three times. All would work, but in my mind I kept changing how I thought the overall implementation should go. In the end I got exactly what I wanted, and back when I was heavy into programming I’m sure I could have done it exactly the same or better in less time and less rewriting since I wouldn’t have to change my implementation ideas several times.
The assignment is, basically, to create a minidatabase system using files. You use the given program to generate an index file of names and file offsets of the database so you can lookup phone numbers. My program scans the index file to match the names to get the offset to lookup the phone number for display.
Anywho, you can check the assignment at http://cns2.uni.edu/~okane/114/#asgn1, supposing the link is still good.
My code, as always, is posted. You can view it at http://ew.xidus.net/download/dbms/1/
Permalink
08.15.07
Posted in General, School, College at 4:49 pm by Nick
I was mixed with emotions today as I spent most of my money on hand to buy $520 worth of textbooks (I’m still missing two). I’m excited, and I’ve already been flipping through the pages of several as work winds down. However, I can’t help but feel cheated by the system.
I figured since I get $450 from ROTC to buy books and supplies I’d buy all new books. This is all well and good, but ROTC doesn’t give me any money for a while. Whats more, the refund check I was planning to use to buy the books was not mailed until today, meaning I must wait for the snail mail check to arrive to alleviate some financial stresses.
Even so, I’m very pleased. And excited. Almost giddy in fact. I haven’t been able to do too much this summer in the ways of personal interest or hobbies (my computer has died twice now, along with most of the data, and I can’t replace it for a little while yet), but I’m very happy to finally be starting school again. But not just school…
College.
Finally! At last! My home away from home, full time. I can again resume the daily rituals of homework, tests, and absorbing knowledge. If family difficulties can stay out of the way perhaps I can regain my academic status and keep it how it should be. I have a good classes, a great job, and a wonderful college that provides both.
Monday can’t come soon enough.
Permalink
07.30.07
Posted in General at 2:32 pm by Nick
After months of trivial happenings and computer neglect I am happy to say I am back. I doubt I will blog as frequently as I did in the past, but I find some blogging is better then not at all. I’ve been bottled up for a while now, feeling like I had no place to say what I really wanted to say, and suddenly I was reminded that was why I started this blog in the first place.
As the academic season pulls into full swing I’m sure I will have loads to say. It is rather hard to even contain my excitement sitting here, knowing I will finally be a full time college student. I’ve never looked forward to anything else this much in my life. Yet these next few weeks will be busy as I attempt to get everything (including myself) into shape for a rigorous learning experience.
Permalink
03.18.07
Posted in General at 2:42 pm by Nick
So, Mexico was awesome. Seriously. Amazing weather, great water, awesome resort. It was excellent. Most days involved lots of sitting and thinking about doing something, usually spending several hours in a hammock.
While in Mexico I went…
- hiking
- rappelling
- zip lining
- canoing
- kayaking
- jet skiing
- para sailing
- swimming with dolphins
- mini-golfing
- swimming in an amazing underground reservoir.
I also…
- played giant chess
- climbed the tallest Mayan temple and examined a few others
- slept and ate normal amounts of food
- sat on the pier just to listen to the waves and look at the sky
- walked on the beach just to feel the wet sand in between my toes
- spent a lot of time thinking
- played poker, hearts, bullshit, and phase 10 with Mandy and her parents
Permalink
« Previous entries · Next entries »