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.
During this last sprint I spent my time working on two things, that of continuing to try to get the styles to work for the buttons on our program and our teams final presentation. In continuing with the styles of the buttons from the bottom navigation bar, I finally tried to create and apply a palette. Ignite UI uses a thing called palettes which is a built in feature that takes two colors as primary and secondary, as well as a few other built in color groups, to create a large “palette” of colors that you can reference. To do this you create an SCSS file, short for Sassy CSS, which is a super set of CSS allowing the programmer to create variables, nested rules, functions, etc.. When you create this SCSS file, you have to import the Ignite UI style index, as well as provide the primary and secondary colors. From here you can define a custom gray scale palette, or take the one automatically created which has a default color of black. Finally once the palettes have been set, this is where the SCSS comes in, by allowing you to create color variables which can be used over and over. To create these variables Ignite UI provides a function for creating these colors, with 3 inputs; palette, color, and variant. The palette is one that you have created, the color is one of the 8 available through Ignite UI, and then finally a number for the variant with the default being 500, lighter shades being 50-400, and darker shades from 600-900. An example of one of these color variables would be “$my-primary-600: igx-color($my-palette, ‘primary’, 600);” I did all of this trying to hopefully change the styles of the individual button elements of the bottom navigation bar, but instead it would apply to most or all of the document. Although I did not get what I had wanted working, I feel that I did learn a lot of the way that this Ignite UI worked during this sprint, having spent many hours trying several different possible solutions. I feel with more time I would have been able to figure out this problem but my team also had to start planning and creating our final presentation for the class. For this my portion of the presentation was to be on the Ignite UI as well as some of the style stuff involving SCSS. To help me with this I spent a long time reviewing the Ignite UI website which was very expansive and almost like a Wiki. On thing that was very helpful with there website was the inclusion of examples using Stack Blitz, which gave examples of how the code would be run, and which could also be changed. This sort of program example helped a lot in trying to understand how a certain element they have in the Ignite UI worked when compiled into code, and I would highly recommend a version of it being used in future classes.
An algorithm is a set of rules to be followed in order to solve mathematical problems in numerous steps that usually involve repetition of an operation. Sometimes algorithm problems do not show up at the beginning of a project. As Steven S. Skiena states, different programmers find them out as subproblems, which appear to be … Continue reading Read Constantly→
We live in a world where different complex software projects have different deadlines and they use a variety of tools to finish the projects. Most of the time employers cannot afford to hire too many specialists to fill every role. You learn only enough about any tool to get today’s job done. You select some … Continue reading Dig Deeper→
The pattern “Craft over Art” is the idea of choosing the craft of programming and making thing functional. Rather than choosing art of programming and making the program look beautiful but not so functional for the customer. Even though you may find an opportunity taking your customer problem and making something nice that will impress your coworkers, it is best that you put the customer needs before your own selfish wants or needs. When it comes to dealing with customer your goal should always be choosing creating a functional valuable product, rather than something else that only advance your own self interest. When dealing with customers it is more important to choose the craft of software development rather than feeding that desire to creating something beautiful, yet not truly functional or deliverable in the real world. This pattern is not telling you that things can’t be beautiful it more saying that whatever you build for your customer must be functional and useful, therefore you must be willing to sacrifice beauty over utility. “The more useful a piece of software, the more important it is that the software be high quality. But quality takes time. You will have to work toward a suitable level of quality by repeatedly making trade-offs between beauty and utility.”
My Reaction
This pattern helps you understand the impotence of building “Craft over Art” because it reminds you that creating something useless yet beautiful is not craftsmanship. I agree with this idea because crating a useful software program far more important than a beautiful non-functional one. I found this pattern to be interesting but also useful and thought-provoking. This pattern has definitely changed the way I think about my profession and the way I think, the reason being is that I should always be willing to sacrifice beauty before sacrificing usefulness.
Thank you for your time. This has been YessyMer in the World Of Computer Science, until next time.
According to my next Apprenticeship Pattern blog I chose “Draw Your Own Map,” as one of the most interesting patterns and which fits perfectly in my logic. When you decide to enter the Software Development world, you may think that it’s a hard and tough game, or sometimes you believe that your career will always … Continue reading Draw Your Own Map→
I haven’t written a blog post for MINIX3 in some time (sorry Professor), and I figured that it would probably be wise to wrap up what I managed to complete this semester after I managed to get past all the stress I was feeling.
About halfway through the semester I started meeting weekly with my professor in order to discuss ways to approach my project. He knew I was pretty darn stressed about it, but was also pleased with how much I had learned about MINIX3 and Operating Systems in general. When we started meeting, I hadn’t done any actual programming in the scheduler, and I was still fuzzy on how the whole scheduler worked as one unit. I had also not realized this at the time, but the scheduling algorithm in the official MINIX3 Book was an older version. It doesn’t reflect the design found in this report, which describes the current scheduling algorithm (found in versions 3.3.0 and newer, I believe). This was adding to the confusion in how to approach the system, because I was getting my information on the implementation of the scheduler from both sources.
I’ve talked about this a bit in my previous blogs, but I figured I’d recap in this one now that I have a better understanding of the system. In the official MINIX3 book, the scheduler is still built into the Kernel. This meant that any scheduling changes that were to be implemented involved editing kernel code, which could end up being pretty complex in the event of errors, etc. What the scheduling report outlines is the move of the scheduler into the user mode level of MINIX’s layered design system. There still is a small default scheduler that had to be implemented, but the main scheduling policy is implemented within the user mode scheduler.
Let’s talk scheduling policies. Both the kernel-level and the user-level schedulers implement a Round Robin scheduling algorithm by default. As outlined in the report, the easiest policies to implement with the user mode scheduler are round robin, priority, staircase, and some other queue-based policies. Whilst I was googling information about implementing priority-based algorithms, I found this wonderful project done by a GitHub user named Akshita Mittel. It includes a few test files and the changes necessary to make to some of MINIX3’s files in order to implement different algorithms. It is very similar to the project I had intended on doing, so whilst I did not copy it directly (licensing and copyright issues and whatnot), I did use it as a resource for implementing my own project.
Since I wanted to deviate my project slightly from the resources I found online, instead of just implementing more than one scheduling policy, I elected to compare the default scheduling policy with a priority scheduling algorithm, and vary the number of queues by +- 25%. This left me with 3 variations of the default Round Robin policy — one with 12 queues, one with the standard 16 queues, and one with 20 queues. It also left me with 3 variants of a scheduler using a priority algorithm, again with 12, 16, and 20 queues. My goal was to run the same test across each of these 6 variations and see if there was some notable runtime difference.
Before I go into the test, I figured I’d explain the difference between Round Robin and Priority style scheduling. Round Robin policies assign each process within the priority queues a time slice, called quantum. As processes run out of quantum, they’re moved to a higher (the higher the number, the lower the priority) priority queue. In MINIX3, after a certain number of ticks, the queues are rebalanced. This means that all processes who have had their priority changed get that priority reset. The difference between round robin and priority scheduling algorithms is fairly simple — round robin policies aim to be fair, which is why they implement queue feedback. Priority policies are designed without fairness in mind. You might want some processes to always have the highest priority. Therefore, it simply disables process feedback from happening. Processes don’t move around between queues. A diagram of the structure of the priority queues are shown below.
Based on an image from Operating Systems: Design and Implementation by Andrew S. Tanenbaum
The test I used was based on Akshita’s that I found on GitHub. The test program would log system time, do some work with a process, then log the system time again, and find the difference between the start and end times. I found the average running time for 100 tests for each of the variations. The results are displayed below.
As you can see, there wasn’t much consistency across the tests. I’m sure that, before I even ran the tests, I could have reasonably come to the conclusion that there wouldn’t have been much of a difference in run times given my particular approach. The test I ran was mostly CPU bound as opposed to I/O bound, which very well could have made a difference. I think CPU bound tests could have made a bigger impact if I had implemented a different policy than priority. On top of designing a better test for what I was doing in particular, I think that theoretically the number of queues within a round robin scheduler wouldn’t make much of a difference unless the processes existed within them for a very long period of time. Also, I think that the number of queues within a priority scheduler wouldn’t make a significant difference either, since processes tend to live where are they spawned. Aside from the crowding of the queues, I don’t see it having a large impact on the overall runtime. Therefore, I think that the results I got make sense.
I’m not upset that my small “research project” didn’t yield great results. The point of this independent study was for me to better understand operating systems, as I felt as though I was seriously lacking in that area. While I know there’s still a tremendous amount of knowledge to be gained in OS’s, I’m happy with the work I did this semester and feel far more confident when discussing OS concepts in general. It was a very stressful project at first, but now that I’ve wrapped it up, I think it was absolutely worth it. Hands-on operating system practice is a great way to go about learning the subject. In fact, this independent study has sparked quite a bit of interest in systems programming for me, and I’m looking forward to continue learning about it in the future!
(Side-note, this is my last school-related blogpost. At first, I felt extremely uncomfortable writing these things. Now, I think it’s something I’d like to do once a week, or at least regularly. I appreciate my professor requiring us to start these blogs — writing is something I never really saw myself doing enjoying, and after doing it for a couple of semesters now, I get it. Who would’ve guessed that recording what you learn is both both enjoyable and rewarding. Thanks, Professor Wurst!)
Today we will once again be continuing our journey into software apprenticeship patterns. From last week, we will continue on to the next pattern, Expose Your Ignorance.
This pattern is all about once you have gotten yourself onto a team where you can learn more from your fellow teammates, presumably in a job. The problem is that well… you are ignorant. You need to deliver and you have a lack of knowledge in whatever language or technology you need to be able to deliver.
The offered solution is fairly simple, ask questions and don’t be afraid to show that you are ignorant in a particular subject. You should recognize that it is human to want to appear competent and not appearing competent is not a bad thing. It is all part of the learning process. As a software craftsman, you need to know many different subjects and technologies. The pattern suggests that people who are uncomfortable with the learning process of appearing ignorant become experts instead. They seek out expertise in one particular field and never venture too far from it. Experts are important but the journey of a software craftsman is much longer and requires a broader scope of knowledge. You become an expert in one or several subjects along the way but that is not the ultimate goal. For a software craftsman, one of the most important skills is the ability to learn. To solve this problem the pattern suggests writing down a small list of thing you don’t really understand about your work and posting it in public view.
This pattern I find interesting. What I found most interesting was the distinction made between the software craftsman and the expert. The pattern admits that a software craftsman will likely become an expert in a few subjects but that is not the ultimate goal. The goal is not explained in the pattern (I’m sure it is explained at the beginning but I have forgotten it at time of writing) but the difference between the expert and the craftsman is that the expertise is not the goal. A craftsman goes further than becoming an expert and goes on to craft with the expertise of many under his belt where the expert gains expertise and then rests on his laurels. I do also appreciate the part where it states that by admitting ignorance it will increase your reputation greater than “fake it until you make it” will.
That’s it, for now, my fellow readers. Until next time!
This week we shall continue looking at Apprenticeship Patterns. I decided to skip over the Unleash Your Enthusiasm pattern and instead decided to talk about the Concrete Skills pattern this week instead.
The Concrete Skills pattern seeks to solve the problem of joining a team of craftsmen to further your learning opportunities. This could also be the all-important problem of getting a job. The problem keeps on going as you are too much of a risk as you may not be able to directly contribute anything to the team. You may not be able to even indirectly contribute.
The solution proposed is fairly self-explanatory. It’s right in the name of the pattern! Acquire concrete skills that allow you to demonstrate ability with relevant tools and technology. The pattern does suggest acquiring some skills that are geared more towards getting past HR and managers. I do like the proposed idea of “buzzword bingo” that the pattern mentions briefly. The rest of the concrete skills that you learn should be directed at showing your team that you are actually useful and that someone doesn’t need to look over your shoulder constantly to ensure you don’t mess up or break something. It goes on to make a good point. When faced with a hiring manager, they will ultimately be looking for someone who can actually contribute in some way on the first day. Having concrete skills is, as the pattern puts it, a way to meet them halfway. Then as you progress, you will have to rely on these concrete skills less and less. To learn what concrete skills to build, the pattern suggests looking at resumes of people whose skill you respect in the business. Identify some skills from the resume and work on them and of course, keep reviewing your own resume.
This is what drew me to talk about this pattern. It is directly relatable to me as I am in the job hunt as I am graduating soon. I found this entire pattern to be generally good advice for anyone in the software development field seeking a job. It also corroborates what a lot of people have given me advice for job hunting.
That’s all for this week. I wonder what pattern I will get to read about next?
For my last apprenticeship pattern blog post, I felt that the pattern Sweep the Floor was appropriate given where I currently am at in my career, given that I hope to be starting in the very near future. This pattern refers to the scenario in which you’re a new apprentice on a project or a new member of a team and you’re not sure what your place is in the team, so you want to contribute and earn the team’s trust. The solution to this is to volunteer for simple, necessary tasks that no one else wants to do and to make sure to do a great job with them. Of course, you want to make sure that you don’t end up only doing menial tasks that no one else wants to do and that you’re given more challenging assignments after proving yourself “worthy”.
As I said earlier, this pattern is probably one of the most applicable to me at the moment, because once I start I can see myself in almost the exact same scenario as described in the pattern. I always figured that most junior level roles start with you being assigned simple tasks like one-liner bug fixes to help you get acquainted with the code base, but I hadn’t considered that it would be a good idea to take on tasks like literally sweeping the floor in order to build confidence as a member of the team. Of course, I don’t entirely agree with consistently taking on tasks that aren’t relevant to what you want to work towards, but there’s merit in doing menial labor when you happen upon it. As long as you make sure to let it be known that you want to be challenged and not just be comfortable standing still working as the team’s gopher.
Overall, I would say that it’s very likely that I’ll end up using this pattern in the very near future, so hopefully I remember to avoid the negative consequences of applying it. In fact, I wouldn’t be surprised if this pattern would be useful for me anytime I happen to enter a new team, not just my first one.
