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:

Comments

Post a Comment

Popular posts from this blog

Sprint 5 Retrospective (Capstone)

It is a shame that we are so close to the end of the semester. We were gaining so much momentum. It took us a while for us to get off the ground, but once we did, we never stopped gaining speed. I feel we will be able to keep this up through this last sprint. My hopes at the beginning of the semester for what we could accomplish were unrealistically high, but I am not disappointed with what we accomplished. We have not completed a full working component quite yet, but we are very close. I think our efforts are best spent finishing the one we are currently working on and doing it right. If we divided our efforts into starting something new, we run the risk of not fully completing anything. In the sage words of Ron Swanson, “Never half-ass two things. Whole-ass one thing.” If we are able to get the tabs working beautifully, I will be happy with our effort. I have felt that our group has done a phenomenal job this sprint and every sprint before with our communication. We have a few ...
Post a Comment
Read more

Mark Richards on the Evolution of Software Architecture

For this week’s blog on Software Architecture, I listened to Episode 3 of the “Software Architecture Radio” Podcast, which featured Mark Richards, an independent software architect. He has 32 years in the industry, with more than twenty years as a software architect.  They mostly talked about the evolution of software architecture. Although some of the things they talked about went a little over my head, I was able to pick up on the majority of what they were talking about.  He divided up the evolution of architecture into five stages. He talked about evolution happening in vertical and horizontal slices, that is within each layer and one layer affecting those above and around it. The layers were (1) hardware, (2) software, (3) human interaction, (4) social interaction, and (5) the environment, such as the internet of things. He said one thing in particular, need, drives change the fastest. As an aside, he also said that that’s the best way of teaching something i...
1 comment
Read more

Sprint 4 Retrospective (Capstone)

This sprint, in my mind, one of the most important things that I was able to figure out was getting connected to AMPATH team through the Zeplin app. It seems that someone, perhaps accidentally, disconnected me from the group. Once reconnected, I was able to connect the rest of my group. Although it hardly was a difficult task, it is hard to overstate how important it is to be on the same page as the team you are building the product for. It could have prevented a lot of wasted time on our end, and it makes it more likely that they get the end product they want. Probably the most important thing I did in terms of learning about the tools we will be using was creating a “spike.” It is a new term I’ve learned that I will add to my lexicon, meaning to build a prototype of a product, diving deep to learn as much as you can. I touched upon it in my last apprenticeship patterns blog post, on “breakable patterns.” I failed to make a successful working prototype that did everythin...
Post a Comment
Read more