Basic Algorithms and Data Structures
“After 221 all of you should use “divide-and-conquer” when handing out exams, its a lot more efficient!”
Text: Objects, Abstraction, Data Structures, and Design Using C++ by Koffman, Elliot B., and Wolfgang, Paul
Prof: Dr. Alan Hu
Dr. Alan Hu is great at making everyday metaphors (often involving Justin Bieber) out of abstract computer concepts. He is also very patient in class, answering questions in detail. His classes have a slightly “free-wheeling” style because of this, so the lack of structure could distract some. Dr. Hu is a super approachable guy, (except during exams!), and he seems genuinely passionate about teaching computer science.
Difficulty
The assignments and labs are all do-able, though the penalties for small compilation errors on assignments are harsh. The midterm was pretty long and it had a mistake on it and I (and many others) got wrecked. The final was significantly easier and the scaling was huge. There is a lot of material in the course though, and the questions on exams definitely require some thinking. However, if you are okay with mathematical proofs and work consistently you should be okay after scaling.
Key Concepts
Big-O, Theta, Omega (Time and Space Complexity)
Sorting Algorithms
Basic Data Structures
Iteration and Recursion
Basic Graph Theory
Parallelism
Hard Concepts
Proof of program correctness: Slightly different than mathematical proof, make sure to fully understand the conditions for a program to be correct. I only realized towards the end of the course, that this requires you to really read and understand the code fully.
Implementation in C++: Algorithms can look a lot less elegant in C++, so one needs to be familiar with common coding style in that language to interpret algorithms well.
Evaluating time complexity of given algorithm: Generally easy, but curve-balls can be thrown. Try breaking it down or stepping through the code.
Conclusion
Really important course for interviews, (along with 213). Felt like I improved a lot of reading code, and Dr. Hu was pretty entertaining.
Follow