Search This Blog

Sunday, June 19, 2022

Data and Programming Structures - Guide for studying and free resources

While studying Data Structures and Algorithms 1, I came upon many resources which helped me! Here are some of the ones I reference quite frequently. For asymptotic analysis, Calculus comes in handy with Limits and L'Hôpital's rule (using derivatives). In addition, the lecturer's often referred to the CLRS Algorithms Book, the acronym is each of the author's first letter of their last names... Overall the book is quite helpful, it is lacking details for the popular AVL Tree (self balancing binary search tree), but besides that it is great. 

I have added plenty of resources below, intentionally there is a mix of academic links in addition to general ones. Computer Science and Data Structures as a field tend to work on the more theoretical level, but I see value in the practical side of Data Structures and Algorithms as well which justifies my choice!

An example of this is using pseudo-code, it is general practice to use it in college and universities rather than a specific programming language. This is because it allows an idea to be conveyed without dealing with quirks of certain languages. A side effect of this is that the code cannot be compiled nor run, this can be good as if you made a mistake it is harder to dock you points. But at the same time, if you made a mistake it is harder to test and find it. 

DALLE Generated image of a BST
DALLE Generated image of a BST


I put a graph together on desmos which you can play with and see for yourself how a large enough N (or x in this case) can impact performance of algorithms. We can assume that X will never be <= 0, as it wouldn't be realistic or even practical to have a data structure with no elements. 

Academically we have 5 different symbols for asymptotic notation:
        o  O  Θ   Ω   ω
F(n) < <=   =   >=  >  G(n)

(in order of appearance) Often called: little O, big O, theta, Big omega, little omega

This strictly means, if F(n) is o(g(n)), then F(n) is certainly better than G(n). You can extend this to the rest of the symbols logically via the comparison symbols I placed. 

Heads up! In the workforce and hi-tech, they most often use Capital Omicron, or Big-oh (and occasionally theta and Capital Omega). 

These are essentially considered bounds of a function. We then can use this notation to compare two functions or an algorithm to some bound. Such as 3n+1 = O(N2), which directly translates to 3n+1 <= N2  which is in fact true. The general extension of asymptotic notation is to use it to determine the time and space complexity of an algorithm. As an example, Quick Sort takes the time complexity of Θ(n log n) for both the best and average case. But in the worst case, it takes Θ(N2). As a side note the worst case can be essentially avoided if the pivot element is decided randomly or logically based on the size of the array and positions of elements.

Courses: (Course for auditing) (some content is related to DS) (Rob Edwards YouTube Playlist - San Diego State University) - Amazing videos! 

Additional resources/Guides: (very conclusive and helpful) (basic overview) (Limited amount of content)


Algorithms by Jeff Erickson (Freely distributed by the author)

CLRS Solutions (3rd party solutions to the practice questions in the book):

Code implementations: (in C)

Algorithms visualized:

Amazing ones: (their BST implementation doesn't handle duplicates)  (Many different options and animations)  (This one is OK)

Thank you for reading, please share the article and follow me on twitter for more resources and guides!

No comments:

Post a Comment