ECE 2400: Introduction to C/C++ Programming

Completed during my fall semester, junior year.

Handwriting Recognition System

Task at hand:

For my handwriting recognition system, my partner and I were tasked with creating 5 search algorithms for the program to work, choosing the fastest while most accurate search function to be the main searching function. These 5 functions were: Linear Search, Binary Search, Tree Search, Table Search, and an Alternative Search. When discussing the Alternative Search, I will address how we created this searching function. Per the instructors request, I cannot and will not release my code.

Linear Search

For the Linear Search Function, the search algorithm simply performed a linear search of all images in over vector set of images. With this implementation, we experienced the highest accuracy as each image in the set was compared to each other, checking for the closest possible image. As a result of searching through every single image, which was 60,000 images in our case, this was the slowest search algorithm. With each comparision, there are a few calculations that needed to be addressed before moving onto the next image, with the most important calculation being the intensity of the image. This intensity told the the user and the program what the value of each pixel was, and when compared to another image using the find closest function we designed, it told us how similar each image was, while only returning the closest image in the set.

Binary Search

For the Binary Search Function, we needed to do one important step first: sort the vector of images. Using the merge sort function I created in an earlier assignment, we implemented the sort function to correctly sort the images in the vector set by comparing the intensities of each image. By doing so, we were able to sort the vector of images in an ascending order, with the images with the lowest intensity at the beginning and the images with the highest intensities at the end. With the vector now sorted, we recursively sorted through the vector, trying to find the closest image based. However, by doing this step alone, the function has a very low accuracy as it cannot distinguish between small changes in intensities. To fix this issue, we incorporated a linear search function that would check the immediate 500 images greater than and 500 values less than the image found with the recursive search. This greatly increased our accruacy. As a result, our functions search time dramatically improved over the linear search, as instead of searching through 10,000 images for each search, we could now search over only one thousand images.

Tree Search

For the Tree Search Function,

Table Search

For my handwriting recognition system, my partner and I were tasked with creating 5 search algorithms for the program to work, choosing the fastest while most accurate search function to be the main searching function. These 5 functions were: Linear Search, Binary Search, Tree Search, Table Search, and an Alternative Search. When discussing the Alternative Search, I will address how we created this searching function.

Alternative Search

For the Alternative Search Function, we used concurrent programming in order to speed up the search process. For our implementation, we used our linear search function. To effectively speed up the search function, we used 4 threads in total: the main thread as well as 3 additional threads made during compilation. Each thread was tasked with performing one fourth of the searching function: thread 1 searched 2,500 images, thread 2 searched another 2,500 images, and so on. Once each thread returned and joined with the main stack, the 4 closest values compiled during the respective threads were then analyzed to find which of the 4 values was closest to the inputed value. As expected, our Alternative Search Function was almost four times as fast as our Linear Search. While expected, our Alternative Search had the exact same accuracy as our single thread Linear Search function. When calculating the time difference between the two functions, our Alternative Search was 3.5-3.7 times faster, which logically works out as there are more steps involved in the Alternative Search when it comes to finding the closest value, which directly impacts performance. Even with these small performance hits, since we are doing multiple computations at once with each thread, we still see a dramatic improvement in performance.