For an anti-plagiarism application I developed about a year ago, I needed a way to calculate the similarity between two strings. I wasn’t sure how to go about doing this at first, but then I came across the Levenshtein Distance Algorithm which gets the job done well. In this example, I’ll show you my Distance class implementing the Levenshtein Distance Algorithm, and how to use it to compare strings (specifically the minimum distance between two strings needed to make them equal). This is also very useful for determining how similar (or dissimilar) two strings are.

(more…)

Data types in Java and C++ (amongst other languages) are limited to a specified range. Even in most basic calculators, performing an operation with 9 or more digits will result in an error. Sometimes, though, you have to perform very large calculations. Wouldn’t it be nice if there were an ADT that can perform arbitrary calculations, and “grow” depending on the size of the number? Of course, Java has a class library that will do this for you (BigInt), and there is almost certainly one available in C++, as well. But what if you had to develop your own? Of course, this would mean you’d have to re-implement basic mathematical operations — which may turn out to be not so “basic” at all. In this project, I’ve developed a “Long Integer ADT” in C++. Because the code for this project is somewhat extensive, I will only post the header files and smaller source files. The full source code can be downloaded here.

(more…)

The middle of a list is one record with equal number of records to the left and right (assuming the list has odd number of elements). If this number is even, the middle consists of two records. Write a pseudo-code procedure to delete the middle (one or two) record(s) of a doubly linked list without counting first or knowing the total number of elements in the list.

(more…)

This question comes up often in undergraduate CS classes, specifically Data Structures and Algorithms: How do you reverse a doubly linked list? Let’s find out!

(more…)

A while back I had to write a program that would compare different sorting algorithms in Java. The algorithms were Heap Sort, Merge Sort, and Quick Sort. I will leave the analysis up to you, but I will share the algorithms below.

(more…)

In the field of computer science, data compression is an extremely important tool used in many different types of applications. One way to compress data is to convert the data to binary code, using a shorter code for more frequently used values and a longer code for less frequently used values. Doing so allows you to save larger values in a much smaller space, thus saving you space overall. This is essentially how Huffman Coding works, and how I have implemented data compression in this application. To download the complete source to this project in C++, click here.

(more…)

I was recently given the task to implement an LSD Radix Sort algorithm to sort a set of strings (a list of names, specifically). Being that there aren’t many examples of this online, I’ve decided to share this. Admittedly, this took me some time to figure out, but looking back, it’s really not too difficult. You may download the complete source to run yourself by clicking here.

(more…)

If you’re a CS student, it’s only a matter of time before you have to write a program implementing a Binary Search Tree. Below, I will go through how I would do it, but what makes this version different from most other examples on the Internet is that this one loads a configuration file (list of commands) and gives a specific output according to the instructions for my class at the time. Because the code to this assignment is pretty lengthy, I’ve made the source code available for download (MyBinarySearchTree.zip).

(more…)