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

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 in this fi
1 comment
Read more

OOP Basics

For this week’s blog on software design, I chose to watch a video presented by Dr. Steve Bagley on some fundamentals of object oriented programming (OOP). I’m embarrassed to say that although I am taking several upper-level computer science classes, I am unsure I would be able to give a good definition of what object oriented design was. To be fair though, it has been several years since I have taken CS 101, and it seemed like such a foreign concept at the time. I felt silly learning about something so elementary again, but it made a lot more sense when I’ve had as much exposure to OOP as I have now. For the video, he uses a game of “Pong” as an example of how OOP might use objects to represent the “ball” and “paddles.” From there, he talked some about inheritance and touched on a few more topics, albeit briefly. The main reason why I didn’t understand the benefit of this way of programming is that I didn’t know how else you would do it. I didn’t realize that without declari
Post a Comment
Read more

Apprenticeship Pattern "Nurture Your Passion"

In this week’s post, I will be discussing the apprenticeship pattern “Nurture Your Passion,” as presented by Adewale Oshineye and Dave Hoover. I chose this chapter because I think I have felt like I’ve been just getting by for a while now. The  problem it identifies as, “You work in an environment that stifles your passion for the craft.” I don’t think that’s quite fair to my school or professors. I think that in any discipline, if someone is only studying for the tests or working on the assigned projects and calling it a day when they have passed them in, they are not truly adopting the apprenticeship mindset. Without a constant push forward, I will stagnate. I may get an “A” on the exam or project, but if I forget the material the next day, there is no point. The pattern suggests finding something that sparks interest and pouring myself into it. I have been wanting to do this for a while, but I have made excuse after excuse of not having enough time. The next sentence in th
Post a Comment
Read more