We used this textbook in my Computational Complexity course:
https://greenteapress.com/wp/think-complexity-2e/
Super interesting. Lots of projects you can do in it.
This is a super easy to read book about complexity:
https://www.amazon.com/Golden-Ticket-NP-Search-Impossible/dp/0691156492
This class was worthless when I took it in 2014, it is amazing they have not improved it. I raised hell all the way to the top of the OSU Engineering School, the best they did was add a bunch of extra credit to the final.
Remember one thing about this class, you are suppose to come away with the ability to design efficient algorithms and analyze their complexity. This class is suppose to give you all the tools and techniques to accomplish this, but it doesn't.
This is the most important class you will take in order to get a job at a top tech company. It was the entire reason I pursued a second degree. I learned a 10th of what I should have, I am still pissed.
Advice: learn all the material elsewhere. The lectures and book are worthless. Check out this post for a list of resources:
https://www.reddit.com/r/OSUOnlineCS/comments/agomik/cs_325_resources/
Go to Hacker Rank and leetcode to practice designing algorithms.
​
Learning Path:
​
A proof that P=NP would break the world, not literally but damn close (as an example all our encryption would be utterly useless - how long will it take for someone to screw with all the banks in the world? days? months? I will assume faster than anyone can find a new encryption theory that works in a P=NP world).
In general it would imply that it is just as easy to validate a solution to a problem as it is to solve the problem itself; quite counter intuitive! This is quite an over-simplification of what it would really would mean, but I'm certainly not the best one to explain the full effect of P=NP. Some other people have written books about this, you should go read them if you want to know more. I think this one is one of the newest. It non technical, but have received quite some good reviews.