Skip to main content

Data Structures Primer

I've been a tutor for this past semester to students taking Introduction to Programming. Many who have come to my session are moving on to Data Structures next semester. They asked if they could have a primer as to what to expect.

I have some resources that I have found helpful both while taking the course and tutoring it in the past. It will take me a little bit to compile a good list of those, but for now, here is a bare-bones list of topics of topics you might expect to see for a data structures course:

Part 1:
- Running time of code segments (Big-O Notation)
- Abstract Data Type (ADT)
- Interfaces (when to use "implements", cannot instantiate them, what inheritance is)
- Superclass, subclass, method overriding/overloading
- Abstract classes

Part 2:
- Binary Search Trees
- Stacks (and its four methods — push, pop, peek, empty)
- Linked list (single, double, circular)
- Prefix and postfix notation (compare to infix)

Part 3:
- Min/Max Heap
- Hash Tables - Open and closed hashing. How to insert into a hash table given a probe sequence.
- Binary Trees (AVL and Red/BLack)
- AVL Trees - how to construct one, worst case AVL-tree
- Red Black Trees
- B-Trees, especially deletion from one
- Know recursive code and how to trace it

Bear in mind, this is an incomplete list. The topics may be presented in different order as well. The "parts" are how I remember it and might not be accurate.

I'm not sure if I'll be able to compile a complete list of resources, but here is probably the best one for visualizing data structures: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Another one is CodingBat.com/java. This is especially helpful for learning recursive code. I don't know if any of the other sections would be helpful, but they might be.

Best of luck! It will be tough, but you got it! Even if you know one or two topics from each part, you will have a leg up on learning this material.

Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

Shailesh Rao on Quality Assurance

In this episode (number 219) of “Test Talks,” I was able to hear Shailesh Rao’s insight into having quality software. He compared it to a “paper-free office” or a “stress-free life,” both worthy goals, but are hard to achieve. They can be strived towards, but it is near impossible to get it 100%. He brought up the issues that bad software can pose to potentially millions of users. Bad software can open the doors to hackers, who might be able to take down websites like Twitter or Reddit. Also, it might stop airlines from being able to function — an annoyance to most, but Mr. Rao asked, “what if there was time-sensitive and lifesaving medicine onboard?” I found this podcast brought up some aspects that I had not thought of before when if comes to quality assurance. I suppose that I’ve thought about the various things he brought up, but as a consumer and never as a creator of the software. A very thought-provoking topic brought up was the fickleness of consumers. They don’t have the...
Post a Comment
Read more

Testing: Like Destroying Sandcastles

https://joecolantonio.com/testtalks/223-testing-dream-journaling-smashing-sand-castles-with-noemi-ferrera/ In this blog for software quality assurance and testing, I decided to return to the “Test Talks” podcast, presented by Joe Colantonio, for another episode (#223). In it, he sat down with Noemi Ferrera, a software tester for a Chinese mobile gaming company to get her take on the subject. Noemi gave a few interesting metaphors that I appreciated for how to look at testing. In one, she gave the example of going to a movie where you had already read the book. It was different than how you imagined it while reading it, and testing is a way of making the “movie version” fit the way you envisioned it playing out.  The other metaphor for testing that she gave was, if you were children at the beach, the developers would be the ones building the sandcastles, whereas the testers would be the ones destroying them. I don’t know if that would be the most accurate way of lookin...
Post a Comment
Read more

Decorator Design Pattern

For this week's blog on Software Design, I decided to watch a short tutorial on one of the design patterns I didn't pick for a previous assignment. I picked Proxy Design pattern to cover before, and now I'm going back to learn about Decorator Design Pattern. It is only a thirteen minute video, so I won't be going as deep as I would had I picked it for the assignment. I am also going to talk about my reflections on it rather than create a tutorial, so I am not going to reteach it to the person reading this blog post. The tutorial I chose was made by Derek Banas on YouTube. He used an example of a pizza parlor to illustrate the wrong way to code it by using inheritance. He shows the problem with this because you would have to create a very large number of subclasses for all your objects (in this case pizzas). Composition, on the other hand, is a dynamic way of modifying objects. Instead of creating as many subclasses, you add functionality at run time. It has th...
Post a Comment
Read more