What should I be most familiar w/for C++ Data Structs & Algorithms

[in the rye]

Hey all,

This coming Spring semester (starts in 6 weeks), I will be taking C++ Data Structures and Algorithms at my University. I started programming at University, so my experience is very limited (I've taken 3 programming courses, 1 in Python, 2 in C++).

Topics we've covered in C++ were procedural programming, some OOP, pointers, inheritance, polymorphism, a small portion of the STL, exceptions, single non-circular linked lists, dynamic stacks, and queues.

The book we will be using Data Structures and Other Objects using C++ by Michael Main. I'm a little nervous because I registered for the most difficult Data Structures professor our University has because I want to be sure I learn the material well. However, this semester I didn't have a great C++ professor so I'm not sure how prepared I am, and I want to be sure I make up any inadequacies before next semester.

The course covers lists, stacks, queues, trees (binary, tree traversals, height balanced trees), graphs, hash tables, sorting, searching, hashing, recursion, dynamic versus array implementations, modular programming using data structures, data structure implementation using header files and implementation files.

I feel fairly confident with my discrete math abilities, its more-or-less deficiencies in C++, so I want to know what I should practice over Winter break.

Thanks.

 

[QuantumQuest]

Before any recommendation keep in mind that C++ is generally a hard beast to tame. This is not a discouraging comment, just keep it in mind and be patient as you learn this programming language and it will finally pay back.

I would recommend checking what you've learned so far regarding the language itself, giving priority to OOP features and pointers as well as STL library - I'm assuming that you already have a good grasp of procedural programming beyond the beginner level so far. If this is not the case then you have to start your check from scratch.

You can use various sources: a good textbook - your textbook from previous semester(s) or if you don't find it very clear or helpful, I'd recommend to take a look at Deitel's textbook as it is very detailed and has a lot of good tips, exercises and problems besides teaching the language itself. There are many other great textbooks as well.

There are also many good online tutorial sites like cplusplus that you can search for specific things. Of utmost importance in my opinion is to be able to solve advanced problems utilizing the various features of the language.

The other part of your preparation is algorithms and data structures. You have to be confident enough about having a good grasp of the theoretical part of algorithms (e.g. searching, sorting) and data structures (e.g. lists, stacks, queues, trees etc.), in order to be ready to start utilizing all this through C++. My recommendation on this is - after doing some recap, start studying on your own some implementations of basic data structures and algorithms in C++.

You can find plenty of code online and also you can take a look at the textbook that you'll have in the next semester and get some rough idea how things work. A good book I'd like to recommend is Algorithms in C++ by Robert Sedgewick. I think that if you get prepared enough on all these you'll have no problem at all.

 

[StoneTemplePython]

My own view is that I really like Tim Roughgarden's free course on algorithms.

Parts 1 and 2 are available here:
https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms1+SelfPaced/about
https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms2+SelfPaced/about

This course is language agnostic. If you are extremely concerned about implementing these algorithms in C++, why not start over winter break by tackling part 1 of this course, and doing the assignments in C++?

 

[in the rye]

I would recommend checking what you've learned so far regarding the language itself, giving priority to OOP features and pointers as well as STL library - I'm assuming that you already have a good grasp of procedural programming

I feel fairly competent with procedural programming. I was actually looking at getting that Data Structures book, but also considering the CLRS Intro. Algo. Book.

Are there any specific topics within OOP that I should focus on? Likewise with pointers and STL?

 

[QuantumQuest]

My own view is that I really like Tim Roughgarden's free course on algorithms.

Parts 1 and 2 are available here:
https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms1+SelfPaced/about
https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms2+SelfPaced/about

This course is language agnostic. If you are extremely concerned about implementing these algorithms in C++, why not start over winter break by tackling part 1 of this course, and doing the assignments in C++?

This is an excellent recommendation in my opinion as well. I took both parts of the course some years ago as a refresher, as for a while I was not particularly dealing with algorithms and I really enjoyed it. Tim Roughgarden is great and I personally tried the problems in various programming languages. He also gives a very good view of many theoretical aspects.

 

[QuantumQuest]

...but also considering the CLRS Intro. Algo. Book.

This is an excellent idea. This a very valuable resource and I recommend digging in it as deep as you can.

Are there any specific topics within OOP that I should focus on? Likewise with pointers and STL?

You need a good grasp of the basic concepts of OOP in general and to work with objects and classes in real code, in order to apply the basic features i.e. encapsulation, inheritance and polymorphism in the context of C++. This becomes hard enough as you proceed to more advanced problems.

For pointers my recommendation is to get a good grasp of the concept of a pointer, as it is applied in a procedural way - in other words, in the same way as we work with pointers in C first, beyond basics. It is a hard concept to grasp in depth and see where and how you can apply it, although - quoting from Nick Parlante's "Pointers and Memory" (Stanford)

There's a lot of nice, tidy code you can write without knowing about pointers. But once you learn to use the power of pointers, you can never go back

I also recommend to read through this resource - if you haven't already done so and work with pointers on your own in real code by solving sufficiently hard problems.

For STL my recommendation is to just try getting used to it in a suitable pace i.e. don't hasten in any way. You must find the way of applying the templates in each and every occasion you have in the context of a problem and see the advantages of doing this. It will take time and efforts but the payback will be big with the most important thing being writing professional code.