Course Introduction

Resources

• Slides
• Previous Versions

Video Script

Hello and welcome to the Computational Core program!

My name is Russ Feldhausen, and I’ll be one of the instructors for this program. My contact information is shown here, and is also listed on the syllabus

[Slide 2]

There are many other instructors and TAs for this program that you may interact with or see in the tutorial videos. They all have been instrumental in the development of this program. Specifically, I’d like to recognize the work of Nathan Bean, the developer of the CIS 400 course on which this course is based.

[Slide 3]

In this course we will primarily use a KSU email group (cc410-help or cc410-help@ksuemailprod.onmicrosoft.com) to communicate. Email sent to this address is forwarded to all instructors and TAs. Our replies to you will also be shared amongst the instructors and TAs so we all have access to the assistance you have already received. We will respond to you within a business day, so be aware that a question emailed Friday night may not receive an answer before Monday. Please read and adhere to the guidance on Netiquette in the syllabus for all electronic communications.

[Slide 3]

In addition to email and Canvas, we’ll be using the online learning platform Codio for most of the programming tutorials and projects in this program. We’ll also discuss how to use Codio later in this module.

[Slide 5]

The Computational Core program consists of several courses, and each course contains a number of learning modules. In general, there are about 12-15 modules per course. Each module will usually consist of an interactive tutorial using Codio, followed by a quiz through Canvas, and lastly a programming project in Codio. In CC 410, there will also be several guided examples for you to follow and submit. The modules themselves are gated, which means that you much complete each item in the module before continuing. In addition, the modules enforce prerequisite requirements from other modules. For CC 410 you must complete them in order starting with module 0.

You are welcome to work on this course at any time during the week as your schedule allows, provided that you complete each module before the listed due date. There will be roughly one module due each week. Unlike other Computational Core courses, CC 410 does not include many auto-graded assignments. This is primarily due to the open-ended nature of the course. Instead, your code will be reviewed by an instructor or TA and you’ll receive feedback through Canvas and Codio. In some instances, you may be encouraged to redo parts of an assignment for additional credit. We will strive to provide feedback on an assignment within one week of it being submitted.

[Slide 6]

Looking ahead to the rest of this introductory module, you’ll see that there are a few more items to be completed before you can move on. In the next video, I’ll discuss a bit more information about navigating through this course on Canvas and using the Codio learning environment.

[Slide 7]

One thing I highly encourage each of you to do is read the syllabus for this course in its entirety, and let us know if you have any questions. My view is that the syllabus is a contract between me as your teacher and you as a student, defining how each of us should treat each other and what we should expect from each other. We have made a few changes to the standard syllabus template for this program, and those changes are clearly highlighted. Finally, the syllabus itself is subject to change as needed as we adapt this program to meet the needs of its students, and all changes will be clearly communicated to everyone before they take effect.

[Slide 8]

One very important part of the syllabus that every student should read is the late work policy. First off, each module has a due date, and you may work on that module at any time before it is due, provided you have met the prerequisites. As discussed before, you must do all the readings and assignments in a module, preferably in listed order, before moving on, so you cannot jump ahead. A module is considered completed when all items have been completed.

[Slide 9]

For the purposes of grading, we will use the date and time that the confirmation quiz was submitted at the end of each module to determine when the module was completed. This is due to the way that Codio handles grading, as it may resubmit previously graded assignments if an error in the module is corrected, making a previously completed assignment appear to be submitted late.

If a module is completed after the due date, a penalty of 10% of the total points of each assignment will be deducted for each day the assignment is late. Therefore, if an assignment is submitted 3 days late, it will be subject to a 30% penalty of the total number of points possible on that assignment. After 10 days, no points will be awarded for a late submission.

However, even if a module is late, it still must be completed before you can move on to a later module. So, it is very important to avoid getting behind in this course, as it can be very difficult to get back on track. If you ever find that you are struggling to keep up, please don’t be afraid to contact either the instructors or GTAs for assistance. We’d be happy to help you get caught back up quickly.

The grading in this course is very simple. First, 10% of your final grade will depend on the grades you receive from each of the tutorials and quizzes throughout the course. Next, 10% of your grade will come from the interactive examples that precede several projects. The next 40% of your grade will come from the numerous project milestones throughout the course, of which there will be approximately 10. There will also be a couple of “concept quizzes” throughout the semester, which are a bit longer than a normal quiz and will ask you to apply what you’ve learned to a novel situation. Those are worth 15% of your grade. Finally, the last 25% of your grade will come from the final project in the course, which will be discussed in a later video. In this program, the standard “90-80-70-60” grading scale will apply, though I reserve the right to curve grades up to a higher grade level at my discretion. Therefore, you will never be required to get higher than 90% for an A, but you may get an A if you score slightly below 90% if I choose to curve the grades.

[Slide 10]

This is intended to be a completely online, self-paced course. There are no mandatory scheduled course times. All of the content is available online, so you can work whenever and wherever you want. It could be a 3-hour block once a week, or a few minutes here and there between classes. It’s really up to you and your schedule. However, remember that each module may require 12 to 16 or more hours of work to complete, so make sure you have plenty of time available to devote to this course.

In addition, due to the flexible online format of this class, there won’t be any long lecture videos to watch. Instead, each module will consist of a guided tutorial and several short videos, each focused on a particular topic or task. Likewise, there won’t be any textbooks required, since all of the information will be presented in the interactive tutorials through Codio. Finally, since we are using Codio as our learning platform, you won’t have to deal with installing and using a clunky integrated development environment, or IDE, just to learn how to program. Codio helps make learning to program quick and painless by moving everything to the web.

[Slide 11]

What hasn’t changed, though, is the basic concept of a college course. You’ll still be expected to watch or read about 6-9 hours of content to complete each module. In addition to that, each project assignment may require another 6-9 hours of work to complete. If you plan on doing a module each week, that roughly equates to 6 hours of content and 6 hours of homework each week, which is the expected workload from a 3-4 credit hour college course.

From my experience, I can definitely share that the number one reason students struggle in this class is due to poor time management, not the complexity of the material. So, make sure you are planning to dedicate enough time to this course, and strive to start assignments as soon as you receive them so you have lots of time to get help if you get stuck.

[Slide 12]

For this course, the only supplies you’ll need as a student are access to a modern web browser and a broadband internet connection. No other special hardware or software is necessary! However, in this course you will also be able to do some development on your own computer using Visual Studio Code and Ubuntu. We’ll provide some short videos to help you get started if you choose to go that route, but it is not required. Due to the complex nature of this course, we do not recommend using phones, tablets, or Chromebooks if you choose to do development on your own systems.

[Slide 13]

Finally, as you are aware, this course is always subject to change. This is a relatively new program here at K-State, and we’re always working on new and interesting ideas to integrate into the courses. The best advice I have is to look upon this graphic with the words “Don’t Panic” written in large, friendly letters. If you find yourself falling behind, or not understanding seek our help via cc410-help.

[Slide 14]

So, to complete this module, there are a few other things that you’ll need to do. The next step is to watch the video on navigating Canvas and Codio, which will give you a good idea of how to most effectively work through the content in this course.

[Slide 15]

To get to that video, click the “Next” button at the bottom right of this page.

Navigating Canvas & Codio

Resources

• Codio Documentation

Video Script

This course makes extensive use of several features of Canvas which you may or may not have worked with before. To give you the best experience in this course, this video will briefly describe those features and the best way to access them.

When you first access the course on Canvas, you will be shown this homepage. It contains quick links to the course syllabus and Piazza discussion boards. This is handy if you just need to jump to a particular area.

Let’s walk through the options in the main menu to the left. The first section is Modules, which is where you’ll primarily interact with the course. You’ll notice that I’ve disabled several of the common menu items in this course, such as Files and Assignments. This is to simplify things for you as students, so you remember that all the course content is available in one place.

When you first arrive at the Modules section, you’ll see all of the content in the course laid out in order. If you like, you can minimize the modules you aren’t working on by clicking the arrow to the left of the module name. I’ll do so, leaving the introductory module open.

As you look at each module, you’ll see that it gives quite a bit of information about the course. At the top of each module is an item telling you what parts of the module you must complete to continue. In this case, it says “Complete All Items.” Likewise, the following modules may list a number of prerequisite modules, which you must complete before you can access it.

Within each module is a set of items, which must be completed in listed order. Under each item you’ll see information about what you must do in order to complete that item. For many of them, it will simply say view, which means you must view the item at least once to continue. Others may say contribute, submit, or give a minimum score required to continue. For assignments, it also helpfully gives the number of points available, and the due date.

Let’s click on the first item, Course Introduction, to get started. You’ve already been to this page by this point. Many course pages will consist of an embedded video, followed by links to any resources used or referenced in the video, including the slides and a downloadable version of the video. Finally, a rough video script will be posted on the page for your quick reference.

While I cannot force you to watch each video in its entirety, I highly recommend doing so. The script on the page may not accurately reflect all of the content in the video, nor can it show how to perform some tasks which are purely visual.

When you are ready to move to the next step in a module, click the Next button at the bottom of the page. Canvas will automatically add Next and Previous buttons to each piece of content which is accessed through the Modules section, which makes it very easy to work through the course content. I’ll click through a couple of items here.

At any point, you may click on the Modules link in the menu to the left to return to the Modules section of the site. You’ll notice that I’ve viewed the first few items in the first module, so I can access more items here. This is handy if you want to go back and review the content you’ve already seen, or if you leave and want to resume where you left off. Canvas will put green checkmarks to the right of items you’ve completed.

Continuing down the menu to the left, you’ll find the usual Canvas links to view your grades in the course, as well as a list of fellow students taking the course.

===

Now, let’s go back to Canvas and load up one of the Codio projects. To load the first Codio projects, click the Next button at the bottom of this page to go to the next part of this module, which is the Codio Introduction tutorial. On that page, there will be a button to click, which opens Codio in a new browser window or tab.

Once Codio loads, it should give you the option to start the Guide for that module. You’ll definitely want to select that option whenever you load a Codio project for the first time.

From there, you can follow the steps in that guide to learn more about the Codio interface. The first page of the guide continues this video. I’ll see you there!

Where to Find Help

Resources

• Slides
• K-State IT Help Desk - Email helpdesk@ksu.edu
• K-State Online Canvas Help
• Instructure Canvas Guides
• Codio Documentation
• Codio Support
• K-State Libraries
• K-State CS Support
• K-State CS Advising
• K-State Engineering Student Services
• K-State Office of Student Life
• K-State Report It

Video Script

As you work on the materials in this course, you may run into questions or problems and need assistance. This video reviews the various types of help available to you in this course.

First and foremost, anytime you have a questions or need assistance in the Computational Core program, please send an email to the appropriate help group for this course. In this case, it would be cc410-help, or cc410-help@ksuemailprod.onmicrosoft.com. That email goes to the instructors and GTAs, and is your best chance to get a quick response. We’ll respond to your email within one business day.

Beyond email, there are a few resources you should be aware of. First, if you have any issues working with K-State Canvas, K-State IT resources, or any other technology related to the delivery of the course, your first source of help is the K-State IT Helpdesk. They can easily be reached via email at helpdesk@ksu.edu. Beyond them, there are many online resources for using Canvas, all of which are linked in the resources section below the video. As a last resort, you may also want to email the help group, but in most cases we may simply redirect you to the K-State helpdesk for assistance.

Similarly, if you have any issues using the Codio platform, you are welcome to refer to their online documentation. Their support staff offers a quick and easy chat interface where you can ask questions and get feedback within a few minutes.

If you have issues with the technical content of the course, specifically related to completing the tutorials and projects, there are several resources available to you. First and foremost, make sure you consult the vast amount of material available in the course modules, including the links to resources. Usually, most answers you need can be found there.

If you are still stuck or unsure of where to go, the next best thing is to post your question as an email to the help group. As discussed earlier, the instructors and GTAs will do their best to help you as soon as they can.

Of course, as another step you can always exercise your information-gathering skills and use online search tools such as Google to answer your question. While you are not allowed to search online for direct solutions to assignments or projects, you are more than welcome to use Google to access programming resources such as StackOverflow, language documentation, and other tutorials. I can definitely assure you that programmers working in industry are often using Google and other online resources to solve problems, so there is no reason why you shouldn’t start building that skill now.

Next, we have grading and administrative issues. This could include problems or mistakes in the grade you received on a project, missing course resources, or any concerns you have regarding the course and the conduct of myself and your peers. Since this is an online course, you’ll be interacting with us on a variety of online platforms, and sometimes things happen that are inappropriate or offensive. There are lots of resources at K-State to help you with those situations. First and foremost, please email me directly as soon as possible and let me know about your concern, if it is appropriate for me to be involved. If not, or if you’d rather talk with someone other than me about your issue, I encourage you to contact either your academic advisor, the CS department staff, College of Engineering Student Services, or the K-State Office of Student Life. Finally, if you have any concerns that you feel should be reported to K-State, you can do so at https://www.k-state.edu/report/. That site also has links to a large number of resources at K-State that you can use when you need help.

Finally, if you find any errors or omissions in the course content, or have suggestions for additional resources to include in the course, email the help group. There are some extra credit points available for helping to improve the course, so be on the lookout for anything that you feel could be changed or improved.

So, in summary, reviewing the existing course content should always be your first stop when you have a question or run into a problem, since most issues can be solved there. If you are still stuck, email cc410-help to ask for assistance, and we’ll get back to you within a business day. For issues with Canvas or Codio, you are also welcome to refer directly to the resources for those platforms. For grading questions and errors in the course content or any other issues, please email cc410-help or the instructors directly for assistance.

Our goal in this program is to make sure that you have the resources available to you to be successful. Please don’t be afraid to take advantage of them and ask questions whenever you want.

How to Learn Programming

Resources

• Slides
• The Science of Learning Programming from Nathan Bean’s CIS 400 Textbook
• The Power of Believing You Can Improve | Carol Dweck - TED Talk on Mindsets and the Power of “Yet”
• The New Science of Learning: How to Learn in Haromony with your Brain by Terry Doyle and Todd Zakrajsek - Great Book on Learning
• Constructivism on Wikipedia - Article about Jean Piaget’s Learning Philosophy
• Toward a Developmental Epistemology of Computer Programming by Raymond Lister - Introduces the Stages of Learning to Program

Video Script

Before we launch into the course itself, I wanted to take a few minutes to share some information with you regarding what we know about how students learn to program. This isn’t just anecdotal evidence from computer science teachers like me, but theories and research from education researchers who study how humans learn new skills and abilities throughout their lives.If I had to summarize all of this information in as few words as possible, I’d simply say “do the work.” Learning to program is difficult, and the only way to really get good at it is through constant practice and learning. However, that greatly oversimplifies the information that I want to share, and I’m hoping that you’ll find some helpful takeaways from this video that you can incorporate into your learning process.

Before I begin, I want go give all the credit to Nathan Bean for developing this information as part of his CIS 400 course. He graciously allowed me to use his hard work here, and I encourage you to check out his original version, which is available at the URL shown on this slide.

The statement “do the work” is a shorter version of a very common quote from educators, which is “the person doing the work is the person doing the learning.” I couldn’t find a solid reference for who said it first, so I’ll just attributed it to various educators throughout time. This really highlights one of the biggest struggles many students run into when learning to program. There are so many guides online, and the answer to many simple problems can be found through a quick Google search. You can just copy and paste the code, and then your program works. However, did you really learn how to write that program and what it does, or just how to find a quick answer? While this may be a useful tactic from time to time, if you rely too much on other people to do your coding, you really won’t learn it yourself. This is just like learning to shoot free throws on a basketball court or beating your best time in a speedrun - you can’t just watch someone do it and expect to do it yourself (believe me, I’ve tried). So, if you aren’t doing the work, you aren’t really learning.

Next, let’s address a major myth in computer science. I’ve heard this many times: “some people are just natural born programmers, and others simply cannot learn to program.” And yes, on the surface, it may appear to be this way. Some students just seem to have a knack for programming, and you may sit and struggle and not really get anywhere. However, there is no innate skill or ability that makes you good at programming.

Instead, let’s reframe what it means to learn programming. At its core, programming is learning to write steps to solve problems in a way that a computer can perform those steps. That’s really what we are doing when we learn programming.

So, we must focus on learning how to write those steps with the proper exactitude and precision so that they make sense, and we must understand how a computer functions to be able to program that computer effectively. So, when you see someone who is good at programming, it’s not because they are good at some esoteric skill that you’ll never have - they just know how to express their steps properly and know enough about how a computer works to make their program do what they want. That’s really it! And, to be honest, after a single semester of learning to program, you’ll have all the skills you need to do both of those things! If you know how to make conditionals, loops, functions, and use simple variables and arrays, that’s really all you need. Everything else that comes after that is just refining those skills to make your programs more powerful and your coding more efficient.

So, how do we learn these skills? Well, there are a couple of important pieces we need to make sure are in the right place first. For starters, we need to have the correct mindset. Many times I’ll see students struggle to learn how to program, and they’ll say things like what you see on this slide. “Its too hard.” “I don’t understand this.” “I give up.” Statements like this are the sign of a “fixed mindset,” and they can be one of the greatest blockers preventing you from really learning to program. Just like learning any other skill, you have to be open to instruction and willing to learn, or else you’ve failed before you even started.

Instead, we want to focus on building a growth mindset. In the TED talk by Carol Dweck that is linked below this video, which I encourage you to watch, she talks about the power of “yet.” We can turn these statements around by simply adding positive power of “yet” - “I don’t understand this yet.” “I love a good challenge.” “I’ll keep trying until I get it.” Going into a programming project with a mindset that is open to growth and change is really an important first steps. When I feel like I’m getting a fixed mindset, I like to think about how difficult it would be to teach a child to tie their shoes if they don’t want to learn. As soon as I realize that, it is pretty easy to recognize that same problem in myself and work to correct it.

So, once we have our growth mindset, how do we actually learn to program? To understand that, let’s dive a bit into the world of educational theory and the work of Jean Piaget. Piaget was a biologist and psychologist who studied how young children acquired new knowledge, and he helped pioneer the concept of Constructivism, one of the most influential philosophies in education. You can read more about Constructivism in the links below this video.

One particular thing that Piaget worked on was a theory of genetic epistemology. Epistemology is the term for the study of human knowledge, so genetic epistemology is the study of the origins, or genesis, of that knowledge. Put more clearly, it’s the study of how humans create new knowledge. This concept was inspired by research done on snails - he was able to prove that two previously distinct species of snails were actually the same by moving snails from one habitat to another and observing how they modified their behaviors and how their shells grew to match the snails in the new habitat. Put clearly, the snails displayed an altered behavior based on their environment. They tried to exist in equilibrium with their environment by adapting their behaviors to fit what they now experienced in the word.

Piaget suspected that something similar happens when humans try to learn something - the brain tries to adapt itself to maintain an equilibrium in its environment, which in this case is the existing knowledge it contains. So, when the brain is exposed to new ideas, it must somehow adjust to account for that new information. Piaget proposed two different mechanisms for how this occurs: assimilation and accommodation. In assimilation, new knowledge can be added to existing structures in the brain. For example, if you are exposed to a new color, such as periwinkle, you can see that it falls somewhere between blue and violet, two colors you already know. So, you can assimilate that new knowledge into the existing knowledge without a major disruption to your mental structure of existing colors. Accommodation, on the other hand, happens when your brain must radically adapt to new information for which no existing structures exist. This can be very difficult, and can lead to a lot of struggle and frustration when trying to get “over the hump” on a new subject. Think about learning algebra or a new language for the first time - you really don’t have anything you can use to help understand this new material, so you just have to keep at it until those new structures are formed in your brain.

Unfortunately, to achieve accommodation, your brain simply has to build brand new structures to store and represent all of this new information, and that process is difficult and takes time. Put another way, it takes significant stimulus, usually in the form of doing homework, struggling with difficult problems and wrestling with the new information to try and understand it all, to create enough disequilibrium in your brain that, coupled with a growth mindset, will allow accommodation to occur. However, when all the pieces are in the right place, and you work hard and have a growth mindset, then…

EUREKA! The structures will form, and you’ll get over that huge hurdle, and things will start falling into place. It may not happen all at once, but it does happen (you’ve probably had it happen to you several times already - think about some eureka moments from your past - were they related to learning a new skill?). Of course, there’s a good chance that your brain might form a few incorrect structures in the process, so you’ll have to overcome those as you continue to learn. I still struggle to spell some words because my brain formed incorrect structures when I was still learning. But, if you continue to work hard and be open to learning, you’ll eventually sort those errors out as well.

Let’s look at one other concept in education, which is called stage theory. Piaget identified four stages that children go through as they learn to reason about the world. Those four stages are shown on this slide. In the sensorimotor stage, the child is just using their senses to interact with the world, without any real understanding of what will happen when they perform an action. This is best represented by babies and toddlers, who touch and taste everything in their surroundings. Next, the preoperational stage is represented in young children as they start to think symbolically about the world, using pictures and words to represent actions and objects. They then progress to the concrete operational stage, where they can begin to think logically and understand how concrete events happen. They can also start to think inductively, building the general principles of the world from their specific experiences. For example, if they observe that cooked spaghetti is better than raw spaghetti, they might reason that other foods like potatoes are better cooked than raw. Finally, the last stage is the formal operational stage. This stage is represented by the ability to work fully with an abstract work, formulating and testing hypotheses to truly understand how the world works and predict how new items will work before experiencing them firsthand.

Many later researchers built upon this model to show that adults learn in much the same way. They also discovered that the stages are not rigid, and you may exhibit behaviors from multiple stages at any given time. This is called the “overlapping waves” model, and is shown here in this diagram. So, as you learn new skills, you may be at the operational stage in some areas, but still at the preoperational stage in other areas. This explains why some concepts may make sense while others don’t for a while - you just have to keep going until it all fits together.

So, how can we apply all of this information to programming? One theory comes from the work of Lister and Teague, who proposed a developmental epistemology of computer programming. Put another way, they applied this theory to computer science education, and gave us a unique way to think about the different stages of learning to program.

At the sensorimotor stage, we’re just getting the basics. So, when given a piece of code and asked to trace what it does, we still make lots of errors and get the answer incorrect. If we want to get a program to work ourselves, it usually involves a lot of trial and error, and many times when it does end up working we don’t even know exactly why it worked that time, but we’re building up a baseline of information that we can use to construct our mental model of how a computer works.

As we progress into the preoperational stage, we become better at tracing code correctly, but we still struggle to understand what the program itself does. We see each line of code as a separate instruction, but not the entire program. A great analogy is reading a recipe that calls for flour, water, salt, and yeast. Will it make bread? Biscuits? Pie crust? We’re not sure yet, but at least we can recognize the ingredients. To solve problems at this stage, we typically will randomly adjust pieces of our code that we don’t quite understand and see what it does, trying to form a better idea of the importance of each line in the code.

Eventually, we’ll get to the concrete operational stage. At this stage, we can construct our own programs, but many times we are simply piecing together parts that we’ve used before and performing some futile patches and bugfixes as we refine the program. We can also work backwards to figure out what a program does from execution results, but we still aren’t very good at deducing the results from the code itself. However, we’re starting to work with abstraction, though we tend to simplify things to a level that we are more comfortable with.

Finally, we’ll reach the formal operational stage. At this stage, we can comfortable read and understand code without executing it, quickly seeing what it does and how it works without fully tracing it ourselves. We can also start to form hypotheses for how to build new programs and code, and reason about whether different approaches would work better or worse than others. This is the goal stage for any programmer! Once you have reached this stage, then you’ll feel totally at home working in code and developing your own programs from scratch.

So, how can we enable ourselves to be the best learners we can be? There is lots of interesting research in that area, best summarized in the book “The New Science of Learning” that is linked below this video. Let’s go through a few of the big concepts.

First, getting ample and regular sleep is important, because it allows your brain to build those knowledge structures we discussed earlier and store the memories from the day in long-term storage. Without enough sleep, your brain is unable to process memories offline and make them ready for retrieval later on, an important step in learning. Also, consuming large amounts of caffeine or alcohol can disrupt your sleep patterns, so keep that in mind before you pour that next cup of coffee or go out partying. You can also take advantage of modern technology to help you track your sleep - most smart watches and smartphones today can help with that!

Likewise, regular exercise is important to both your physical and mental health. When you exercise, especially aerobic exercise that gets your heart rate up, your body releases neurochemicals that help your brain cells communicate. In addition, just getting up and moving around regularly helps keep your body healthy, so take regular breaks, and consider getting a standing desk for some extra benefits.

Research also shows that engaging your senses is an important part in learning. This is why we, as teachers, try to vary our lessons with pictures, videos, activities, and more. It is also the basis of the cognitive apprenticeship style of learning that we use, which you can learn more about in the links below this video. We show you the code we are writing, engaging your sense of vision, while talking about it so you are also listening, and then you are writing your own version, using your sense of touch. You can build upon this by using your senses while you learn by taking notes during a lecture video, building concept maps, and even printing out and writing on your code and these lecture scripts. All of these processes help engage different parts of your brain and make it that much easier to build new knowledge structures.

Looking for patterns is another important way to understand programming. There are many common patterns in computer programs, such as using a for loop to iterate through an array, or an if-else statement to determine if a particular variable is set to a valid value. By recognizing and understanding those patterns, we can more quickly understand new programs that use slightly different versions of the same code. Humans are naturally very good at pattern recognition, and it is one of the reasons why we see the same code structures time and time again - not because they are the only way to accomplish that goal, but because that structure is commonly used across many programs and therefore is easier to understand.

There is quite a bit of research into how memories are formed and how we can adjust our studying habits to take advantage of that. For example, cognitive science shows that the parts of our brain responsible for memory creation are active up to one hour after a learning experience has ended, such as a lecture video or activity. So, instead of jumping to the next task, you may want to take a little while to reflect on what you just did and let it sink in before moving on. Likewise, to build strong memories, it is important to constantly recall the memory or use the skills you’ve learned to strengthen their structures in the brain. This is why teachers like to throw in a few questions from a previous exam or quiz every once in a while - it helps strengthen those structures by forcing you to recall information you’ve learned previously. On the other hand, many students try to “cram” a bunch of information right before an exam, only to forget it soon after because it wasn’t recalled more than once. As you progress further, we’ll continue to come back to concepts you’ve already learned and build upon them, a process called elaboration that helps reinforce what you’ve already learned while building new, related knowledge.

Finally, it is important to remember that we must give our brains the space it needs to focus on the task at hand. Multitasking while learning, such as watching YouTube or Twitch, chatting with friends, or listening to a lecture video while coding can all reduce your brain’s ability to form strong memories and do well. In fact, research shows that individuals who try to multitask tend to make 50% more errors and spend 50% more time on both tasks. So, instead of giving yourself distractions, try to find things that will help you focus better - there are some great playlists online for music without lyrics that can help you focus or code better, and you can easily mute notifications on your phone and on your computer for an hour or so while you work.

So, let’s summarize what we’ve covered here. First, and most importantly, remember that you can learn to program, just like the many students who have done it before you. However, it can be difficult and frustrating at times, and it will take lots of hard work on your part to make it happen. That means that you’ll need to read and write a lot of code before it really starts to make sense. In short, you must do the work to learn to program.

That said, you can help make the process easier by getting good sleep, exercising regularly, and engaging fully with all of the content in the course. That means you’ll need to take your own notes, maybe draw some diagrams, and annotate code you write and code you read to help you understand it. While you are working, try not to multitask so you can focus. If you are given some code to include in your program, don’t copy/paste it - rewrite it, and make sure you completely understand what each line does. Finally, take some time to read code written by others! GitHub is a great place to discover all sorts of code and see how others write code. If you want to write good poetry you have to read lots of good poetry, and the same goes for coding.

With that in mind, I hope you are able to make the best of this course and continue to develop your programming skills. If you are interested in this topic and would like to know more about things you can do to be a better learner, let us know! As you can imagine, teachers like me love to talk about this stuff, so don’t be afraid to ask. Good luck!

Spring 2024 Syllabus

CC 310 - Data Structures & Algorithms I - Fall 2024

Previous Versions

Instructor Contact Information

• Instructor: Russell Feldhausen (russfeld AT ksu DOT edu)
  I use he/him pronouns. Feel free to share your own pronouns with me, and I’ll do my best to use them!
• Office: DUE 2213, but I mostly work remotely from Kansas City, MO
• Phone: (785) 292-3121 (Call/Text)
• Website: https://russfeld.me
• Virtual Office Hours: By appointment via Zoom. Schedule a meeting at https://calendly.com/russfeld

Preferred Methods of Communication:

• Email: Students should email cc310-help (cc310-help@KSUemailProd.onmicrosoft.com). We will try to respond within one business day.
• Ed Discussion: For short questions and discussions of course content and assignments, Ed Discussion is preferred since questions can be asked once and answered for all students. Students are encouraged to post questions there and use that space for discussion, and the instructor will strive to answer questions there as well.
• Phone/Text: Emergencies only! We will do our best to respond as quickly as we can.

Prerequisites

• MATH 100 - College Algebra
• CC 210 - Fundamental Computer Programming Concepts

Course Overview

Exploration of data structures & related algorithms in computer programming. Basic concepts of complexity analysis. Object-oriented design concepts.

Course Description

This course introduces simple data structures such as sets, lists, stacks, queues, and maps. Students learn how to create data structures and the algorithms that use them. Students are introduced to algorithm analysis to determine the efficiency of algorithms.

Major Course Topics

• Data Structures
  • Sets
  • Lists
  • Stacks
  • Queues
  • Maps
• Algorithms
  • Searching
  • Sorting
  • Structural Operations
  • Hashing
  • Set Relations
• Recursion
• Complexity Analysis
• Algorithm Design Strategies and Patterns
• Logic: Preconditions, Postconditions and Invariants

Course Structure

These courses are being taught 100% online, and each module is self-paced. There may be some bumps in the road as we refine the overall course structure. Students will work at their own pace through a set of modules, with approximately one module being due each week. Material will be provided in the form of recorded videos, online tutorials, links to online resources, and discussion prompts. Each module will include a coding project or assignment, many of which will be graded automatically through Codio. Assignments may also include portions which will be graded manually via Canvas or other tools.

A common axiom in learner-centered teaching is “the person doing the work is the person doing the learning.” What this really means is that students primarily learn through grappling with the concepts and skills of a course while attempting to apply them. Simply seeing a demonstration or hearing a lecture by itself doesn’t do much in terms of learning. This is not to say that they don’t serve an important role - as they set the stage for the learning to come, helping you to recognize the core ideas to focus on as you work. The work itself consists of applying ideas, practicing skills, and putting the concepts into your own words.

The Work

There is no shortcut to becoming a great programmer. Only by doing the work will you develop the skills and knowledge to make you a successful computer scientist. This course is built around that principle, and gives you ample opportunity to do the work, with as much support as we can offer.

Tutorials, Quizzes & Examples: Each module will include many tutorial assignments, quizzes, and examples that will take you step-by-step through using a particular concept or technique. The point is not simply to complete the example, but to practice the technique and coding involved. You will be expected to implement these techniques on your own in the milestone assignment of the module - so this practice helps prepare you for those assignments.

Programming Assignments: Throughout the semester you will be building several programming projects that explore the topics, data structures, and algorithms introduced in this class. Each programming project may include multiple tasks and an automated grading system.

Grading

In theory, each student begins the course with an A. As you submit work, you can either maintain your A (for good work) or chip away at it (for less adequate or incomplete work). In practice, each student starts with 0 points in the gradebook and works upward toward a final point total earned out of the possible number of points. In this course, each assignment constitutes a portion of the final grade, as detailed below:

• 70% - Codio Programming Projects
• 30% - Codio Tutorials and Canvas Quizzes

Up to 5% of the total grade in the class is available as extra credit. See the Extra Credit - Bug Bounty & Extra Credit - Helping Hands assignments for details.

Letter grades will be assigned following the standard scale:

• 90% - 100% → A
• 80% - 89.99% → B
• 70% - 79.99% → C
• 60% - 69.99% → D
• 00% - 59.99% → F

Collaboration Policy

In this course, all work submitted by a student should be created solely by the student without any outside assistance beyond the instructor and TA/GTAs. Students may seek outside help or tutoring regarding concepts presented in the course, but should not share or receive any answers, source code, program structure, or any other materials related to the course. Learning to debug coding problems is a vital skill, and students should strive to ask good questions and perform their own research instead of just sharing broken source code when asking for assistance.

Late Work

Since this course is entirely online, students may work at any time and at their own pace through the modules. However, to keep everyone on track, there will be approximately one module due each week. Each graded item in the module will have a specific due date specified. Any assignment submitted late will have that assignment’s grade reduced by 10% of the total possible points on that project for each day it is late. This penalty will be assessed automatically in the Canvas gradebook. For the purposes of record keeping, a combination of the time of a submission via Canvas and the creation of a release in GitHub will be used to determine if the assignment was submitted on time.

However, even if a module is not submitted on time, it must still be completed before a student is allowed to begin the next module. So, students should take care not to get too far behind, as it may be very difficult to catch up.

Finally, all course work must be submitted on or before the last day of the semester in which the student is enrolled in the course in order for it to be graded on time.

If you have extenuating circumstances, please discuss them with the instructor as soon as they arise so other arrangements can be made. If you find that you are getting behind in the class, you are encouraged to speak to the instructor for options to make up missed work.

Incomplete Policy

Students should strive to complete this course in its entirety before the end of the semester in which they are enrolled. However, since retaking the course would be costly and repetitive for students, we would like to give students a chance to succeed with a little help rather than immediately fail students who are struggling.

If you are unable to complete the course in a timely manner, please contact the instructor to discuss an incomplete grade. Incomplete grades are given solely at the instructor’s discretion. See the official K-State Grading Policy for more information. In general, poor time management alone is not a sufficient reason for an incomplete grade.

Unless otherwise noted in writing on a signed Incomplete Agreement Form, the following stipulations apply to any incomplete grades given in Computational Core courses:

1. Students may receive at most two incompletes in Computational Core courses throughout their time in the program
2. Students will be given 6 calendar weeks from the end of the enrolled semester’s finals week to complete the course
3. Any modules in a future CC course which depend on incomplete work will not be accessible until the previous course is finished
4. For example, if a student is given an incomplete in CC 210, then all modules in CC 310 will be inaccessible until CC 210 is complete
5. Students understand that access to instructor and GTA assistance may be limited after the end of an academic semester due to holidays and other obligations
6. If a student fails to resolve an incomplete grade after 6 weeks, they will be assigned an ‘F’ in the course. In addition, they will be dropped from any other Computational Core courses which require the failed course as a prerequisite or corequisite.

Recommended Texts & Supplies

To participate in this course, students must have access to a modern web browser and broadband internet connection. All course materials will be provided via Canvas and Codio. Modules may also contain links to external resources for additional information, such as programming language documentation.

Students will make use of GitHub or GitLab for source code management.

Students may choose to do some development work on their own computer. The recommended software is Visual Studio Code along with access to a system running Ubuntu. For Windows systems, Ubuntu can be installed via the Windows Subsystem for Linux. For Mac systems, Ubuntu can be installed in a virtual machine through VirtualBox.

Subject to Change

The details in this syllabus are not set in stone. Due to the flexible nature of this class, adjustments may need to be made as the semester progresses, though they will be kept to a minimum. If any changes occur, the changes will be posted on the Canvas page for this course and emailed to all students. All changes may also be posted to Canvas.

Standard Syllabus Statements

Academic Honesty

Kansas State University has an Honor and Integrity System based on personal integrity, which is presumed to be sufficient assurance that, in academic matters, one’s work is performed honestly and without unauthorized assistance. Undergraduate and graduate students, by registration, acknowledge the jurisdiction of the Honor and Integrity System. The policies and procedures of the Honor and Integrity System apply to all full and part-time students enrolled in undergraduate and graduate courses on-campus, off-campus, and via distance learning. A component vital to the Honor and Integrity System is the inclusion of the Honor Pledge which applies to all assignments, examinations, or other course work undertaken by students. The Honor Pledge is implied, whether or not it is stated: “On my honor, as a student, I have neither given nor received unauthorized aid on this academic work.” A grade of XF can result from a breach of academic honesty. The F indicates failure in the course; the X indicates the reason is an Honor Pledge violation.

For this course, a violation of the Honor Pledge will result in sanctions such as a 0 on the assignment or an XF in the course, depending on severity. Actively seeking unauthorized aid, such as posting lab assignments on sites such as Chegg or StackOverflow, or asking another person to complete your work, even if unsuccessful, will result in an immediate XF in the course.

This course assumes that all your course work will be done by you. Use of AI text and code generators such as ChatGPT and GitHub Copilot in any submission for this course is strictly forbidden unless explicitly allowed by your instructor. Any unauthorized use of these tools without proper attribution is a violation of the K-State Honor Pledge.

We reserve the right to use various platforms that can perform automatic plagiarism detection by tracking changes made to files and comparing submitted projects against other students’ submissions and known solutions. That information may be used to determine if plagiarism has taken place.

Students with Disabilities

At K-State it is important that every student has access to course content and the means to demonstrate course mastery. Students with disabilities may benefit from services including accommodations provided by the Student Access Center. Disabilities can include physical, learning, executive functions, and mental health. You may register at the Student Access Center or to learn more contact:

• Manhattan/Olathe/Global Campus – Student Access Center
  • accesscenter@k-state.edu
  • 785-532-6441
• K-State Salina Campus – Julie Rowe; Student Success Coordinator
  • jarowe@k-state.edu
  • 785-820-7908

Students already registered with the Student Access Center please request your Letters of Accommodation early in the semester to provide adequate time to arrange your approved academic accommodations. Once SAC approves your Letter of Accommodation it will be e-mailed to you, and your instructor(s) for this course. Please follow up with your instructor to discuss how best to implement the approved accommodations.

Expectations for Conduct

All student activities in the University, including this course, are governed by the Student Judicial Conduct Code as outlined in the Student Governing Association By Laws, Article V, Section 3, number 2. Students who engage in behavior that disrupts the learning environment may be asked to leave the class.

Mutual Respect and Inclusion in K-State Teaching & Learning Spaces

At K-State, faculty and staff are committed to creating and maintaining an inclusive and supportive learning environment for students from diverse backgrounds and perspectives. K-State courses, labs, and other virtual and physical learning spaces promote equitable opportunity to learn, participate, contribute, and succeed, regardless of age, race, color, ethnicity, nationality, genetic information, ancestry, disability, socioeconomic status, military or veteran status, immigration status, Indigenous identity, gender identity, gender expression, sexuality, religion, culture, as well as other social identities.

Faculty and staff are committed to promoting equity and believe the success of an inclusive learning environment relies on the participation, support, and understanding of all students. Students are encouraged to share their views and lived experiences as they relate to the course or their course experience, while recognizing they are doing so in a learning environment in which all are expected to engage with respect to honor the rights, safety, and dignity of others in keeping with the K-State Principles of Community.

If you feel uncomfortable because of comments or behavior encountered in this class, you may bring it to the attention of your instructor, advisors, and/or mentors. If you have questions about how to proceed with a confidential process to resolve concerns, please contact the Student Ombudsperson Office. Violations of the student code of conduct can be reported using the Code of Conduct Reporting Form. You can also report discrimination, harassment or sexual harassment, if needed.

Netiquette

Online communication is inherently different than in-person communication. When speaking in person, many times we can take advantage of the context and body language of the person speaking to better understand what the speaker means, not just what is said. This information is not present when communicating online, so we must be much more careful about what we say and how we say it in order to get our meaning across.

Here are a few general rules to help us all communicate online in this course, especially while using tools such as Canvas or Discord:

• Use a clear and meaningful subject line to announce your topic. Subject lines such as “Question” or “Problem” are not helpful. Subjects such as “Logic Question in Project 5, Part 1 in Java” or “Unexpected Exception when Opening Text File in Python” give plenty of information about your topic.
• Use only one topic per message. If you have multiple topics, post multiple messages so each one can be discussed independently.
• Be thorough, concise, and to the point. Ideally, each message should be a page or less.
• Include exact error messages, code snippets, or screenshots, as well as any previous steps taken to fix the problem. It is much easier to solve a problem when the exact error message or screenshot is provided. If we know what you’ve tried so far, we can get to the root cause of the issue more quickly.
• Consider carefully what you write before you post it. Once a message is posted, it becomes part of the permanent record of the course and can easily be found by others.
• If you are lost, don’t know an answer, or don’t understand something, speak up! Email and Canvas both allow you to send a message privately to the instructors, so other students won’t see that you asked a question. Don’t be afraid to ask questions anytime, as you can choose to do so without any fear of being identified by your fellow students.
• Class discussions are confidential. Do not share information from the course with anyone outside of the course without explicit permission.
• Do not quote entire message chains; only include the relevant parts. When replying to a previous message, only quote the relevant lines in your response.
• Do not use all caps. It makes it look like you are shouting. Use appropriate text markup (bold, italics, etc.) to highlight a point if needed.
• No feigning surprise. If someone asks a question, saying things like “I can’t believe you don’t know that!” are not helpful, and only serve to make that person feel bad.
• No “well-actually’s.” If someone makes a statement that is not entirely correct, resist the urge to offer a “well, actually…” correction, especially if it is not relevant to the discussion. If you can help solve their problem, feel free to provide correct information, but don’t post a correction just for the sake of being correct.
• Do not correct someone’s grammar or spelling. Again, it is not helpful, and only serves to make that person feel bad. If there is a genuine mistake that may affect the meaning of the post, please contact the person privately or let the instructors know privately so it can be resolved.
• Avoid subtle -isms and microaggressions. Avoid comments that could make others feel uncomfortable based on their personal identity. See the syllabus section on Diversity and Inclusion above for more information on this topic. If a comment makes you uncomfortable, please contact the instructor.
• Avoid sarcasm, flaming, advertisements, lingo, trolling, doxxing, and other bad online habits. They have no place in an academic environment. Tasteful humor is fine, but sarcasm can be misunderstood.

As a participant in course discussions, you should also strive to honor the diversity of your classmates by adhering to the K-State Principles of Community.

SafeZone Ally

I am part of the SafeZone community network of trained K-State faculty/staff/students who are available to listen and support you. As a SafeZone Ally, I can help you connect with resources on campus to address problems you face that interfere with your academic success, particularly issues of sexual violence, hateful acts, or concerns faced by individuals due to sexual orientation/gender identity. My goal is to help you be successful and to maintain a safe and equitable campus.

Discrimination, Harassment, and Sexual Harassment

Kansas State University is committed to maintaining academic, housing, and work environments that are free of discrimination, harassment, and sexual harassment. Instructors support the University’s commitment by creating a safe learning environment during this course, free of conduct that would interfere with your academic opportunities. Instructors also have a duty to report any behavior they become aware of that potentially violates the University’s policy prohibiting discrimination, harassment, and sexual harassment, as outlined by PPM 3010.

If a student is subjected to discrimination, harassment, or sexual harassment, they are encouraged to make a non-confidential report to the University’s Office for Institutional Equity (OIE) using the online reporting form. Incident disclosure is not required to receive resources at K-State. Reports that include domestic and dating violence, sexual assault, or stalking, should be considered for reporting by the complainant to the Kansas State University Police Department or the Riley County Police Department. Reports made to law enforcement are separate from reports made to OIE. A complainant can choose to report to one or both entities. Confidential support and advocacy can be found with the K-State Center for Advocacy, Response, and Education (CARE). Confidential mental health services can be found with Lafene Counseling and Psychological Services (CAPS). Academic support can be found with the Office of Student Life (OSL). OSL is a non-confidential resource. OIE also provides a comprehensive list of resources on their website. If you have questions about non-confidential and confidential resources, please contact OIE at equity@ksu.edu or (785) 532–6220.

Academic Freedom Statement

Kansas State University is a community of students, faculty, and staff who work together to discover new knowledge, create new ideas, and share the results of their scholarly inquiry with the wider public. Although new ideas or research results may be controversial or challenge established views, the health and growth of any society requires frank intellectual exchange. Academic freedom protects this type of free exchange and is thus essential to any university’s mission.

Moreover, academic freedom supports collaborative work in the pursuit of truth and the dissemination of knowledge in an environment of inquiry, respectful debate, and professionalism. Academic freedom is not limited to the classroom or to scientific and scholarly research, but extends to the life of the university as well as to larger social and political questions. It is the right and responsibility of the university community to engage with such issues.

Campus Safety

Kansas State University is committed to providing a safe teaching and learning environment for student and faculty members. In order to enhance your safety in the unlikely case of a campus emergency make sure that you know where and how to quickly exit your classroom and how to follow any emergency directives. Current Campus Emergency Information is available at the University’s Advisory webpage.

Weapons Policy

Kansas State University prohibits the possession of firearms, explosives, and other weapons on any University campus, with certain limited exceptions, including the lawful concealed carrying of handguns, as provided in the University Weapons Policy.

You are encouraged to take the online weapons policy education module to ensure you understand the requirements of the policy, including the requirements related to concealed carrying of handguns on campus. Students possessing a concealed handgun on campus must be lawfully eligible to carry and either at least 21 years of age or a licensed individual who is 18-21 years of age. All carrying requirements of the policy must be observed in this class, including but not limited to the requirement that a concealed handgun be completely hidden from view, securely held in a holster that meets the specifications of the policy, carried without a chambered round of ammunition, and that any external safety be in the “on” position.

If an individual carries a concealed handgun in a personal carrier such as a backpack, purse, or handbag, the carrier must remain within the individual’s exclusive and uninterrupted control. This includes wearing the carrier with a strap, carrying or holding the carrier, or setting the carrier next to or within the immediate reach of the individual.

During this course, you will be required to engage in activities, such as interactive examples or sharing work on the whiteboard, that may require you to separate from your belongings, and thus you should plan accordingly.

Each individual who lawfully possesses a handgun on campus shall be wholly and solely responsible for carrying, storing and using that handgun in a safe manner and in accordance with the law, Board policy and University policy. All reports of suspected violation of the weapons policy are made to the University Police Department by picking up any Emergency Campus Phone or by calling 785-532-6412.

Student Resources

K-State has many resources to help contribute to student success. These resources include accommodations for academics, paying for college, student life, health and safety, and others. Check out the Student Guide to Help and Resources: One Stop Shop for more information.

Student Academic Creations

Student academic creations are subject to Kansas State University and Kansas Board of Regents Intellectual Property Policies. For courses in which students will be creating intellectual property, the K-State policy can be found at University Handbook, Appendix R: Intellectual Property Policy and Institutional Procedures (part I.E.). These policies address ownership and use of student academic creations.

Mental Health

Your mental health and good relationships are vital to your overall well-being. Symptoms of mental health issues may include excessive sadness or worry, thoughts of death or self-harm, inability to concentrate, lack of motivation, or substance abuse. Although problems can occur anytime for anyone, you should pay extra attention to your mental health if you are feeling academic or financial stress, discrimination, or have experienced a traumatic event, such as loss of a friend or family member, sexual assault or other physical or emotional abuse.

If you are struggling with these issues, do not wait to seek assistance.

• Kansas State University Counseling and Psychological Services offers free and confidential services to assist you to meet these challenges.
• Lafene Health Center has specialized nurse practitioners to assist with mental health.
• The Office of Student Life can direct you to additional resources.
• K-State Family Center offers individual, couple, and family counseling services on a sliding fee scale.
• Center for Advocacy, Response, and Education (CARE) provides free and confidential assistance for those in our K-State community who have been victimized by violence.

For Kansas State Salina Campus:

• Kansas State Salina Counseling Services offers free and confidential services to assist you to meet these challenges.
• The Kansas State Salina Office of Student Life can direct you to additional resources.
• The Kansas State Salina Campus offers several services for students, including health services, counseling, and academic assistance.

For Global Campus/K-State Online:

• K-State Online students have free access to mental health counseling with My SSP - 24/7 support via chat and phone.
• The Office of Student Life can direct you to additional resources.

University Excused Absences

K-State has a University Excused Absence policy (Section F62). Class absence(s) will be handled between the instructor and the student unless there are other university offices involved. For university excused absences, instructors shall provide the student the opportunity to make up missed assignments, activities, and/or attendance specific points that contribute to the course grade, unless they decide to excuse those missed assignments from the student’s course grade. Please see the policy for a complete list of university excused absences and how to obtain one. Students are encouraged to contact their instructor regarding their absences.

Copyright Notice

© The materials in this online course fall under the protection of all intellectual property, copyright and trademark laws of the U.S. The digital materials included here come with the legal permissions and releases of the copyright holders. These course materials should be used for educational purposes only; the contents should not be distributed electronically or otherwise beyond the confines of this online course. The URLs listed here do not suggest endorsement of either the site owners or the contents found at the sites. Likewise, mentioned brands (products and services) do not suggest endorsement. Students own copyright to what they create.

Plagiarism Policy

Resources

• K-State Honor & Integrity System

Video Script

“On my honor, as a student, I have neither given nor received unauthorized aid on this academic work.” - K-State Honor Pledge

Plagiarism is a very serious concern in this course, and something that we do not take lightly. Computer programs and code are especially easy targets for plagiarism due to how easy it is to copy and manipulate code in such a way that it is unrecognizable as the original source but still performs correctly.

At its core, plagiarism is taking someone else’s work and passing it off as your own without giving appropriate credit to the original source. As a student at K-State, you are bound by the K-State Honor Code not to accept any unauthorized aid, and this includes plagiarized code.

When it comes to plagiarism in computer code, there is a fine line between using resources appropriately and copying code. In this program, you should strive to avoid plagiarism issues by doing the following:

1. Do not search for or use any complete solutions to projects in this course found online or from fellow students.
2. Small portions of code may be used or adapted from an online source with proper citation. To cite a piece of code, include a code comment section above it that contains the original source URL and a description of why it was used.

In general, copying or adapting small pieces of code to perform auxiliary functions in the assignment is permitted. Copying or adapting code that is the general goal of the assignment should be avoided. For example, if the assignment is to create a bubble sort algorithm, you should write the algorithm from scratch yourself since that is the goal of the assignment. If the assignment is to create a program for displaying data that you feel should be sorted, you may choose to adapt an existing sorting algorithm for your needs (or use one from a library).

If you aren’t sure about whether it is OK to use an online resource or piece of code in this course, please contact the instructors using the course discussion forums or help email address. You will not get in trouble for asking, and it will help you determine what the best course of action is. Plagiarism can really only occur when you submit the assignment for grading, so you are welcome to ask for clarification or a judgement on whether a particular usage is acceptable at any time before you submit the assignment.

Codio has features that will compare your submissions against those of your fellow students. Any submissions with a high degree of similarity may be subjected to additional scrutiny by the instructors to determine if plagiarism has occurred.

In this course, any violation of the K-State Honor Code will result in a 0 on that assignment and a report made to the K-State Honor Council. A second violation will result in an XF in this course, as well as any additional sanctions imposed by the K-State Honor Council.

For more information on the K-State Honor & Integrity system, please visit their website, which is linked in the resources section below this video.

Programming Overview

Programming

¹

Programming is the act of writing source code for a computer program in such a way that a modern computer can understand and perform the steps described in the code. There are many different programming languages that can be used, such as high-level languages like Java and Python.

To run code written in those languages, we can use a compiler to convert the code to a low-level language that can be directly executed by the computer, or we can use an interpreter to read the code and perform the requested operations on the computer.

At this point, we have most likely written some programs already. This chapter will review the important aspects of our chosen programming language, giving us a solid basis to build upon. Hopefully most of this will be review, but there may be a few new terms or concepts introduced here as well.

Flowcharts and Pseudocode

In this course, we will primarily be learning different ways to store and manipulate data in our programs. Of course, we could do this using the source code of our chosen programming language, but in many cases that would defeat the purpose of learning how to do it ourselves!

Instead, we will use several different ways to represent the steps required to build our programs. Let’s review a couple of them now.

Natural Language

One of the simplest ways to describe a computer program is to simply write what it does using our preferred language, such as English. Of course, natural language can be very ambiguous, so we must be careful to make our written descriptions as precise as possible. So, it is a good idea to limit ourselves to simple, clear sentences that aren’t written as prose. It may seem a bit boring, but this is the best way to make sure our intent is completely understood.

A great example is a recipe for baking. Each step is written clearly and concisely, with enough descriptive words used to allow anyone to read and follow the directions.

Flowcharts

One method of representing computer programs is through the use of flowcharts. A flowchart consists of graphical blocks representing individual operations to be performed, connected with arrows which describe the flow of the program. The image above gives the basic building blocks of the flowcharts that will be used in this course. We will mostly follow the flowchart design used by the Flowgorithm program available online. The following pages in this chapter will introduce and discuss each block in detail.

Pseudocode

We can also express our computer programs through the use of pseudocode. Pseudocode is an abstract language that resembles a high-level programming language, but it is written in such a way that it can be easily understood by any programmer who is familiar with any one of several common languages. The pseudocode may not be directly executable as written, but it should contain enough detail to be easily understood and adapted to an actual programming language by a skilled programmer.

There are many standards that exist for pseudocode, each with their own unique features and uses. In this course, we will mostly follow the standards from the International Baccalaureate Organization. In the following pages in this chapter, we’ll also introduce pseudocode for each of the flowchart blocks shown above.

References

• Flowgorithm
• International Baccalaureate Organization Pseudocode

Syntax Overview

Let’s discuss some of the basic concepts we need to understand about the Python programming language.

Program Structure

To begin, let’s look at a simple Hello World program written in Python:

def main():
    print("Hello World!")


# main guard
if __name__ == "__main__":
    main()

This program contains multiple important parts:

1. First, we define a function called main(). Python does not require us to do this, since we can write our code directly in the file and it will execute. However, since we are going to be building larger programs in this course, it is a good idea to start using functions now.
2. The function definition ends with a colon :, and then the code inside of that function comes directly after it. The code contained in the function must be indented a single level. By convention, Python files should use 4 spaces to indent the code. Thankfully, Codio does that for us automatically.
3. At the bottom of the file, we’ve included a main guard that determines if this file is being executed. If it is, it will call the main() function to run the program.

Of course, this is a very brief overview for the Python programming language. To learn more, feel free to refer to the references listed below, as well as the textbook content for previous courses.

References

• The Python Tutorial from Python
• Python Tutorial from W3Schools
• Python Tutorial from Tutorials Point

Running Code

Now that we’ve written our first Python program, we must run the program to see the fruits of our labors. There are many different ways to do this using the Codio platform. We’ll discuss each of them in detail here.

Terminal

Codio includes a built-in Linux terminal, which allows us to perform actions directly on a command-line interface just like we would on an actual computer running Linux. We can access the Terminal in many ways:

1. Selecting the Tools menu, then choosing the Terminal option
2. Pressing SHIFT + ALT + T in any Codio window (you can customize this shortcut in your Codio user preferences)
3. Pressing the Open Terminal icon in the file tree
4. Selecting the Open Terminal option from the Run menu (it is the first menu to the right of the Help menu)

Additionally, some pages may already open a terminal window for us in the left-hand pane, as this page so helpfully does. As we can see, we’re never very far away from a terminal.

Let’s go to the terminal window and navigate to our program. When we first open the Terminal window, it should show us a prompt that looks somewhat like this one:

There is quite a bit of information there, but we’re interested in the last little bit of the last line, where it says ~/workspace. That is the current directory, or folder, our terminal is looking at, also known as our working directory. We can always find the full location of our working directory by typing the pwd command, short for “Print Working Directory,” in the terminal. Let’s try it now!

Enter this command in the terminal:

pwd

and we should see output similar to this:

In that output, we’ll see that the full path to our working directory is /home/codio/workspace. This is the default location for all of our content in Codio, and it’s where everything shown in the file tree to the far left is stored. When working in Codio, we’ll always want to store our work in this directory.

Next, let’s use the ls command, short for “LiSt,” to see a list of all of the items in that directory:

ls

We should see a whole list of items appear in the terminal. Most of them are directories containing examples for the chapters this textbook, including the HelloWorld.py file that we edited in the last page. Thankfully, the directories are named in a very logical way, making it easy for us to find what we need. For example, to find the directory for Chapter 1 that contains examples for Python, look for the directory with the name starting with 1p. In this case, it would be 1p-hello.

Finally, we can use the cd command, short for “Change Directory,” to change the working directory. To change to the 1p-hello directory, type cd into the terminal window, followed by the name of that directory:

cd 1p-hello

We are now in the 1p-hello directory, as we can see by observing the ~/workspace/1p-hello on the current line in the terminal. Finally, we can do the ls command again to see the files in that directory:

ls

We should see our HelloWorld.py file! If it doesn’t appear, try using this command to get to the correct directory: cd /home/codio/workspace/1p-hello.

Once we’re at the point where we can see the HelloWorld.py file, we can move on to actually running the program.

Running in Terminal

To run it, we just need to type the following in the terminal:

python3 HelloWorld.py

That’s all there is to it! We’ve now successfully run our first Python program. Of course, we can run the program as many times as we want by repeating the previous python3 command. If we make changes to the HelloWorld.py file that instruct the computer to do something different, we should see those changes the next time we run the file..

Codio Assessments

Last, but not least, many of the Codio tutorials and projects in this program will include assessments that we must solve by writing code. Codio can then automatically run the program and check for specific things, such as the correct output, in order to give us a grade. For most of these questions, we’ll be able to make changes to our code as many times as we’d like to get the correct answer.

As we can see, there are many different ways to compile and run our code using Codio. Feel free to use any of these methods throughout this course.

Debugging

Codio also includes an integrated debugger, which is very helpful when we want to determine if there is an error in our code. We can also use the debugger to see what values are stored in each variable at any point in our program.

To use the debugger, find the Debug Menu at the top of the Codio window. It is to the right of the Run Menu we’ve already been using. On that menu, we should see an option for Python - Debug File. Select that option to run our program in the Codio debugger.

As we build more complex programs in this course, we’ll be able to configure our own debugger configurations that allow us to test multiple files and operations.

The Codio debugger only works with input from a file, not from the terminal. So, to use the debugger, we’ll need to make sure the input we’d like to test is stored in a file, such as input.txt, before debugging. We can then give that file as an argument to our program in our debugger configuration, and write our program to read input from a file if one is provided as an argument.

Learning how to use a debugger is a hands-on process, and is probably best described in a video. You can find more information in the Codio documentation to get up to speed on working in the Codio debugger.

Codio Documentation - Debugger

We can always use the debugger to help us find problems in our code.

Visualizer

¹

Codio now includes support for Python Tutor, allowing us to visualize what is happening in our code. We can see that output in the second tab that is open to the left.

Unfortunately, students are not able to open the visualizer directly, so it must be configured by an instructor in the Codio lesson. If you find a page in this textbook where you’d like to be able to visualize your code, please let us know!

Variables

A variable in a programming language is an abstraction that allows storing one value in each instant of time, but this value can change along with the program execution. A variable can be represented as a box holding a value. If the variable is a container, e.g., a list (or array or vector), a matrix, a tuple, or a set of values, each box in the container contains a single value.

Characteristics

A variable is characterized by:

1. An identifier or name. The name represents the most important information since it allows us to identify the variable inside the program. This name has to be unique inside the program and it allows us to identify the variable. In order to improve program legibility, and facilitate debugging, and understanding it is important to choose a representative name for the variable that clearly represents the function of the variable. Representative names could be results, number_of_nodes, number_of_edges. For writing variable names composed of two or more words in Python we can use underscores to separate the words.
2. A single value, i.e. the value that is stored in the variable. The value of the variable can be modified during program execution but at each instant of time, the variable holds a single value.
3. A data type. The data type characterizes the set of values that the variable can take. For example, the integer type contains numbers without a decimal part. The decimal or floating point type contains numbers with a decimal part. In mathematics, we call these real numbers. The string type (text) characterizes character sequences, and the Boolean type contains true or false values and is used to hold the result of the conditions. In some untyped languages, like Scratch and Python, the data type is deduced from the value that contains the variable. Since the value can change, its type can also change. For example, a variable can contain an integer value at the beginning of the program, a value that is subsequently changed to a real number. In other programming languages, such as Java, the type must be explicitly indicated at the time of declaration and cannot change.

4. A memory address, which is the memory address, in the RAM of the computer, where the value is stored. We won’t work directly with memory addresses in this course, but we may see them when using a visualizer or debugger to execute our programs.

Other Features

Depending on the programming language, we could also specify for a variable:

1. Visibility. An area of visibility or purpose, which is where inside the program the variable is visible. In Python and Java, visibility can be specified at the global level, i.e. visible in all the program, or local, i.e. visible at the individual procedure level.
2. A lifetime. The lifetime of a variable is closely related to its visibility: when the program performs an instruction outside the purpose of the variable, i.e. outside the scope of a variable, the variable itself ends its life.

Variable Operations

A programming language allows to perform two basic operations with a variable:

1. Reading the value of a variable. This value can be used in expression allowing to relate variables by means of operators. The basic operators are:
   1. Arithmetic operators: such as addition +, and subtraction -. They allow performing basic arithmetic operations with numbers.
   2. Comparison operators: such as less than <, and greater than >. Usually, they allow to comparing two operands, each of which could be a variable. The result of the comparison is either the Boolean value true or the Boolean value false.
   3. Logic operators: such as and , or, and not. This operator allows us to relate logical conditions together to create more complex statements.
   4. String operators: such union or concatenation of strings of characters. For example, we can use the plus symbol + to concatenate the strings “Hello” and the string “world” to produce the string “Hello world”. These operators allow us to manipulate strings.
2. Writing or storing a value inside a variable. This can be performed by an assignment operation such as a = b.

Variables in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent variables, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
Declare		X = 0
Assign		X = 5
Declare & Assign		X = 5

Notice that variables must be assigned a value when declared in pseudocode. By default, most programming languages automatically assign the value $0$ to a new integer variable, so we’ll use that value in our pseudocode as well.

Likewise, variables in a flowchart are given a type, whereas variables in pseudocode are not. Instead, the data type of those variables can be inferred by the values stored in them.

Variables in Python

Variables in Python are simply defined by giving them a value. The type of the variable in inferred from the data stored in it at any given time, and a variable’s type may change throughout the program as different values are assigned to it.

To define a variable, we can simply use an assignment statement to give it a value:

x = 5
y = 3.5

Casting

We can also convert, or cast, data between different types. When we do this, the results may vary a bit due to how computers store and calculate numbers. So, it is always best to fully test any code that casts data between data types to make sure it works as expected.

To cast, we can simply use the new type as a function and place the value to be converted in parentheses:

x = 1.5
y = int(x)

This will convert the floating point value stored in x to an integer value stored in y.

Conditionals

The conditional statement, also known as the If-Then statement, is used to control the program’s flow by checking the value of a Boolean statement and determining if a block of code should be executed based on that value. This is the simplest conditional instruction. If the condition is true, the block enclosed within the statement is executed. If it is false, then the code in the block is skipped.

A more advanced conditional statement, the If-Then-Else or If-Else statement, includes two blocks. The first block will be executed if the Boolean statement is true. If the Boolean statement is false, then the second block of code will be executed instead.

Simple conditions are obtained by means of the relational operators, such as <, >, and ==, which allow you to compare two elements, such as two numbers, or a variable and a number, or two variables. Compound conditions are obtained by composing two or more simple conditions through the logical operators and, or, and not.

Boolean Logic Review

Recall that the Boolean logic operators and, or, and not can be used to construct more complex Boolean logic statements.

Or

For example, consider the statement x <= 5. This could be broken down into two statements, combined by the or operation: x < 5 or x == 5. The table below, called a truth table, gives the result of the or operation based on the values of the two operands:

As shown above, the result of the or operation is True if at least one of the operands is True.

And

Likewise, to express the mathematical condition 3 < a < 5 we can use the logical operator and by dividing the mathematical condition into two logical conditions: a > 3 and a < 5. The table below gives the result of the and operation based on the values of the two operands:

As shown above, the result of the and operation is True if both of the operands are True.

Not

Finally, the not logical operator is used to reverse, or invert, the value of a Boolean statement. For example, we can express the logical statement x < 3 as not (x >= 3), using the not operator to invert the value of the statement. The table below gives the result of the not operation based on the value of its operand:

In propositional logic, the completeness theorem shows that all other logical operators can be obtained by appropriately combining the and, or and not operators. So, by just understanding these three operators, we can construct any other Boolean logic statement.

Conditionals in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent conditional statements, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
If-Then		if A < 5 then A = 5 end if
If-Then-Else		if A < 5 then A = 5 else A = 10 end if

Conditionals in Practice

The mechanism for determining which block an If-Then-Else statement executes is the following:

1. If the initial condition is true, execute the instructions enclosed between if and else
2. If the initial condition is false, execute the instructions between the else and the end of the block

To understand how a conditional statement works, let’s look at this example of a simple If-Then-Else statement. Consider the following flowchart:

In this case, if a is less than zero, the output message will be “The value of a is less than zero”. Otherwise, if a is not less than zero (that is, if a is greater than or equal to zero), the output message will be “The value of a is greater than or equal to zero”.

Nesting

We can also nest conditional statements together, making more complex programs.

Consider the following flowchart:

In this case, if a is less than zero the output message will be “The value of a is less than zero”. Otherwise (that is, if a is not less than zero so if a is greater than or equal to zero) the block checks whether a is equal to zero; if so, the output message will be “The value of a is equal to zero”. Otherwise (that is, if the first condition is false, i.e. a >= 0 and the second condition is false, i.e. is nonzero; the two conditions must be both true as if they were bound by a logical and, and they are the same as the condition a > 0) the output message will be “The value of a is greater than zero”.

Conditionals in Python

To see how conditional statements look in Python, let’s recreate them from the flowcharts shown above.

if a < 5:
    a = 5

if a < 5:
    a = 5
else:
    a = 10

if a < 0:
    print("The value of a is less than zero")
elif a == 0:
    print("The value of a is equal to zero")
else:
    print("The value of a is greater than zero")

As we can see in the examples above, we must carefully indent each block of code to help set it apart from the other parts of the program. In addition, each line containing if, elif and else must end in a colon :.

Loops

Loops are another way we can control the flow of our program, this time by repeating steps based on a given criteria. A computer is able to repeat the same instructions many times. There are several ways to tell a computer to repeat a sequence of instructions:

• Repeat an infinite number of times, e.g. while true. This construct is useful in software applications such as servers that will offer a service. The service is supposed to be available forever.
• Repeat a specific number of times, e.g. Repeat 10 times or for i = 1 to 10. This loop can be used when you know the number of repetitions. There are also loops that allow you to repeat as many times as there are elements of a collection, such as for each item in list
• Repeat according to a condition. The number of repetitions depends on the condition. Most programming languages support the while loop, which repeats while the condition is true.

In repeat while loops, the number of repetitions depends on the occurrence of a condition: the cycle repeats if the condition is true. Loops can also be nested, just like conditional statements.

Loops in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent loop statements, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
While Loop		loop while A < 5 A = A + 1 end loop
For Loop		loop I from 1 to 10 A = A + I end loop
For Loop with Step		loop I from 1 to 10 step by 2 A = A + I end loop
For Each Loop		loop each I in LIST A = A + I end loop

Loops in Python

To see how loops look in Python, let’s recreate them from the flowcharts shown above.

while a < 5:
    a = a + 1

for i in range(1, 11):
    a = a + i

for i in range(1, 11, 2):
    a = a + i

for i in list:
    a = a + i

As we can see in the examples above, we must carefully indent each block of code to help set it apart from the other parts of the program. In addition, each line containing for and while must end in a colon :. Finally, notice that the range() function in Python does not include the second parameter in the output. So, to get the numbers $1$ through $10$, inclusive, we must use range(1, 11) in our code.

Lists

^[File:USPS Post office boxes 1.jpg. (2017, May 17). Wikimedia Commons, the free media repository. Retrieved 18:17, November 5, 2018 from https://commons.wikimedia.org/w/index.php?title=File:USPS_Post_office_boxes_1.jpg&oldid=244476438.]

Arrays allow us to store multiple values in the same variable, using an index to determine which value we wish to store or retrieve from the array. We can think of arrays like a set of post office boxes. Each one has the same physical address, the post office, but within the post office we can find an individual box based on its own box number.

Some programming languages, such as Java, use arrays that are statically sized when they are first created, and those arrays cannot be resized later. In addition, many languages that require variables to be declared with a type only allow a single variable type to be stored in an array.

Other languages, such as Python, use lists in place of arrays. List can be resized, and in untyped languages such as Python they can store different data types within the same list.

Arrays in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent arrays, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
Declare Array		ARR = new array[5]
Store Item		ARR[0] = 5
Retrieve Item		X = ARR[0]

Lists in Python

Let’s review the syntax for working with lists in Python.

List Creation

To define a list in Python, we can simply place values inside of a set of square brackets [], separated by commas ,:

arr = [1, 2]
arr2 = [1.2, 3.4]

We can also create an empty list by simply omitting any items inside the square brackets

arr3 = []

Adding Items

Once we’ve created a list in Python, we can add items to the end of the list using the append() method:

arr4 = []
arr4.append(1)
arr4.append(2)
arr4.append(3)

Accessing List Elements

Once the list is created, we can access individual items in the list by placing the index in square brackets [] after the list’s variable name:

x = arr[2]
arr[1] = 5

Multidimensional List

Python lists can also be created with multiple dimensions, simply by appending lists as elements in a base list.

two_dim_arr = []
two_dim_arr.append([1, 2, 3])
two_dim_arr.append([4, 5, 6])

They can also be created through the use of lists as individual elements in a list when it is defined:

another_arr = [[1, 2, 3], [4, 5, 6]]

To access elements in a multidimensional list, simply include additional sets of square brackets containing an index [] for each dimenison:

another_arr = [[1, 2, 3], [4, 5, 6]]
x = another_arr[1, 2]
another_arr[0, 1] = 5

List Operations

There are several operations that can be performed on lists in Python as well:

arr = [1, 2, 3, 4, 5]

# list length
length = len(arr)

# concatenation
arr2 = [6, 7]
arr3 = arr + arr2  # [1, 2, 3, 4, 5, 6, 7]

# slicing
b = arr[2:4]   # [3, 4]

List Loops

Finally, we can use a special form of loop, called a For Each loop, to iterate through items in a list in Python:

arr = [1, 2, 3, 4 5]

for i in arr:
    print(i)

Once important thing to note is that lists accessed within a For Each loop are read only. So, we cannot change the values stored in the list using this loop, but we can access them. If we want to change them, we should use a standard For loop to iterate through the indices of the list:

arr = [1, 2, 3, 4, 5]

for i in range(0, len(arr)):
    arr[i] = arr[i] + 5

References

• An Informal Introduction to Python: Lists
• Data Structures: More on Lists

Variable Roles

Variables in our programs can be used in a variety of different roles. The simplest role for any variable is to store a value that does not change throughout the entire program. Most variables, however, fit into one of several roles throughout the program.

To help us understand these roles, let’s review them in detail here. As we move forward in this course, we’ll see many different data structures that use variables in these ways, so it helps to know each of them early on!

Container

OPERAND = 1

In this role, the variable is used to hold a value. This value can be changed during the program execution. In the example:

1. a variable named operand of type Integer is declared
2. the value 1 is assigned to the variable

Counter

loop COUNTER from 1 to 10
    print COUNTER
end loop

In this role, variables are used to hold a sequence of values known beforehand. In the example, the variable counter holds values from 1 to 10 and these values are conveyed to the user.

Accumulator

SUM = 0
loop COUNTER from 1 to 10
    SUM = SUM + COUNTER
end loop
print SUM

In this role, the variable is used to hold a value that aggregates, summarizes, and synthesize multiple values by means of an operation such as sum, product, mean, geometric mean, or median. In the example, we calculate the sum of the first ten numbers in the accumulator variable sum.

Recent Value

ANSWER = 0
print "Input a number"
input ANSWER
print "You input " + ANSWER

In this role, the variable answer contains the last value encountered so far in a data series, such as the last value that the program receives from the user.

Extreme Value

COUNTER = 0
SCORES = new array[10]
input SCORES
MAX = SCORES[0]
loop COUNTER from 0 to (size of SCORES) - 1
    if SCORES[COUNTER] > MAX
        MAX = SCORES[COUNTER]
    end if
end loop
print "Max value: " + MAX

In this role, the variable contains the value that is most appropriate for the purpose of the program, e.g. the minimum or the maximum. The instruction scores[counter] > max checks if the list item under observation is greater than the maximum. If the condition is true the value of the maximum variable is changed.

Follower

COUNTER = 0
SCORES = new array[10]
input SCORES
MAX = SCORES[0]
SECOND = MAX
loop COUNTER from 0 to (size of SCORES) - 1
    if SCORES[COUNTER] > MAX
        SECOND = MAX
        MAX = SCORES[COUNTER]
    else if SCORES[COUNTER] > SECOND
        SECOND = SCORES[COUNTER]
    end if
end loop
print "Max value: " + MAX + " Second max: " + SECOND

A variable, such as second, to which you assign the value of another variable that will be changed immediately after. In the example, the second variable contains the second largest value in a list.

Flag

MISTAKE = false
COUNTER = 0
input COUNTER
if COUNTER < 0
    MISTAKE = true
else
    MISTAKE = false
end if

A flag variable is used to report the occurrence or not of a particular condition, e.g. the occurrence of an error, the first execution, etc..

Temporary

TEMP = FIRST
FIRST = SECOND
SECOND = TEMP

A variable used to hold a temporary value. For example, to exchange two variables, you must have a temporary variable temp to store a value before it is replaced.

Index

SCORES = new array[10]
input SCORES
loop INDEX from 0 to 9
    print SCORES[INDEX]
end loop

A variable used to indicate the position of the current item in a set of elements, such as the current item in an array of elements. The index variable here is a great example.

References

• Sajaniemi, J. (2005, October). Roles of variables and learning to program. In Proc. 3rd Panhellenic Conf. Didactics of Informatics, Jimoyiannis A (ed) University of Peloponnese, Korinthos, Greece.
• Hosanee, M., & Rana, M. E. (2018). A Refined Approach for Understanding Role of Variables in Elementary Programming. Jour of Adv Research in Dynamical & Control Systems, 10(11).

Strings

Strings are another very important data type in programming. A string is simply a set of characters that represent text in our programs. We can then write programs that use and manipulate strings in a variety of ways, allowing us to easily work with textual data.

Strings in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent strings, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
Create String		STR = “abc”
Access Character		C = STR[0]
String Length		X = size of STR

Strings in Python

Let’s review the syntax for working with strings in Python.

String Creation

Strings in Python are declared just like any other variable:

s = "abc123"

Notice that strings are enclosed in double quotations marks ". Since Python does not have a data type for a single character, we can do the same for single character strings as well:

c = "a"

There are several special characters we can include in our strings. Here are a few of the more common ones:

• \' - Single Quotation Mark (usually not required)
• \" - Double Quotation Mark
• \n - New Line
• \t - Tab

String Parsing

Most of the time, we will need to be able to parse strings in order to read input from the user. This is easily done using Python. Let’s refer to the skeleton code given in an exercise:

# Load required modules
import sys


def main(argv):

    # create a file reader for terminal input
    reader = sys.stdin

    # read a single integer from the terminal
    x = int(reader.readline())

    # -=-=-=-=- MORE CODE GOES HERE -=-=-=-=- 


# main guard
if __name__ == "__main__":
    main(sys.argv)

This code will initialize a variable called reader to read input from the terminal, or sys.stdin in Python.

Once we have a reader initialized, we can read a line of data from the input as follows:

line = reader.readline()

If we know that line will contain a single item of a different data type, such as an integer, we can also convert that input using the appropriate method:

x = int(reader.readline())

Finally, if we have read an entire string of input consisting of multiple parts, we can use the split method to split the string in to tokens that are separated by a special delimiter. When we do this, we’ll have to use special methods to convert the strings to other primitive data types. Here’s an example:

line = "This 1 is 2.0 true"
parts = line.split(" ")
first = parts[0]
second = int(parts[1])
third = parts[2]
fourth = float(parts[3])
fifth = bool(parts[4])

In this example, we are able to split the first string variable into $5$ parts, each one separated by a space in the original string. Then, we can use methods such as int() to convert each individual string token into the desired data type.

Reading Input in a Loop

When reading an unknown number of lines of input, we can use a loop in Python such as the following example:

for line in reader:
    line = line.strip()
    if not line or len(line) == 0:
        break
    
    # parse the input

This will read input until either a blank line is received (usually via the terminal), or there is no more input available to read (from a file).

String Operations

There are also several operations we can perform on strings in Python:

s1 = "This"
s2 = "That"

# string length
x = len(s1)

# string comparison
# can use standard comparison operators
b1 = s1 == s2
b2 = s1 < s2 

# concatenation
s3 = s1 + " " + s2

Additional methods can be found on the Python Built-In Types: str and Python Common String Operations pages

String Formatting

Strings can also be used to create formatted output in Python through the use of f-strings. Here’s a short example:

sum = 123
avg = 1.23
name = "Student"

print(f"{name}: Your score is {sum} with an average of {avg}.")

When we run this program, the output will be:

Student: Your score is 123 with an average of 1.23.

Each item in the formatted output can also be given additional attributes such as width and precision. More details can be found on the Python Format String Syntax page.

References

• Python Built-In Types: str
• Python Common String Operations
• Python Format String Syntax

Exceptions

An exception is an error that a program encounters when it is running. While some errors cannot be dealt with directly by the program, many of these exceptions can be caught and handled directly in our programs.

Exceptions in Flowcharts & Pseudocode

There isn’t really a standard way to display exceptions in flowcharts and pseudocode, but we can easily create a system that works well for our needs. Below are the flowchart blocks and pseudocode examples we’ll use in this course to represent exceptions and exception handling:

Operation	Flowchart	Pseudocode
Throw Exception		throw INPUT EXCEPTION
Catch Exception		catch INPUT EXCEPTION
Try-Catch Example		X = 0 try input X if X < 0 throw INPUT EXCEPTION end if print X catch INPUT EXCEPTION print “Error” end try

Exceptions in Python

Let’s review the syntax for working with exceptions in Python.

Try-Catch

In Python, we can use a Try-Except statement to detect and handle exceptions in our code:

# Load required modules
import sys

try:
    reader = open(sys.argv[1])
    x = int(reader.readline())
    print(x)

except Exception as e:
    print("Error!")

In this example, the program will try to open a file using the first command-line argument as a file name. There are several exceptions that could occur in this code, such as a ValueError, a IndexError, a FileNotFoundError, and more. They can also be handled individually:

# Load required modules
import sys

try:
    reader = open(sys.argv[1])
    x = int(reader.readline())
    print(x)

except IndexError as e:
    print("Error: Invalid Array Index!")
except FileNotFoundError as e:
    print("Error: File Not Found!")
except ValueError as e:
    print("Error: Input Does Not Match Expected Format!")
except OSError as e:
    print("Error: OS Exception!")

Throw

If desired, we can also raise our own exceptions in Python:

if y == 0:
    raise ValueError("Cannot divide by zero")
else:
    z = x / y
    print(z)

This will cause an exception to be thrown if the value of y is equal to $0.0$.

Finally

We can also add Else and Finally blocks at the end of each Try-Except block. A Finally block will be executed whenever the control exits the Try-Except block, even through the use of a return statement to return from a method. The Else block will be executed if the entire Try-Except block completes without any exceptions being raised:

# Load required modules
import sys

try:
    reader = open(sys.argv[1])
    x = int(reader.readline())
    print(x)

except Exception as e:
    print("Error!")
else:
    print("No Errors!")
finally:
    print("Finally Block")

With Statement

When working with resources such as files in Python, we can also use a With block to ensure that those resources are properly closed when we are done with them. In addition, a With block will automatically catch and suppress any exceptions that result from trying to close the resource after an exception has occurred, preventing us from being bombarded by unavoidable exceptions. Here’s an example:

import sys

try:    
    with open(sys.argv[1]) as reader:
        x = int(reader.readline())
        print(x)

except IndexError as e:
    print("Error: Invalid Array Index!")
except ValueError as e:
    print("ValueError: {}".format(e))
except FileNotFoundError as e:
    print("FileNotFoundError: {}".format(e))

In this example, we are opening a file using the open() method inside of the With statement. That file will automatically be closed once the program leaves the With statement.

References

• Built-in Exceptions
• Tutorial: Errors and Exceptions
• Python Exception Hierarchy

I/O

One of the major features of a modern computer is the ability to store and retrieve data from the computer’s file system. So, we need to be able to access the file system in our code in order to build useful programs. Thankfully, most modern programming languages include a way to do this.

I/O in Flowcharts & Pseudocode

Most operations working with files in code take the form of method calls. So, we will primarily use the call block to represent operations on files:

Operation	Flowchart	Pseudocode
Open File		S = “file.txt” FILE = open(S)
Read from File		S = FILE.read()
Write to File		FILE.write(X)

I/O in Python

Let’s review the syntax for working with files in Python.

Reading Files

To open a file in Python, we can simply use the open() method. Here is an example:

import sys

try:
    reader = open(sys.argv[1])
except FileNotFoundError as e:
    print("FileNotFoundError: {}".format(e))
    sys.exit()
except IndexError as e:
    print("IndexError: {}".format(e))
    reader = sys.stdin
  
with reader:
    # -=-=-=-=- MORE CODE GOES HERE -=-=-=-=-

In this example, the program will try to open a file provided as the first command-line argument. If no argument is provided, it will automatically read from standard input instead. However, if an argument is provided, it will try to open it as a file. In addition, we can use a With statement to make sure the file is properly closed once it is open.

Once we have opened the file, we can read the file just like we would any other input:

for line in reader:
    line = line.strip()
    if not line or len(line) == 0:
        break
    # use line variable

Writing Files

To write to a file, we must open it a different way. In Python, we must provide an optional "w" argument to the open() method call to make the file writable:

import sys

try:
    with open(sys.argv[1], "w") as writer:
        writer.write("Hello World")
        writer.write("\n")

except IndexError as e:
    # no arguments provided
    print("IndexError: {}".format(e))
    sys.exit()
except IOError as e:
    # unable to write to the file
    print("IOError: {}".format(e))
    sys.exit()
except Exception as e:
    # unknown exception
    print("Exception: {}".format(e))
    sys.exit()

This example shows to how to open a file for writing using the open() method inside of a With statement. It also lists several of the common exceptions and their cause.

Resources

• Open Method Options in the Python Documentation
• pathlib on the Python Documentation
• shutil on the Python Documentation

Documentation

It is important both to easily grasp the design choice and the code structure of a project even long after it has been completed. The documentation process starts by commenting the code. Code comments are usually intended for software developers and aim at clarifying the code by giving details of how it works. They are usually performed using inline or multiple lines comments using the language syntax.

Single Line Comments

As we’ve seen before, we can add single-line comments to our Python programs using a hash symbol # before a line in our source file:

# this is a comment
x = 5

# this is also a comment
b = True

Docstrings

Finally, Python also includes a secondary type of comment that spans multiple lines, specifically for creating documentation. A docstring is usually the first line of text inside of a class or method definition, and is surrounded by three double quotes """ with one set of three on each end.

These comments are specifically designed to provide information about classes and methods in our code. Here’s a quick example using a simple class:

class IntTuple:
  """ Represents a tuple containing two integer values
  
  This class is an adaptation of a class developed for Java
  that mimics the built-in tuples in Python
  
  Attributes
  ----------
  first : int
      the first element in the tuple
  second : int
      the second element in the tuple
  """
  
  def __init__(self, one, two):
    """ Initializes a new IntTuple object
    
    Parameters
    ----------
    one : int
        the first element in the new tuple
    two : int
        the second element in the new tuple
    """
    self.first = one
    self.second = two

Unfortunately, Python does not enforce a particular style for these docstrings, so there are many different formats used in practice. To learn more, we can consult the following references.

References

• Documenting Python Code from Real Python
• Google Docstring Style Guide
• reStructured Text - The format used in official Python libraries

Style

To make your code easier to read, many textbooks and companies use a style guide that defines some of the formating rules that you should follow in your source code. In Python, these rules are very important, as the structure of your code is defined by the layout. We’ll learn more about that in a later module.

For this book, most of the examples will be presented using the guidelines in the Style Guide for Python. However, by default Codio used to use 2 spaces for an indentation level instead of 4, so that is the format that will be used in some examples in this book.

Google also provides a comprehensive style guide that is recommended reading if you’d like to learn more about how to format your source code.

Review Summary

That’s a quick overview of the basics we’ll need to know before starting the new content in this course. The next module will provide a quick review of object-oriented programming concepts as well as the model-view-controller or MVC architecture, both of which will be used heavily in this course.

Object-Oriented Programming

¹

Object-oriented programming uses the idea of objects and classes to provide many improvements over other programming paradigms. The key concept of object-oriented programming - encapsulation - allows our data and the operations that manipulate that data to be bundled together within a single object.

Functions

Functions are small pieces of reusable code that allow you to divide complex programs into smaller subprograms. Ideally, functions perform a single task and return a single value. (It should be noted that some programming languages allow for procedures, which are similar to functions but return no values. Except for the return value, it is safe to group them with functions in our discussion below.)

Functions can be thought of as black boxes. When we talk about black boxes we mean that users cannot look inside the box to see how it actually works. A good example of a black box is a soda machine. We all use them and know how to operate them, but very few of actually know how they work inside. Nor do we really want to know. We are happy to simply use them machine and have it give a nice cold soda when we are thirst!

Calling Functions

To be able to reuse functions easily, it is important to define what a function does and how it should be called.

Before we can call a function, we must know the function’s signature. A function’s signature includes the following.

1. The name of the function.
2. The parameters (data) that must be provided for the function to perform its task.
3. The type of result the function returns.

While a signature will allow us to actually call the function in code. Of course to use functions effectively, we must also know exactly what the function is supposed to do. We will talk more about how we do this in the next module on programming by contract. For now we can assume that we just have a good description of what the function does.

While we do not need to know exactly how a function actually performs its task, the algorithm used to implement the function is vitally important as well. We will spend a significant amount of time in this course designing such algorithms.

Executing Functions

The lifecycle of a function is as follows.

1. A program (or another function) calls the function.
2. The function executes until it is complete.
3. The function returns to the calling program.

When the function is called, the arguments, or actual parameters, are copied to the function’s formal parameters and program execution jumps from the “call” statement to the function. When the function finishes execution, execution resumes at the statement following the “call” statement.

In general, parameters are passed to functions by value, which means that the value of the calling program’s actual parameter is copied into the function’s formal parameter. This allows the function to modify the value of the formal parameter without affecting the actual parameter in the calling program.

However, when passing complex data structures such as objects, the parameters are passed by reference instead of by value. In this case, a pointer to the parameter is passed instead of a copy of the parameter value. By passing a pointer to the parameter, this allows the function to actually make changes to the calling program’s actual parameter.

Classes & Objects

As you might guess from its name, object-oriented programming languages are made to create and manipulate entities called objects. But what exactly are these objects? Objects were created to help decompose large complex programs with a lot of complex data into manageable parts.

A good example of an object is dog. But not just any dog, or all dogs, but a specific dog. Each dog has specific characteristics that are captured as data such as their name, their height, their weight, their breed, their age, etc. We call these characteristics attributes and all dogs have the same type of attributes, although the values of those attributes may be unique. And generally, all dogs exhibit the same behaviors, or methods. Almost all dogs can walk, run, bark, eat, etc.

So, how do we define the basic attributes and behaviors of a dog? We probably start with some kind of idea of what a dog is. How do we describe dogs in general. In object orientation we do that through classes.

What do we use blueprints for? Well, when we are building a physical structure such as a home or office building, an architect first creates a blueprint that tells the builder what to build and how everything should fit together. That is essentially what a class does. A class describes the types of attributes and methods that an object of that class will have.

Then to create objects, we say we create an instance of a class by calling the class’s constructor method, which creates an object instance in memory and makes sure it’s attributes are properly created. Once the object has been created, the methods defined by the class can be used to manipulate the attributes and internal data of the object.

Information Hiding

Two of the most powerful concepts in object orientation are encapsulation and information hiding.

• Encapsulation is capturing both data and behavior into a single object.
• Information hiding is restricting access to some of the data and behavior of an object.

Encapsulation enables information hiding, and information hiding allows us to simplify the interface used to interact with an object. Instead of needing to know everything about a particular class of objects in order to use or interact with those objects. This will make our programs less complex and easier to implement and test. It also makes it easier for you to change the internal implementations of methods without affecting the rest of your program. As long as the method behaves in the same way (i.e., produces the same outputs given a given set of inputs), the rest of your program will not be affected. Thus, we see two key parts of any class:

• The interface to the class. Those methods and attributes that can be seen and called by an external object.
• The implementation of the class. The internal representation of the attributes and implementation of methods to achieve the desired behavior.

Real World Example

Encapsulation and information hiding are actually all around us. Take for example, a soda vending machine. There are many internal parts to the machine. However, as a user, we care little about how the machine works or what it does inside. We need to simply know how to insert money or swipe our card and press a couple of buttons to get the soda we desire. If a repair is needed and an internal motor is replaced, we don’t care whether they replaced the motor with the exact same type of motor or the new model. As long as we can still get our soda by manipulating the same payment mechanisms and buttons, we are happy. You and I care only about the interface to the machine, not the implementation hiding inside.

Private and Public

To implement information hiding in our classes, we use visibility. In general, attributes and methods can either be public or private. If we want and attribute or method to be part of the class interface, we define them as public. If we want to hide a attribute or method from external objects, we defined them as private. An external object may access public attributes and call public methods, which is similar to using the payment mechanism or the buttons on a soda machine. However, the internals of how the object works is hidden by private attributes and methods, which are equivalent to the internal workings of the soda machine.

Best Practices

To implement information hiding, we recommend that you declare all attributes of a class as private. Any attribute whose value should be able to be read or changed by an external object should create special “getter” and “setter” methods that access those private variables. This way, you can make changes to the implementation of the attributes without changing how it is accessed in the external object.

Inheritance

Polymorphism

Polymorphsim is a concept that describes the fact that similar objects tend to behave in similar ways, even if they are not exactly alike. For example, if we might have a set of shapes such as a square, a circle, and a rhombus. While each shape shares certain attributes like having an area and a perimeter. However, each shape is also unique and may have differing number of sides and angles between those sides, or in the case of a circle, a diameter. We describe this relationship by saying a circle (or rectangle, or rhombus) “is a” shape as shown in the figure below.

Inheritance

Inheritance is a mechanism that captures polymorphism by allowing classes to inherit the methods and attributes from another class. The basic purpose of inheritance to to reuse code in a principled and organized manner. We generally call the inheriting class the subclass or child class, while the class it inherits from is called the superclass or parent class.

Basically, when class ‘A’ inherits from class ‘B’, all the methods and attributes of class ‘A’ are automatically copied to class ‘B’. Class ‘B’ can then add additional methods or attributes to extend class ‘A’, or overwrite the implementations of methods in class ‘A’ to specialize it.

When programming, we use inheritance to implement polymorphism. In our shape example, we would have a generic (or abstract) Shape class, which is inherited by a set of more specific shape classes (or specializations) as shown below.

In this example, the Shape class defines the ‘color’ attribute and the ‘getArea’ and ‘getCircumference’ methods, which are inherited by the Rectangle, Circle, and Rhombus classes. Each of the subclasses define additional attributes that are unique to the definition of each shape type.

Notice that although the Shape class defines the signatures for the ‘getArea’ and ‘getCircumference’ methods, it cannot define the implementation of the methods, since this is unique to each subclass shape. Thus, each subclass shape will specialize the Shape class by implementing their own ‘getArea’ and ‘getCircumference’ methods.

Multiple Inheritance

So far, we have discussed Single inheritance, which occurs when a class has only one superclass. However, theoretically, a class may inherit from more than one superclass, which is termed multiple inheritance. While a powerful mechanism, multiple inheritance also introduces complexity into understanding and implementing programs. And, there is always the possibility that attributes and methods from the various superclasses contradict each other in the subclass.

Associations

For object a to be able to call a method in object b, object a must have a reference (a pointer, or the address of) object b. In many cases, objects a and b will be in a long-term relationship so that one or both objects will need to store the reference to the other in an attribute. When an object holds a reference to another object in an attribute, we call this a link. Examples of such relationships include a driver owning a car, a person living at an address, or a worker being employed by a company.

As we discussed earlier, objects are instances of classes. To represent this in a UML class diagram, we use the notion of an association, which is shown as a line connecting to two classes. More precisely, a link is an instance of an association. The figure belows shows three examples of an association between class A and class B.

The top example shows the basic layout of an association in UML. The line between the two classes denotes the association itself. The diagram specifies that ClassA is associated with ClassB and vice versa. We can name the association as well as place multiplicities on the relationships. The multiplicities show exactly how many links an object of one class must have to objects of the associated class. The general form a multiplicity is n .. m, which means that an object must store at least n, but no more than m references to other objects of the associated class; if only one number is given such as n, then the object must store exactly n references to objects in the associated class.

There are two basic types of associations.

• Two-way - both classes store references to the other class.
• One-way - only one class stores a reference to its associated class.

The middle example shows a two-way association between ClassA and ClassB. Furthermore, each object of ClassA must have a link to exactly three objects of ClassB, while each ClassB object must have a link with exactly one ClassA object. (Note that the multiplicity that constrains ClassA is located next to ClassB, while the multiplicity that constrains ClassB is located next to ClassA.)

The bottom example shows a one-way association between ClassA and ClassB. In this case, ClassA must have links to either zero or one objects of ClassB. Since it is a one-way association, ClassB will have no links to objects of ClassA.

Functions

In Python, we can break our programs up into individual functions, which are individual routines that we can call in our code. Let’s review how to create functions in Python.

Functions in Flowcharts & Pseudocode

The table below lists the flowchart blocks used to represent functions, as well as the corresponding pseudocode:

Operation	Flowchart	Pseudocode
Declare Function		function FOO(X) X = X + 5 return X end function
Call Function		X = FOO(5)

Functions in Python

Declaring Functions

In general, a function definition in Python needs a few elements. Let’s start at the simplest case:

def foo():
  print("Foo")
  return

Let’s break this example function definition down to see how it works:

1. First, we use the keyword def at the beginning of this function definition. That keyword tells Python that we’d like to define a new function. We’ll need to include it at the beginning of each function definition.
2. Next, we have the name of the function, foo. We can name a function using any valid identifier in Python. In general, function names in Python always start with a lowercase letter, and use underscores between the words in the function name if it contains multiple words.
3. Following the function name, we see a set of parentheses () that list the parameters for this function. Since there is nothing included in this example, the function foo does not require any parameters.
4. Finally, we see a colon : indicating that the indented block of code below this definition is contained within the function. In this case, the function will simply print Foo to the terminal.
5. The function ends with the return keyword. Since we aren’t returning a value, we aren’t required to include a return keyword in the function. However, it is helpful to know that we may use that keyword to exit the function at any time.

Once that function is created, we can call it using the following code:

foo()

Parameters and Return

In a more complex case, we can declare a function that accepts parameters and returns a value, as in this example:

def count_letters(input, letter):
  output = 0
  for i in range(0, len(input)):
    if input[i] == letter:
      output += 1
  return output

In this example, the function accepts two parameters: input, which could be a string, and letter, which could be a single character. However, since Python does not enforce a type on these parameters, they could actually be any value. We could add additional code to this function that checks the type of each parameter and raises a TypeError if they are not the expected type.

We can use the parameters just like any other variable in our code. To return a value, we use the return keyword, followed by the value or variable containing the value we’d like to return.

To call a function that requires parameters, we can include values as arguments in the parentheses of the function call:

sum += count_letters("The quick brown fox jumped over the lazy dog", "e")

Overloading

Python allows us to specify default values for parameters in a function definition. In that way, if those parameters are not provided, the default value will be used instead. So, it may appear that there are multiple functions with the same name that accept a different number of parameters. This is called function overloading.

Function Overloading using Default Values

For example, we could create a function named max() that could take either two or three parameters:

def main():
  max(2, 3)
  max(3, 4, 5)
  
def max(x, y, z=None):
  if z is not None:
    if x >= y:
      if x >= z:
        print(x)
      else:
        print(z)
    else:
      if y >= z:
        print(y)
      else:
        print(z)  
  else:
    if x >= y:
      print(x)
    else:
      print(y)
      
# main guard
if __name__ == "__main__":
  main()

In this example, we are calling max() with both 2 and 3 arguments from main(). When we only provide 2 arguments, the third parameter will be given the default value None, which is a special value in Python showing that the variable is empty. Then, we can use if z is not None as part of an If-Then statement to see if we need to take that variable into account in our code.

This example also introduces a new keyword, is. The is keyword in Python is used to determine if two variables are exactly the same object, not just the same value. In this case, we want to check that z is exactly the same object as None, not just that it has the same value. In Python, it is common to use the is keyword when checking to see if an optional parameter is given the value None. We’ll see this keyword again in a later chapter as we start dealing with objects.

Keyword Arguments

Python also allows us to specify function arguments using keywords that match the name of the parameter in the function. In that way, we can specify the arguments we need, and the function can use default values for any unspecified parameters. Here’s a quick example:

def main():
  args(1)             # 6
  args(1, 5)          # 9
  args(1, c=5)        # 8
  args(b=7, a=2)      # 12
  args(c=5, a=2, b=3) # 10
  
def args(a, b=2, c=3):
  print(str(a + b + c))
      
# main guard
if __name__ == "__main__":
  main()

In this example, the args() method has one required parameter, a. It can either be provided as the first argument, known as a positional argument, or as a keyword argument like a=2. The other parameters, b and c, can either be provided as positional arguments or keyword arguments, but they are not required since they have default values.

Also, we can see that when we use keyword arguments we do not have to provide the arguments in the order they are defined in the function’s definition. However, any arguments provided without keywords must be placed at the beginning of the function call, and will be matched positionally with the first parameters defined in the function.

Variable Length Parameters

Finally, Python allows us to define a single parameter that is a variable length parameter. In essence, it will allow us to accept anywhere from 0 to many arguments for that single parameter, which will then be stored in a list. Let’s look at an example:

def main():
  max(2, 3)
  max(3, 4, 5)
  max(5, 6, 7, 8)
  max(10, 11, 12, 13, 14, 15, 16)

def max(*values):
  if len(values) > 0:
    max = values[0]
    for value in values:
      if value > max:
        max = value
    print(max)

# main guard
if __name__ == "__main__":
  main()

Here, we have defined a function named max() that accepts a single variable length parameter. To show a parameter is variable length we use an asterisk * before variable name. We must respect two rules when creating a variable length parameter:

1. Each function may only have one variable length parameter
2. It must be defined after any positional parameters. Any parameters after the variable length parameter can only be assigned as keyword arguments

So, when we run this program, we see that we can call the max() function with any number of arguments, and it will be able to determine the maximum of those values. Inside of the function itself, values can be treated just like a list.

Classes

In programming, a class describes an individual entity or part of the program. In many cases, the class can be used to describe an actual thing, such as a person, a vehicle, or a game board, or a more abstract thing such as a set of rules for a game, or even an artificial intelligence engine for making business decisions.

In object-oriented programming, a class is the basic building block of a larger program. Typically each part of the program is contained within a class, representing either the main logic of the program or the individual entities or things that the program will use.

Representing Classes in UML

We can represent the contents of a class in a UML Class Diagram. Below is an example of a class called Person:

Throughout the next few pages, we will realize the design of this class in code.

Creating Classes in Python

To create a class in Python, we can simply use the class keyword at the beginning of our file:

class Person:
    pass

As we’ve already learned, each class declaration in Python includes these parts:

1. class - this keyword says that we are declaring a new class.
2. Person - this is an identifier that gives us the name of the class we are declaring.

Following the declaration, we see a colon : marking the start of a new block, inside of which will be all of the fields and methods stored in this class. We’ll need to indent all items inside of this class, just like we do with other blocks in Python.

In order for Python to allow this code to run, we cannot have an empty block inside of a class declaration. So, we can add the keyword pass to the block inside of the class so that it is not empty.

By convention, we would typically store this class in a file called Person.py.

Attributes

Of course, our classes are not very useful at this point because they don’t include any attributes or methods. Including attributes in a class is one of the simplest uses of classes, so let’s start there.

Adding Attributes

To add an attribute to a class, we can simply declare a variable inside of our class declaration:

class Person:
    last_name = "Person"
    first_name = "Test"
    age = 25

That’s really all there is to it! These are static attributes or class attributes that are shared among all instances of the class. On the next page, we’ll see how we can create instance attributes within the class’s constructor.

Finally, we can make these attributes private by adding two underscores to the variable’s name. We denote this on our UML diagram by placing a minus - before the attribute or method’s name. Otherwise, a + indicates that it should be public. In the diagram above, each attribute is private, so we’ll do that in our code:

class Person:
    __last_name = "Person"
    __first_name = "Test"
    __age = 25

Unfortunately, Python does have a way to get around these restrictions as well. Instead of referencing __last_name, we can instead reference _Person__last_name to find that value, as in this example:

ellie = Person("Jonson", "Ellie", 29)
ellie._Person__last_name = "Jameson"
print(ellie.last_name) # Jameson

Behind the scenes, Python adds an underscore _ followed by the name of the class to the beginning of any class attribute or method that is prefixed with two underscores __. So, knowing that, we can still access those attributes and methods if we want to. Thankfully, it’d be hard to do this accidentally, so it provides some small level of security for our data.

Methods

We can also add methods to our classes. These methods are used either to modify the attributes of the class or to perform actions based on the attributes stored in the class. Finally, we can even use those methods to perform actions on data provided as arguments. In essence, the sky is the limit with methods in classes, so we’ll be able to do just about anything we need to do in these methods. Let’s see how we can add methods to our classes.

Constructors

A constructor is a special method that is called whenever a new instance of a class is created. It is used to set the initial values of attributes in the class. We can even accept parameters as part of a constructor, and then use those parameters to populate attributes in the class.

Let’s go back to the Person class example we’ve been working on and add a simple constructor to that class:

class Person:
    __last_name = "Person"
    __first_name = "Test"
    __age = 25
    
    def __init__(self, last_name, first_name, age):
        self.__last_name = last_name
        self.__first_name = first_name
        self.__age = age

Since the constructor is an instance method, we need to add a parameter to the function at the very beginning of our list of parameters, typically named self. This parameter is automatically added by Python whenever we call an instance method, and it is a reference to the current instance on which the method is being called. We’ll learn more about this later.

Inside that constructor, notice that we use each parameter to set the corresponding attribute, using the self keyword once again to refer to the current object.

Also, since we are now defining the attributes as instance attributes in the constructor, we can remove them from the class definition itself:

class Person:
    
    def __init__(self, last_name, first_name, age):
        self.__last_name = last_name
        self.__first_name = first_name
        self.__age = age

class Test:
  age = 15
  
  def foo(self):
    age = 12
    print(age)      # 12
    print(self.age) # 15
    
  def bar(self):
    print(self.age) # 15
    print(age)      # NameError

Properties

In Python, we can use a special decorator @property to define special methods, called getters and setters, that can be used to access and update the value of private attributes.

Getter

In Python, a getter method is a method that can be used to access the value of a private attribute. To mark a getter method, we use the @property decorator, as in the following example:

class Person:
    
    def __init__(self, last_name, first_name, age):
        self.__last_name = last_name
        self.__first_name = first_name
        self.__age = age
        
    @property
    def last_name(self):
        return self.__last_name
    
    @property
    def first_name(self):
        return self.__first_name
        
    @property
    def age(self):
        return self.__age

Setter

Similarly, we can create another method that can be used to update the value of the age attribute:

class Person:
    
    def __init__(self, last_name, first_name, age):
        self.__last_name = last_name
        self.__first_name = first_name
        self.__age = age
        
    @property
    def last_name(self):
        return self.__last_name
    
    @property
    def first_name(self):
        return self.__first_name
        
    @property
    def age(self):
        return self.__age
    @age.setter
    def age(self, value):
        self.__age = value

However, this method is not required in the UML diagram, so we can omit it.

Adding Methods

To add a method to our class, we can simply add a function declaration inside of our class.

class Person:
    
    def __init__(self, last_name, first_name, age):
        self.__last_name = last_name
        self.__first_name = first_name
        self.__age = age
        
    @property
    def last_name(self):
        return self.__last_name
    
    @property
    def first_name(self):
        return self.__first_name
        
    @property
    def age(self):
        return self.__age
        
    def happy_birthday(self):
        self.__age = self.age + 1

Notice that once again we must remember to add the self parameter as the first parameter. This method will update the private age attribute by one year.

Instantiation

Now that we have fully constructed our class, we can use it elsewhere in our code through the process of instantiation. In Python, we can simply call the name of the class as a method to create a new instance, which calls the constructor, and then we can use dot-notation to access any attributes or methods inside of that object.

from Person import *

john = Person("Smith", "John", 25)
print(john.last_name)
john.happy_birthday()

Notice that we don’t have to provide a value for the self parameter when we use any methods. This parameter is added automatically by Python based on the value of the object we are calling the methods from.

Inheritance & Polymorphism

We can also build classes that inherit attributes and methods from another class. This allows us to build more complex structures in our code, better representing the relationships between real world objects.

Inheritance in UML

As we learned earlier in this chapter, we can represent an inheritance relationship with an open arrow in our UML diagrams, as shown below:

In this diagram, the Student class inherits from, or is a subclass of, the Person class.

Inheritance in Python

To show inheritance in Python, we place the parent class inside of parentheses directly after the name of the subclass when it is defined:

from Person import *

class Student(Person):
    pass

From there, we can quickly implement the code for each property and getter method in the new class:

from Person import *

class Student(Person):
    
    @property
    def student_id(self):
        return self.__student_id
    
    @property
    def grade_level(self):
        return self.__grade_level

Method Overriding

Since the subclass Student also includes a definition for the method happy_birthday(), we say that that method has been overridden in the subclass. We can do this by simply creating the new method in the Student class, making sure it accepts the same number of parameters as the original:

from Person import *

class Student(Person):
    
    @property
    def student_id(self):
        return self.__student_id
    
    @property
    def grade_level(self):
        return self.__grade_level
        
    def happy_birthday(self):
        super().happy_birthday()
        self.__grade_level += 1

Here, we are using the function super() to refer to our parent class. In that way, we can still call the happy_birthday() method as defined in Person, but extend it by adding our own code as well.

Inherited Constructors

In addition, we can use the super() method to call our parent class’s constructor.

from Person import *

class Student(Person):
    
    @property
    def student_id(self):
        return self.__student_id
    
    @property
    def grade_level(self):
        return self.__grade_level
        
    def __init__(self, last_name, first_name, age, student_id, grade_level):
        super().__init__(last_name, first_name, age)
        self.__student_id = student_id
        self.__grade_level = grade_level
        
    def happy_birthday(self):
        super().happy_birthday()
        self.__grade_level += 1

Security

In addition to private and public attributes and methods, UML also includes the concept of protected methods. This modifier is used to indicate that the attribute or method should not be accessed outside of the class, but will allow any subclasses to access them. Python does not enforce this restriction; it is simply convention. In a UML diagram, the protected keyword is denoted by a hash symbol # in front of the attribute or method. In Python, we then prefix those attributes or methods with a single underscore _.

Polymorphism

Inheritance allows us to make use of polymorphism in our code. Loosely polymorphism allows us to treat an instance of a class within the data type of any of its parent classes. By doing so, we can only access the methods and attributes defined by the data type, but any overriden methods will use the implementation from the child class.

Here’s a quick example:

steve_student = new Student("Jones", "Steve", "19", "123456", "13")

# We can now treat steve_student as a Person object
steve_person = steve_student
print(steve_person.first_name)

# We can call happy_birthday(), and it will use
# the code from the Student class, even if we 
# think that steve_student is a Person object
steve_person.happy_birthday()

# We can still treat it as a Student object as well
print(steve_person.grade_level) # 14

Polymorphism is a very powerful tool in programming, and we’ll use it throughout this course as we develop complex data structures.

Static and Abstract

Static

Many programming languages include a special keyword static. In essence, a static attribute or method is part of the class in which it is declared instead of part of objects instantiated from that class. If we think about it, the word static means “lacking in change”, and that’s sort of a good way to think about it.

In a UML diagram, static attributes and methods are denoted by underlining them.

Static Attributes

In Python, any attributes declared outside of a method are class attributes, but they can be considered the same as static attributes until they are overwritten by an instance. Here’s an example:

class Stat:
    x = 5     # class or static attribute
  
    def __init__(self, an_y):
        self.y = an_y # instance attribute

In this class, we’ve created a class attribute named x, and a normal attribute named y. Here’s a main() method that will help us explore how the static keyword operates:

from Stat import *

class Main:
  
    def main():
        some_stat = Stat(7)
        another_stat = Stat(8)

        print(some_stat.x)     # 5
        print(some_stat.y)     # 7 
        print(another_stat.x)  # 5
        print(another_stat.y)  # 8

        Stat.x = 25           # change class attribute for all instances

        print(some_stat.x)     # 25
        print(some_stat.y)     # 7 
        print(another_stat.x)  # 25 
        print(another_stat.y)  # 8

        some_stat.x = 10      # overwrites class attribute in instance

        print(some_stat.x)     # 10 (now an instance attribute)
        print(some_stat.y)     # 7 
        print(another_stat.x)  # 25 (still class attribute)
        print(another_stat.y)  # 8

if __name__ == "__main__":
    Main.main()

First, we can see that the attribute x is set to 5 as its default value, so both objects some_stat and another_stat contain that same value. Interestingly, since the attribute x is static, we can access it directly from the class Stat, without even having to instantiate an object. So, we can update the value in that way to 25, and it will take effect in any objects instantiated from Stat.

Below that, we can update the value of x attached to some_stat to 10, and we’ll see that it now creates an instance attribute for that object that contains 10, overwriting the previous class attribute. The value attached to another_stat is unchanged.

Static Methods

Python also allows us to create static methods that work in a similar way:

class Stat:
    x = 5     # class or static attribute
  
    def __init__(self, an_y):
        self.y = an_y # instance attribute
  
    @staticmethod
    def sum(a):
        return Stat.x + a

We have now added a static method sum() to our Stat class. To create a static method, we place the @staticmethod decorator above the method declaration. We haven’t learned about decorators yet, but they allow us to tell Python some important information about the code below the decorator.

In addition, it is important to remember that a static method cannot access any non-static attributes or methods, since it doesn’t have access to an instantiated object in the self parameter.

As a tradeoff, we can call a static method without instantiating the class either, as in this example:

from Stat import *

class Main:
  
    @staticmethod
    def main():
        # other code omitted
        Stat.x = 25
    
        moreStat = Stat(7)
        print(moreStat.sum(5))  # 30
        print(Stat.sum(5))      # 30

if __name__ == "__main__":
    Main.main()

This becomes extremely useful in our main() method. Since we aren’t instantiating our Main class, we can use the decorator @staticmethod above the method to clearly mark that it should be considered a static method.

Abstract

Another major feature of class inheritance is the ability to define a method in a parent class, but not provide any code that implements that function. In effect, we are saying that all objects of that type must include that method, but it is up to the child classes to provide the code. These methods are called abstract methods, and the classes that contain them are abstract classes. Let’s look at how they work!

Abstract in Python

In the UML diagram above, we see that the describe() method in the Vehicle class is printed in italics. That means that the method should be abstract, without any code provided. To do this in Python, we simply inherit from a special class called ABC, short for “Abstract Base Class,” and then use the @abstractmethod decorator:

from abc import ABC, abstractmethod

class Vehicle(ABC):
  
    def __init__(self, name):
        self.__name = name
        self._speed = 1.0
    
    @property
    def name(self):
        return self.__name
    
    def move(self, distance):
        print("Moving");
        return distance / self._speed;
  
    @abstractmethod
    def describe(self):
        pass

Notice that we must first import both the ABC class and the @abstractmethod decorator from a library helpfully called ABC. Then, we can use ABC as the parent class of our class, and update each method using the @abstractmethod decorator before the method, similar to how we’ve already used @staticmethod in an earlier module.

In addition, since we have declared the method describe() to be abstract, we can either add some code to that method that can be called using super().describe() from a child class, or we can simply choose to use the pass keyword to avoid including any code in the method.

Now, any class that inherits from the Vehicle class must provide an implementation for the describe() method. If it does not, that class must also be declared to be abstract. So, for example, in the UML diagram above, we see that the MotorVehicle class does not include an implementation for describe(), so we’ll also have to make it abstract.

Of course, that means that we’ll have to inherit from both Vehicle and ABC. In Python, we can do that by simply including both classes in parentheses after the subclass name, separated by a comma.

Object Oriented Programming Summary

This chapter covered the rest of the programming basics we’ll need to know before starting on the new content of this course. By now we should be pretty familiar with the basic syntax of the language we’ve chosen, as well as the concepts of classes, objects, inheritance, and polymorphism in object-oriented programming. Finally, we’ve explored the Model-View-Controller (MVC) architecture, which will be used extensively in this course.

Data Structures

One way to look at a computer program is to think of it as a list of instructions that the computer should follow. However, in another sense, many computer programs are simply ways to manipulate data to achieve a desired result. We’ve already written many programs that do this, from calculating the minimum and maximum values of a list of numbers, to storing and retrieving data about students and teachers in a school.

As we start to consider our programs as simply ways to manipulate data, we may quickly realize that we are performing the same actions over and over again, or even treating data in many similar ways. Over time, these ideas have become the basis for several common data structures that we may use in our programs.

¹

Data Structure

Broadly speaking, a data structure is any part of our program that stores data using a particular format or method. Typically data structures define how the data is arranged, how it is added to the structure, how it can be removed, and how it can be accessed.

Data structures can give us very useful ways to look at how our data is organized. In addition, a data structure may greatly impact how easy, or difficult, it can be to perform certain actions with the data. Finally, data structures also impose performance limitations on our code. Some structures may be better at performing a particular operation than others, so we may have to consider that as well when choosing a data structure for our program.

In this class, we’ll spend the majority of our time learning about these common data structures, as well as algorithmic techniques that work well with each one. By formalizing these structures and techniques, we are able to build a common set of building blocks that every programmer is familiar with, making it much easier to build programs that others can understand and reuse.

First, let’s review some of these common data structures and see how they could be useful in our programs.

Linear Structures

First, we can broadly separate the data structures we’re going to learn about into two types, linear and non-linear data structures.

A linear data structure typically stores data in a single dimension, just like an array. By using a linear data structure, we would know that a particular element in the data structure comes before another element or vice-versa, but that’s about it. A great example is seen in the image above. We have a list of numbers, and each element in the list comes before another element, as indicated by the arrows.

Linear Data Structure Hierarchy

Linear data structures can further be divided into two types: arrays, which are typically finite sized; and linked lists, which can be infinitely sized. We’ve already worked with arrays extensively by this point, but linked lists are most likely a new concept. That’s fine! We’ll explore how to build our own later in this course.

Using either arrays or linked lists, we can build the three most commonly used linear data structures: stacks, queues, and sets. However, before we learn about each of those, let’s review a bit more about what the list data structure itself looks like.

Lists

The list data structure is the simplest form of a linear data structure. As we can guess from the definition, a list is simply a grouping of data that is presented in a given order. With lists, not only do the elements in the list matter, but the order matters as well. It’s not simply enough to state that elements $8$, $6$ and $7$ are in the list, but generally we also know that $8$ comes before $6$, which comes before $7$.

We’ve already learned about arrays, which are perfect examples of lists in programming. In fact, Python uses the data type list in the same way most other programming languages use arrays. Other programming languages, such as Java, provide a list data structure through their standard libraries.

List Operations

One important way to classify data structures is by the operations they can perform on the data. Since a list is the simplest version of a linear data structure, it has several important operations it can perform:

• insert - inserts an element anywhere in the list, including at the beginning or the end;
• remove - removes an element from anywhere in the list, including at the beginning or the end;
• find - finds the location of the given element in the list, usually given as an index just like an array index;
• get - returns the element at a given location, similar to using an array index to retrieve an element from an array; and
• size - returns the number of elements in the list.

For example, let’s look at the insert operation. Assume we have the list shown in the following diagram:

Then, we decide we’d like to add the element $4$ at index $3$ in this list. So, we can think of this like trying to place the element in the list as shown below:

Once we insert that element, we then shift all of the other elements back one position, making the list one element larger. The final version is shown below:

Lists are a very powerful data structure, and one of the most commonly used in a variety of programs. While arrays may seem very flexible, their static size and limited operations can sometimes make them more difficult to use than they are worth. Many programmers choose to use the more flexible list data structure instead.

When to Use a List

When deciding which data structure to use, lists are best when we might be adding or removing data from anywhere in the list, but we want to maintain the ordering between elements. As we’ll see on the later pages, we can have more specific types of structures for particular ways we intend to add and remove data from our structure, but lists are a great choice if neither of those are a good fit.

Stacks and Queues

The next two data structures we’ll look at are stacks and queues. They are both very similar to lists in most respects, but each one puts a specific limitation on how the data structure operates that make them very useful in certain situations.

Stack

¹

A stack is one special version of a list. Specifically, a stack is a Last In, First Out or LIFO data structure.

So, what does that mean? Basically, we can only add elements to the end, or top of the stack. Then, when we want to get an element from the stack, we can only take the one from the top–the one that was most recently added.

A great way to think of a stack is like a stack of plates, such as the one pictured below:

²

When we want to add a new plate to the stack, we can just set it on top. Likewise, if we need a plate, we’ll just take the top one off and use it.

A stack supports three major unique operations:

• push - add an item to the top of the stack;
• pop - remove an item from the top of the stack; and
• peek - see what the top item on the stack is, but don’t remove it.

Many stacks also include additional operations such as size and find as well.

Queue

³

A queue is another special version of a list, this time representing a First In, First Out or FIFO data structure.

As seen in the diagram above, new items are added to the back of the queue. But, when we need to take an item from a queue, we’ll take the item that is in the front, which is the one that was added first.

Where have we seen this before? A great example is waiting our turn in line at the train station,

⁴

In many parts of the world, the term queueing is commonly used to refer to the act of standing in line. So, it makes perfect sense to use that same word to refer to a data structure.

When to Use a Stack or a Queue

As we can probably guess, we would definitely want to use a stack if we need our data structure to follow the last in, first out, or LIFO ordering. Similarly, we’d use a queue if we need first in, first out or FIFO ordering.

If we can’t be sure that one or the other of those orderings will work for us, then we can’t really use a stack or a queue in our program.

Why Not Just Use Lists?

Of course, one of the biggest questions that comes from this is “why not just use lists for everything?” Indeed, lists can be used as both a queue and a stack, simply by consistently inserting and removing elements from either the beginning or the end of the list as needed. So why do we need to have separate data structures for a queue and a stack?

There are two important reasons. First, if we know that we only need to access the most recently added element, or the element added first, it makes sense to have a special data structure for just that usage. In this way, it is clear to anyone else reading our program that we will only be using the data in that specific way. Behind the scenes, of course, we can just use a list to represent a queue or a stack, but in our design documents and in our code, it might be very helpful to know if we should think of it like a stack or a queue.

The other reason has to do with performance. By knowing exactly how we need to use the data, we can design data structures that are specifically created to perform certain operations very quickly and efficiently. A generic list data structure may not be as fast or memory efficient as a structure specifically designed to be used as a stack, for example.

As we learn about each of these data structures throughout this course, we’ll explore how each data structure works in terms of runtime performance and memory efficiency.

Sets

Another linear data structure is known as a set. A set is very similar to a list, but with two major differences:

1. A set cannot contain duplicate elements. Each element must be unique in the set.
2. A set does not necessarily keep track of the ordering of the elements within the set.

In fact, the term set comes from mathematics. We’ve probably seen sets already in a math class.

Beyond the typical operations to add and remove elements from a set, there are several operations unique to sets:

• union - find the elements that are contained in one or both of the sets given;
• intersection - find the elements only contained in both sets given;
• set difference - remove all elements from a set that are also contained in another set; and
• subset - test if all elements in one set are also contained in another set.

Again, many of these operations may be familiar from their use in various math classes.

Set Operations and Boolean Logic

In addition, we can easily think of set operations as boolean logic operators. For example, the set operation union is very similar to the boolean operator or, as seen in the diagram below.

¹

As long as an item is contained in one set or the other, it is included in the union of the sets.

Similarly, the same comparison works for the set operation intersection and the boolean and operator.

²

Once again, if an item is contained in the first set and the second set, it is contained in the intersection of those sets.

When to Use a Set

A set is a great choice when we know that our program should prevent duplicate items from being added to a data structure. Likewise, if we know we’ll be using some of the specific operations that are unique to sets, then a set is an excellent choice.

Of course, if we aren’t sure that our data structure will only store unique items, we won’t be able to use a set.

Maps

The last of the linear data structures may seem linear from the outside, but inside it can be quite a bit more complex.

The map data structure is an example of a key-value data structure, also known as a dictionary or associative array. In the simplest case, a map data structure keeps track of a key that uniquely identifies a particular value, and stores that value along with the key in the data structure.

Then, to retrieve that value, the program must simply provide the same key that was used to store it.

In a way, this is very similar to how we use an array, since we provide an array index to store and retrieve items from an array. The only difference is that the key in a map can be any data type! So it is a much more powerful data structure.

In fact, this data structure is one of the key ideas behind modern databases, allowing us to store and retrieve database records based on a unique primary key attached to each row in the database.

Map Operations

A map data structure should support the following operations:

• put - places a new value in the map using the given key,
• get - retrieves a value from the map using the given key,
• entries - gets all of the values in the map,
• keys - gets all of the keys in the map,
• containsKey - determines if the given key is in use in the map, and
• containsValue - determines if the given value is stored in the map.

Later in this course, we’ll devote an entire module to learning how to build our own map data structures and explore these operations in more detail.

Hash Table

¹

One of the most common ways to implement the map data structure is through the use of a hash table. A hash table uses an array to store the values in the map, and uses a special function called a hash function to convert the given key to a simple number. This number represents the array index for the value. In that way, the same key will always find the value that was given.

But what if we have two keys that produce the same array index? In that case, we’ll have to add some additional logic to our map to handle that situation.

When to Use a Map

Maps are great data structures when we need to store and retrieve data using a specific key. Just like we would store data in a database or put items in a numbered box to retrieve later, we can use a map as a general purpose storage and retrieval data structure.

Of course, if our data items don’t have unique keys assigned to them, then using a map may not be the best choice of data structure. Likewise, if each key is a sequential integer, we may be able to use an array just as easily.

Non-Linear Structures

¹

The other type of data structure we can use in our programs is the non-linear data structure.

Broadly speaking, non-linear data structures allow us to store data across multiple dimensions, and there may be multiple paths through the data to get from one item to another. In fact, much of the information stored in the data structure has to do with the paths between elements more than the elements themselves.

Non-Linear Data Structure Hierarchy

Just like linear data structures, there are several different types of non-linear data structures. In this case, each one is a more specialized version of the previous one, hence the hierarchy shown above. On the next few pages, we’ll explore each one just a bit to see what they look like.

Graphs

¹

The most general version of a non-linear data structure is the graph, as shown in the diagram above. A graph is a set of nodes that contain data, as well as a set of edges that link two nodes together. Edges themselves may also contain data.

Graphs are great for storing and visualizing not just data, but also the relationships between data. For example, each node in the graph could represent a city on the map, with the edges representing the travel time between the two cities. Or we could use the nodes in a graph to represent the people in a social network, and the edges represent connections or friendships between two people. There are many possibilities!

When to Use a Graph

Graphs are a great choice when we need to store data and relationships between the data, but we aren’t sure exactly what structures or limitations are present in the data. Since a graph is the most general and flexible non-linear data type, it has the most ability to represent data in a wide variety of ways.

Trees

[^1]

File:Tree (computer science).svg. (2019, October 20). Wikimedia Commons, the free media repository. Retrieved 03:13, February 8, 2020 from https://commons.wikimedia.org/w/index.php?title=File:Tree_(computer_science).svg&oldid=371240902.

A tree is a more constrained version of a graph data structure. Specifically, a tree is a graph that can be shown as a hierarchical structure, where each node in the tree is itself the root of a smaller tree. Each node in the tree can have one or more child nodes and exactly one parent node, except for the topmost node or root node, which has no parent nodes.

A tree is very useful for representing data in a hierarchical or sorted format. For example, one common use of a tree data structure is to represent knowledge and decisions that can be made to find particular items. The popular children’s game 20 Questions can be represented as a tree with 20 levels of nodes. Each node represents a particular question that can be asked, and the children of that node represent the possible answers. If the tree only contains yes and no questions, it can still represent up to $2^{20} = 1,408,576$ items!

Trie

Another commonly used tree data structure is the trie, which is a special type of tree used to represent textual data. Ever wonder how a computer can store an entire dictionary and quickly spell-check every single word in the language? It actually uses a trie!

Below is a small example of a trie data structure:

¹

This trie contains the words “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn” and “A” in just a few nodes and edges. Imagine creating a trie that could store the entire English language! While it might be large, we can hopefully see how it would be much more efficient to search and store that data in a trie instead of a linear data structure.

When to Use a Tree

A tree is a great choice for a data structure when there is an inherent hierarchy in our data, such that some nodes or elements are naturally “parents” of other elements. Likewise, if we know that each element may only have one parent but many children, a tree becomes an excellent choice. Trees contain several limitations that graphs do not, but they are also very powerful data structures.

Heaps

¹

The last non-linear data structure we’ll talk about is the heap, which is a specialized version of a tree. In a heap, we try to accomplish a few goals:

1. Store either the largest or smallest element in the heap at the root node,
2. Ensure that each parent node is either larger or smaller than all of its children, and
3. Minimize the height, or number of levels, of the tree.

If we follow those three guidelines, a heap becomes the most efficient data structure for managing a set of data where we always want to get the maximum or minimum value each time we remove an element. These are typically called priority queues, since we remove items based on their priority instead of the order they entered the queue.

Because of this, heaps are very important in creating efficient algorithms that deal with ordered data.

When to Use a Heap

As discussed above, a heap is an excellent data structure for when we need to store elements and then always be able to quickly retrieve either the smallest or largest element in the data structure. Heaps are a very specific version of a tree that specialize in efficiency over everything else, so they are only really good for a few specific uses.

Algorithms

¹

The other major topic covered in this course is the use of algorithms to manipulate the data stored in our data structures.

An algorithm is best defined as a finite list of specific instructions for performing a task. In the real world, we see algorithms all the time. A recipe for cooking your favorite dish, instructions for how to fix a broken car, or a method for solving a complex mathematical equation can all be considered examples of an algorithm. The flowchart above shows Euclid’s Algorithm for finding the greatest common divisor of two numbers.

In this course, however, we’re going to look specifically at the algorithms and algorithmic techniques that are most commonly used with data structures in computer programming.

Algorithmic Techniques

An algorithmic technique, sometimes referred to as a methodology or paradigm, is a particular way to design an algorithm. While there are a few commonly used algorithms across different data structures, many times each program may need a unique algorithm, or at least an adaptation of an existing algorithm. to perform its work.

To make these numerous algorithms easier to understand, we can loosely categorize them based on the techniques they use to solve the problem. On the next few pages, we’ll introduce some of the more commonly used algorithmic techniques in this course. Throughout this course, we will learn how to apply many of these techniques when designing algorithms that work with various data structures to accomplish a goal.

Brute Force

The first algorithmic technique we’ll use is the brute force technique. This is the algorithmic technique that most of us are most familiar with, even if we don’t realize it.

Simply put, a brute force algorithm will try all possible solutions to the problem, only stopping when it finds one that is the actual solution. A great example of a brute force algorithm in action is plugging in a USB cable. Many times, we will try one way, and if that doesn’t work, flip it over and try the other. Likewise, if we have a large number of keys but are unsure which one fits in a particular lock, we can just try each key until one works. That’s the essence of the brute force approach to algorithmic design.

Example - Closest Pair

¹

A great example of a brute force algorithm is finding the closest pair of points in a multidimensional space. This could be as simple as finding the two closest cities on a map, or the two closest stars in a galaxy.

To find the answer, a brute force approach would be to simply calculate the distance between each individual pair of points, and then keep track of the minimum distance found. A pseudocode version of this algorithm would be similar to the following.

MINIMUM = infinity
POINT1 = none
POINT2 = none
loop each POINTA in POINTS
    loop each POINTB in POINTS
        if POINTA != POINTB
            DISTANCE = COMPUTE_DISTANCE(POINTA, POINTB)
            if DISTANCE < MINIMUM
                MINIMUM = DISTANCE
                POINT1 = POINTA
                POINT2 = POINTB
            end if
        end if
    end loop
end loop

Looking at this code, if we have $N$ points, it would take $N^2$ steps to solve the problem! That’s not very efficient, event for a small data set. However, the code itself is really simple, and it is guaranteed to find exactly the best answer, provided we have enough time and a powerful enough computer to run the program.

In the project for this module, we’ll implement a few different brute-force algorithms to solve simple problems. This will help us gain more experience with this particular technique.

Divide and Conquer

The next most common algorithmic technique is divide and conquer. A divide and conquer algorithm works just like it sounds. First, it will divide the problem into at least two or more smaller problems, and then it will try to solve each of those problems individually. It might even try to subdivide those smaller problems again and again to finally get to a small enough problem that it is easy to solve.

A great real-world example of using a divide and conquer approach to solving a problem is when we need to look for something that we’ve lost around the house. Instead of trying to search the entire house, we can subdivide the problem into smaller parts by looking in each room separately. Then, within each room, we can even further subdivide the problem by looking at each piece of furniture individually. By reducing the problem’s size and complexity, it becomes easier to search through each individual piece of furniture in the house, either finding our lost object or eliminating that area as the likely location it will be found.

Example - Binary Search

One great example of a divide and conquer algorithm is the binary search algorithm. If we have a list of data that has already been sorted, as seen in the figure above, we can easily find any item in the list using a divide and conquer process.

For example, let’s say we want to find the value $19$ in that list. First, we can look at the item in the middle of the list, which is $23$. Is it our desired number? Unfortunately, it is not. So, we need to figure out how we can use it to divide our input into a smaller problem. Thankfully, we know the list is sorted, so we can use that to our advantage. If our desired number is less than the middle number, we know that it must exist in the first half of the list. Likewise, if it is greater than the middle number, it must be in the second half. In this case, since $19$ is less than $23$, we must only look at the first half of the list.

Now we can just repeat that process, this time using only the first half of the original list. This is the powerful feature of a divide and conquer algorithm. Once we’ve figured out how to divide our data, we can usually follow the same steps again to solve the smaller problems as well.

Once again, we ask ourselves if $12$, the centermost number in the list, is the one we are looking for. Once again, it is not, but we know that $19$ is greater than $12$, so we’ll need to look in the second half of the list.

Finally, we have reduced our problem to the simplest, or base case of the problem. Here, we simply need to determine if the single item in the list is the number we are looking for. In this case, it is! So, we can return that our original list did indeed include the number $19$.

We’ll explore many ways of using divide and conquer algorithms in this course, especially when we learn to sort and search through lists of values.

Greedy

Another algorithmic technique that we’ll learn about is the greedy technique. In a greedy algorithm, the program tries to build a solution one piece at a time. At each step, it will act “greedy” by choosing the piece that it thinks is the best choice for the solution based on the available information. Instead of trying every possible solution like a brute force algorithm or dividing the problem into smaller parts like the divide and conquer approach, a greedy algorithm will just try to construct the one best answer it can.

¹

Example

For example, we can use a greedy algorithm to determine the fewest number of coins needed to give change, as shown in the example above. If the customer is owed $36$ cents, and we have coins worth $20$ cents, $10$ cents, $5$ cents and $1$ cent, how many coins are needed to reach $36$ cents?

In a greedy solution, we could choose the coin with the highest value that is less than the change required, give that to the customer, and subtract its value from the remaining change. In this case, it will indeed produce the optimal solution.

In fact, both the United States dollar and the European euro have a system of coins that will always produce the minimum number of coins with a greedy algorithm. So that’s very helpful!

However, does it always work? What if we have a system that has coins worth $30$ cents, $18$ cents $4$ cents, and $1$ cent. Would a greedy algorithm produce the result with the minimum number of coins when making change for $36$ cents?

Let’s try it and see. First, we see that we can use a $30$ cent coin, leaving us with $6$ cents left. Then, we can use a single $4$ cent coin, as well as two $1$ cent coins for a total of $4$ coins: $30 + 4 + 1 + 1 = 36$.

Is that the minimum number of coins?

It turns out that this system includes a coin worth $18$ cents. So, to make $36$ cents, we really only need $2$ coins: $18 + 18 = 36$!

This is the biggest weakness of the greedy approach to algorithm design. A greedy algorithm will find a possible solution, but it is not guaranteed to be the best possible solution. Sometimes it will work just fine, but other times it may produce solutions that are not very good at all. So we always must consider that when creating an algorithm using a greedy technique.

Recursion

The next algorithmic technique we’ll discuss is recursion. Recursion is closely related to the divide and conquer method we discussed earlier. However, recursion itself is a very complicated term to understand. It usually presents one of the most difficult challenges for a novice programmer to overcome when learning to write more advanced programs. Don’t worry! We’ll spend an entire module on recursion later in this course.

What is Recursion?

There are many different ways to define recursion. In one sense, recursion is a problem solving technique where the solution to a problem depends on solutions to smaller versions of the problem, very similar to the divide and conquer approach.

However, to most programmers, the term recursion is used to describe a function or method that calls itself inside of its own code. It may seem strange at first, but there are many instances in programming where a method can actually call itself again to help solve a difficult problem. However, writing recursive programs can be tricky at first, since there are many ways to make simple errors using recursion that cause our programs to break.

Mastering recursion takes quite a bit of time and practice, and nearly every programmer has a strong memory of the first time recursion made sense in their minds. So, it is important to make sure we understand it! In fact, it is so notable, that when we search for “recursion” on Google, it helpfully prompts us if we want to search for “recursion” instead, as seen at the top of this page.

Example - Factorial

A great example of a recursive method is calculating the factorial of a number. We may recall from mathematics that the factorial of a number is the product of each integer from 1 up to and including that number. For example, the factorial of $5$, written as $5!$, is calculated as $5 * 4 * 3 * 2 * 1 = 120$

We can easily write a traditional method to calculate the factorial of a number as follows.

function ITERATIVE_FACTORIAL(N)
    RESULT = 1
    loop I from 1 to N:
        RESULT = RESULT * I
    end loop
    return RESULT
end function

However, we may also realize that the value of $5!$ is the same as $4! * 5$. If we already know how to find the factorial of $4$, we can just multiply that result by $5$ to find the factorial of $5$. As it turns out, there are many problems in the real world that work just like this, and, in fact, many of the data structures we’ll learn about are built in a similar way.

We can rewrite this iterative function to be a recursive function instead.

function RECURSIVE_FACTORIAL(N)
    if N == 1
        return 1
    else
        return N * RECURSIVE_FACTORIAL(N - 1)
    end if
end function

As we can see, a recursive function includes two important elements, the base case and a recursive case. We need to include the base case so we can stop calling our recursive function over and over again, and actually reach a solution. This is similar to the termination condition of a for loop or while loop. If we forget to include the base case, our program will recurse infinitely!

The second part, the recursive case, is used to reduce the problem to a smaller version of the same problem. In this case, we reduce $N!$ to $N * (N - 1)!$. Then, we can just call our function again to solve the problem $(N - 1)!$, and multiply the result by $N$ to find the solution to $N!$.

So, if we have a problem that can be reduced to a smaller instance of itself, we may be able to use recursion to solve it!

Graph Traversal

Beyond the algorithmic techniques we’ve introduced so far, there are a number of techniques that deal specifically with data stored in non-linear data structures based on graphs. Generally speaking, we can group all of these algorithms under the heading graph traversal algorithms.

A graph traversal algorithm constructs an answer to a problem by moving between nodes in a graph using the graph’s edges, thereby traversing the graph. For example, a graph traversal algorithm could be used by a mapping program to construct a route from one city to another on a map, or to determine friends in common on a social networking website.

Example - Dijkstra’s Algorithm

¹

A great example of a graph traversal algorithm is Dijkstra’s Algorithm, which can be used to find the shortest path between two selected nodes in a graph. In the image above, we can see the process of running Dijkstra’s Algorithm on a graph that contains just a few nodes.

¹

Of course, we can use the same approach on any open space, as seen in this animation. Starting at the lower left corner, the algorithm slowly works toward the goal node, but it eventually runs into an obstacle. So, it must find a way around the obstacle while still finding the shortest path to the goal.

Algorithms such as Dijkstra’s Algorithm, and a more refined version called the A* Algorithm are used in many different computer programs to help find a path between two points, especially in video games.

Programming by Contract

In this course, we will learn how to develop several different data structures, and then use those data structures in programs that implement several different types of algorithms. However, one of the most difficult parts of programming is clearly explaining what a program should do and how it should perform.

So far, we’ve used UML class diagrams to discuss the structure of a program. It can give us information about the classes, attributes, and methods that our program will contain, as well as the overall relationships between the classes. We can even learn if attributes and methods are private or public, and more.

However, to describe what each method does, we have simply relied on descriptions in plain language up to this point, with no specific format at all. In this module, we’ll introduce the concept of programming by contract to help us provide more specific information about what each method should do and the expectations we can count on based on the inputs and outputs of the method.

Specifically, we’ll learn about the preconditions that are applied to the parameters of a method to make sure they are valid, the postconditions that the method will guarantee if the preconditions are met, and the invariants that a loop or data structure will maintain.

Finally, we can put all of that information together to discuss how to prove that an algorithm correctly performs the task it was meant to, and how to make sure that it works correctly in all possible cases.

Preconditions

First, let’s discuss preconditions. A precondition is an expectation applied to any parameters and existing variables when a method or function is called. Phrased a different way, the preconditions should all be true before the method is called. If all of the preconditions are met, the function can proceed and is expected to function properly. However, if any one of the preconditions are not met, the function may either reach an exception, prompt the user to correct the issue, or produce invalid output, depending on how it is written.

Example - Area of a Triangle

Let’s consider an example method to see how we can define the preconditions applied to that method. In this example, we’re going to write a method triangleArea(side1, side2, side3) that will calculate the area of a triangle, given the lengths of the sides of the triangle.

So, to determine what the preconditions of that method should be, we must think about what we know about a triangle and what sort of data we expect to receive.

For example, we know that the length of each side should be a number. In addition, those lengths should all be positive, so each one must be strictly greater than $0$.

We can also determine if we expect the length to be whole numbers or floating-point numbers. To make this example simpler, let’s just work with whole numbers.

When looking at preconditions, determining the types and expected range of values of each parameter is a major first step. However, sometimes we must also look at the relationship between the parameters to find additional preconditions that we must consider.

¹

For example, the triangle inequality states that the longest side of a triangle must be strictly shorter than the sum of the other two sides. Otherwise, those sides will not create a triangle. So, another precondition must state that the sides satisfy the triangle inequality.

All together, we’ve found the following preconditions for our method triangleArea(side1, side2, side3):

1. side1, side2 and side3 each must each be an integer that is strictly greater than $0$
2. side1, side2 and side3 must satisfy the triangle inequality

Precondition Failures

What if our method is called and provided a set of parameters that do not meet the preconditions described above? As a programmer, there are several actions we can take in our code to deal with the situation.

Exceptions

One of the most common ways to handle precondition failures is to simply throw or raise exceptions from our method as soon as it determines that the preconditions are not met. In this way, we can quickly indicate that the program is unable to perform the requested operation, and leave it up to the code that called that method to either handle the exception or ignore it and allow the program to crash.

This method is best used within the model portions of a program written using the Model-View-Controller or MVC architecture. By doing so, this allows our controller to react to problems quickly, usually by requesting additional input from the user using the view portion of the program.

Prompt User

In simpler programs, it is common for the code to simply handle the precondition failure by asking the user for new input. This is commonly done in programs that are small enough to fit in a single class, instead of being developed using MVC architecture.

Incorrect Output

Of course, we could choose to simply ignore these precondition failures and allow our code to continue running. IN that case, if the preconditions are not met, then the answer we receive may be completely invalid. On the next page, we’ll discuss how failed preconditions affect whether we can trust our method’s output.

Postconditions

Next, we can discuss postconditions. A postcondition is a statement that is guaranteed to be true after a method is executed, provided all of the preconditions were met. If any one of the preconditions were not met, then we can’t count on the postcondition being true either. This is the most important concept surrounding preconditions and postconditions.

Example - Area of a Triangle

On the last page, we discussed the preconditions for a method triangleArea(side1, side2, side3) that will calculate the area of a triangle given the lengths of its sides. Those preconditions are:

1. side1, side2 and side3 each must each be an integer that is strictly greater than $0$
2. side1, side2 and side3 must satisfy the triangle inequality

So, once the method completes, what should our postcondition be? In this case, we want to find a statement that would be always true if all of the preconditions are met.

Since the method will be calculating the area of the triangle, the strongest postcondition we can use is the most obvious one:

1. The method will return the area of a triangle with side lengths side1, side2 and side3

That’s really it!

Of course, there are a few other postconditions that we could consider, especially when we start working with data structures and objects. For example, one of the most powerful postconditions is the statement:

1. The values of the parameters are not modified from their original values

When we call a method that accepts an array or object as a parameter, we know that we can modify the values stored in that array or object because the parameter is handled in a call-by-reference fashion in most languages. So, if we don’t state that this postcondition applies, we can’t guarantee that the method did not change the values in the array or object we provided as a parameter.

Precondition Failures: Incorrect Output

So, what if the preconditions are not met? Then what happens?

As we discussed on the previous page, if the preconditions are not met, then we cannot guarantee that the postcondition will be true once the method executes. In fact, it may be decidedly incorrect, depending on how we implement the method.

¹

For example, the simplest way to find the area of a triangle given the lengths of all three sides is Heron’s formula, which can be written mathematically as:

Since this is a mathematical formula, it is always possible to get a result from it, even if all of the preconditions are not met. For example, the inputs could be floating-point values instead of integers, or they may not satisfy the triangle inequality. In that case, the function may still produce a result, but it will not represent the actual area of the triangle described, mainly because the parameters provided describe a triangle that cannot exist in the real world. So, we must always be careful not to assume that a method will always provide the correct output unless we provide parameters that make all of its preconditions true.

Unit Testing

Once we’ve written a program, how can we verify that it works correctly? There are many ways to do this, but one of the most common is unit testing.

Unit Testing

Unit testing a program involves writing code that actually runs the program and verifies that it works correctly. In addition, many unit tests will also check that the program produces appropriate errors when given bad input, or even that it won’t crash when given invalid input.

For example, a simple unit test for the maximum() method would be:

function MAXIMUMTEST()
    ARRAY = new array[5]
    ARRAY[0] = 5
    ARRAY[1] = 25
    ARRAY[2] = 10
    ARRAY[3] = 15
    ARRAY[4] = 0
    RESULT = MAXIMUM(ARRAY)
    if RESULT == 25:
        print "Test Passed"
    end if
end function

This code will simply create an array that we know the maximum value of, and then confirm that our own maximum() method will find the correct result.

Of course, this is a very simplistic unit test, and it would take several more unit tests to fully confirm that the maximum() method works completely correctly.

However, it is important to understand how this test relates to the preconditions and postconditions that were established on previous pages. Here, the unit tests creates a variable ARRAY which is an array of at least one numerical value. Therefore, it has met the preconditions for the maximum() method, so we can assume that if maximum() is written correctly, then the postconditions will be true once it is has executed. This is the key assumption behind unit tests.

Data Structures & Algorithms Summary

In this chapter, we introduced a number of different data structures that we can use in our programs. In addition, we explored several algorithmic techniques we can use to develop algorithms that manipulate these data structures to allow us to solve complex problems in our code.

Throughout the rest of this course, as well as a subsequent course, we’ll explore many of these data structures and techniques in detail. We hope that introducing them all at the same time here will allow us to compare and contrast each one as we learn more about it, while still keeping in mind that there are many different structures and techniques that will be available to us in the future.

What is a Stack?

A stack is a data structure with two main operations that are simple in concept. One is the push operation that lets you put data into the data structure and the other is the pop operation that lets you get data out of the structure.

Why do we call it a stack? Think about a stack of boxes. When you stack boxes, you can do one of two things: put boxes onto the stack and take boxes off of the stack. And here is the key. You can only put boxes on the top of the stack, and you can only take boxes off the top of the stack. That’s how stacks work in programming as well!

A stack is what we call a “Last In First Out”, or LIFO, data structure. That means that when we pop a piece of data off the stack, we get the last piece of data we put on the stack.

Stacks in the Real World

So, where do we see stacks in the real world? A great example is repairing an automobile. It is much easier to put a car back together if we put the pieces back on in the reverse order we took them off. Thus, as we take parts off a car, it is highly recommended that we lay them out in a line. Then, when we are ready to put things back together, we can just start at the last piece we took off and work our way back. This operation is exactly how a stack works.

Another example is a stack of chairs. Often in schools or in places that hold different types of events, chairs are stacked in large piles to make moving the chairs easier and to make their storage more efficient. Once again, however, if we are going to put chairs onto the stack or remove chairs from the stack, we are going to have to do it from the top.

Stacks in Code

How do we implement stacks in code? One way would be to use something we already understand, an array. Remember that arrays allow us to store multiple items, where each entry in the array has a unique index number. This is a great way to implement stacks. We can store items directly in the array and use a special top variable to hold the index of the top of the stack.

The following figure shows how we might implement a stack with an array. First, we define our array myStack to be an array that can hold 10 numbers, with an index of 0 to 9. Then we create a top variable that keeps track of the index at the top of the array.

Notice that since we have not put any items onto the stack, we initialize top to be -1. Although this is not a legal index into the array, we can use it to recognize when the stack is empty, and it makes manipulating items in the array much simpler. When we want to push an item onto the stack, we follow a simple procedure as shown below. Of course, since our array has a fixed size, we need to make sure that we don’t try to put an item in a full array. Thus, the precondition is that the array cannot be full. Enforcing this precondition is the function of the if statement at the beginning of the function. If the array is already full, then we’ll throw an exception and let the user handle the situation. Next, we increment the top variable to point to the next available location to store our data. Then it is just a matter of storing the item into the array at the index stored in top.

function PUSH(ITEM)
    if MYSTACK is full then
        throw exception
    end if
    TOP = TOP + 1
    MYSTACK[TOP] = ITEM
end function

If we call the function push(a) and follow the pseudocode above, we will get an array with a stored in myStack[0] and top will have the value 0 as shown below.

As we push items onto the stack, we continue to increment top and store the items on the stack. The figure below shows how the stack would look if we performed the following push operations.

push("b")
push("c")
push("d")
push("e")

Although we are implementing our stack with an array, we often show stacks vertically instead of horizontally as shown below. In this way the semantics of top makes more sense.

Of course, the next question you might ask is “how do we get items off the stack?”. As discussed above, we have a special operation called pop to take care of that for us. The pseudocode for the pop operation is shown below and is similar in structure to the push operation.

function POP
    if TOP == -1 then
        throw exception
    end if
    TOP = TOP - 1
    return MYSTACK[TOP + 1]
end function

However, instead of checking to see if the stack is full, we need to check if the stack is empty. Thus, our precondition is that the stack is not empty, which we evaluate by checking if top is equal to -1. If it is, we simply throw an exception and let the user handle it. If myStack is not empty, then we can go ahead and perform the pop function. We simply decrement the value of top and return the value stored in myStack[top+1].

Now, if we perform three straight pop operations, we get the following stack.

Stack Operations

The following table shows an example of how to use the above operations to create and manipulate a stack. It assumes the steps are performed sequentially and the result of the operation is shown.

Step	Operation	Effect
1	Constructor	Creates an empty stack.
2	isFull()	Returns false since top is not equal to the capacity of the stack.
3	isEmpty()	Returns true since top is equal to -1
4	push(1)	Increments top by 1 and then places item $1$ onto the top of the stack
5	push(2)	Increments top by 1 and then places item $2$ onto the top of the stack
6	push(3)	Increments top by 1 and then places item $3$ onto the top of the stack
7	peek()	Returns the item $3$ on the top of the stack but does not remove the item from the stack. top is unaffected by peek
8	pop()	Returns the item $3$ from the top of the stack and removes the item from the stack. top is decremented by 1.
9	pop()	Returns the item $2$ from the top of the stack and removes the item from the stack. top is decremented by 1.
10	pop()	Returns the item $1$ from the top of the stack and removes the item from the stack. top is decremented by 1.
11	isEmpty()	Returns true since top is equal to -1

Using a Stack

Stacks are useful in many applications. Classic real-world software that uses stacks includes the undo feature in a text editor, or the forward and back features of web browsers. In a text editor, each user action is pushed onto the stack as it is performed. Then, if the user wants to undo an action, the text editor simply pops the stack to get the last action performed, and then undoes the action. The redo command can be implemented as a second stack. In this case, when actions are popped from the stack in order to undo them, they are pushed onto the redo stack.

Maze Explorer

Another example is a maze exploration application. In this application, we are given a maze, a starting location, and an ending location. Our first goal is to find a path from the start location to the end location. Once we’ve arrived at the end location, our goal becomes returning to the start location in the most direct manner.

We can do this simply with a stack. We will have to search the maze to find the path from the starting location to the ending location. Each time we take a step forward, we push that move onto a stack. If we run into a dead end, we can simply retrace our steps by popping moves off the list and looking for an alternative path. Once we reach the end state, we will have our path stored in the stack. At this point it becomes easy to follow our path backward by popping each move off the top of the stack and performing it. There is no searching involved.

We start with a maze, a startCell, a goalCell, and a stack as shown below. In this case our startCell is 0,0 and our end goal is 1,1. We will store each location on the stack as we move to that location. We will also keep track of the direction we are headed: up, right, down, or left, which we’ll abbreviate as u,r,d,and l.

In our first step, we will store our location and direction 0,0,u on the stack.

For the second step, we will try to move “up”, or to location 1,0. However, that square in the maze is blocked. So, we change our direction to r as shown below.

After turning right, we attempt to move in that direction to square 0,1, which is successful. Thus, we create a new location 0,1,u and push it on the stack. (Here we always assume we point up when we enter a new square.) The new state of the maze and our stack are shown below.

Next, we try to move to 1,1, which again is successful. We again push our new location 1,1,u onto the stack. And, since our current location matches our goalCell location (ignoring the direction indicator) we recognize that we have reached our goal.

Of course, it’s one thing to find our goal cell, but it’s another thing to get back to our starting position. However, we already know the path back given our wise choice of data structures. Since we stored the path in a stack, we can now simply reverse our path and move back to the start cell. All we need to do is pop the top location off of the stack and move to that location over and over again until the stack is empty. The pseudocode for following the path back home is simple.

loop while !MYSTACK.ISEMPTY()
	NEXTLOCATION = MYSTACK.POP()
	MOVETO(NEXTLOCATION)
end while

Path Finding Algorithm

The pseudocode for finding the initial path using the stack is shown below. We assume the enclosing class has already defined a stack called myStack and the datatype called Cell, which represents the squares in the maze. The algorithm also uses three helper functions as described below:

• getNextCell(maze, topCell): computes the next cell based on our current cell’s location and direction;
• incrementDirection(topCell): increments a cell’s direction attribute following the clockwise sequence of up, right, down, left, and then finally done, which means that we’ve tried all directions; and
• valid(nextCell): determines if a cell is valid. A cell is invalid if it is “blocked”, is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack).

The parameters of findPath are a 2-dimensional array called maze, the startCell and the endCell. The algorithm begins by pushing the startCell onto myStack. The cell at the top of the stack will always represent our current cell, while the remaining cells in the stack represent the path of cells taken to reach the current cell.

Next, we enter a loop, where we will do the bulk of the work. We peek at the cell on the top of the stack in order to use it in our computations. If the topCell is equal to our goalCell, then we are done and return true indicating that we have found a path to the goal.

If we are not at our goal, we check to see if we have searched all directions from the current cell. If that is the case, then the direction attribute of the topCell will have been set to done. If the direction attribute of topCell is equal to done, then we pop the topCell of the stack, effectively leaving that cell and returning to the next cell in the stack. This is an algorithmic technique called backtracking.

function FINDPATH(MAZE, STARTCELL, GOALCELL)
    MYSTACK.PUSH(STARTCELL);
	loop while !MYSTACK.ISEMPTY()
        TOPCELL = MYSTACK.PEEK()
		if TOPCELL equals GOALCELL
			return true
		if TOPCELL.GETDIRECTION() = done then
            MYSTACK.POP()
		else
            NEXTCELL = GETNEXTCELL(MAZE, TOPCELL)
            INCREMENTDIRECTION(TOPCELL)	
			if VALID(MAZE, NEXTCELL) then
				if MYSTACK.ISFULL() then
                    MYSTACK.DOUBLECAPACITY();
				end if
                MYSTACK.PUSH(NEXTCELL)
			end if 
		end if
	end while 
	return false
end function

However, if we have not searched in all directions from topCell, we will try to explore a new cell (nextCell) adjacent to the topCell. Specifically, nextCell will be the adjacent cell in the direction stored by the direction attribute. We then increment the direction attribute of the topCell so if we end up backtracking, we will know which direction to try next.

Before we push the nextCell onto the stack, we must first check to see if it’s a valid cell by calling the helper function valid. A cell is valid if it is open to be explored. A cell is invalid if it is “blocked,” is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack). To help us determine if a cell is in the stack, we will need to extend our stack operations to include a find operation that searches the stack while leaving its contents intact. You will get to implement this operation in your project.

If nextCell is valid, we then check to make sure that the stack is not already full. If it is, we simply call doubleCapacity and continue on our way. Then we push nextCell onto myStack so it will become our next topCell on the next pass through the loop.

After we have explored all possible paths through the maze, the loop will eventually end, and the operation will return false indicating no path was found. While this is not the most efficient path finding algorithm, it is a good example of using stacks for backtracking. Also, if we do find a path and return, the path will be saved in the stack. We can then use the previous pseudocode for retracing our steps and going back to the startCell.

What is a Queue?

A queue (pronounced like the letter “q”) data structure organizes data in a First In, First Out (FIFO) order: the first piece of data put into the queue is the first piece of data available to remove from the queue. A queue functions just like the line you would get into to go into a ballgame, movie, or concert: the person that arrives first is the first to get into the venue.

¹

You might be thinking that this sounds a lot like the stack structure we studied a few modules back, with the exception that the stack was a Last in, First Out (LIFO) structure. If so, you are correct. The real difference between a stack and a queue is how we take data out of the data structure. In a stack, we put data onto the top of the stack and removed it from the top as well. With a queue, we put data onto the end (or rear) of the queue and remove it from the start (or front) of the queue.

Queues in the Real World

The name for queues comes the word in British English used to describe a line of people. Instead of forming lines to wait for some service, British form queues. Thus, when we think of queues, often the first picture to come to mind is a group of people standing in a line. Of course, this is exactly how a computer queue operates as well. The first person in line gets served first. If I get into line before you do, then I will be served before you do.

¹

Of course, there are other examples of queues besides lines of people. You can think of a train as a long line of railway cars. They are all connected and move together as the train engine pulls them. A line of cars waiting to go through a toll booth or to cross a border is another good example of a queue. The first car in line will be the first car to get through the toll booth. In the picture below, there are actually several lines.

²

Queues in Code

How do we implement queues in code? Like we did with stacks, we will use an array, which is an easily understandable way to implement queues. We will store data directly in the array and use special start and end variables to keep track of the start of the queue and the end of the queue.

The following figure shows how we might implement a queue with an array. First, we define our array myQueue to be an array that can hold 10 numbers, with an index of 0 to 9. Then we create a start variable to keep track of the index at the start of the queue and an end variable to keep track of the end of the array.

Notice that since we have not put any items into the queue, we initialize start to be -1. Although this is not a legal index into the array, we can use it like we did with stacks to recognize when we have not yet put anything into the queue. As we will see, this also makes manipulating items in the array much simpler. However, to make our use of the array more efficient, -1 will not always indicate that the queue is empty. We will allow the queue to wrap around the array from the start index to the end index. We’ll see an example of this behavior later.

When we want to enqueue an item into the queue, we follow the simple procedure as shown below. Of course, since our array has a fixed size, we need to make sure that we don’t try to put an item in a full array. Thus, the precondition is that the array cannot be full. Enforcing this precondition is the function of the if statement at line 2. If the array is already full, then we’ll throw an exception in line 3 and let the caller handle the situation. Next, we store item at the end location and then compute the new value of end in line 5. Line 6 uses the modulo operator % to return the remainder of the division of $(\text{end} + 1) / \text{length of myQueue}$. In our example, this is helpful when we get to the end of our ten-element array. If end == 9 before enqueue was called, the function would store item in myQueue[9] and then line 4 would cause end to be $(9 +1) % 10$ or $10 % 10$ which is simply $0$, essentially wrapping the queue around the end of the array and continuing it at the beginning of the array.

 1function ENQUEUE (item)
 2  if ISFULL() then
 3    raise exception
 4  end if	
 5  MYQUEUE[END] = ITEM	
 6  END = (END + 1) % length of MYQUEUE
 7  if START == -1
 8    START = 0
 9  end if
10end function

Given our initial configuration above, if we performed an enqueue(7) function call, the result would look like the following.

Notice that the value 7 was stored at myQueue[0] in line 5, end was updated to 1 in line 6, and start was set to 0 in line 8. Now, let’s assume we continue to perform enqueue operations until myQueue is almost filled as shown below.

If at this point, we enqueue another number, say -35, the modulo operator in line 6 would help us wrap the end of the list around the array and back to the beginning as expected. The result of this function call is shown below.

Now we have a problem! The array is full of numbers and if we try to enqueue another number, the enqueue function will raise an exception in line 3. However, this example also gives us insight into what the isFull condition should be. Notice that both start, and end are pointing at the same array index. You may want to think about this a little, but you should be able to convince yourself that whenever start == end we will be in a situation like the one above where the array is full, and we cannot safely enqueue another number.

To rectify our situation, we need to have a function to take things out of the queue. We call this function dequeue, which returns the item at the beginning of the queue (pointed at by start) and updates the value of start to point to the next location in the queue. The pseudocode for the dequeue is shown below.

 1function DEQUEUE ()
 2  if ISEMPTY() then
 3    raise exception
 4  end if 
 5  ITEM = MYQUEUE[START]
 6  START = (START + 1) % length of MYQUEUE
 7  if START == END
 8    START = -1
 9    END = 0
10  end if
11  return ITEM
12end function

Line 2 checks if the queue is empty and raises an exception in line 3 if it is. Otherwise, we copy the item at the start location into item at line 5 and then increment the value of start by 1, using the modulo operator to wrap to the beginning of the array if needed in line 6. However, if we dequeue the last item in the queue, we will actually run into the same situation that we ran into in the enqueue when we filled the array, start == end. Since we need to differentiate between being full or empty (it’s kind of important!), we reset the start and end values back to their initial state when we dequeue the last item in the queue. That is, we set start = -1 and end = 0. This way, we will always be able to tell the difference between the queue being empty or full. Finally, we return the item to the calling function in line 11.

Using Operations

The following table shows an example of how to use the above operations to create and manipulate a queue. It assumes the steps are performed sequentially and the result of the operation is shown.

Step	Operation	Effect
1	Constructor	Creates an empty queue of capacity 3.
2	isFull()	Returns false since start is not equal to end
3	isEmpty()	Returns true since start is equal to -1.
4	enqueue(1)	Places item 1 onto queue at the end and increments end by 1.
5	enqueue(2)	Places item 2 onto queue at the end and increments end by 1.
6	enqueue(3)	Places item 3 onto queue at the end and sets end to end+1 modulo the size of the array (3). The result of the operation is 0, thus end is set to 0.
7	peek()	Returns the item 1 on the start of the queue but does not remove the item from the queue. start and end are unaffected by peek.
8	isFull()	Returns true since start is equal to end
9	dequeue()	Returns the item 1 from the start of the queue. start is incremented by 1, effectively removing 1 from the queue.
10	dequeue()	Returns the item 2 from the start of the queue. start is incremented by 1, effectively removing 2 from the queue.
11	enqueue(4)	Places item 4 onto queue at the end and increments end.
12	dequeue()	Returns the item 3 from the start of the queue. start is set to start+1 modulo the size of the array (3). The result of the operation is 0, thus start is set to 0.
13	dequeue()	Returns the item 4 from the start of the queue. start is incremented by 1, and since start == end, they are both reset to -1 and 0 respectively.
14	isEmpty()	Returns true since start is equal to -1.

Using a Queue

Queues are useful in many applications. Classic real-world software which uses queues includes the scheduling of tasks, sharing of resources, and processing of messages in the proper order. A common need is to schedule tasks to be executed based on their priority. This type of scheduling can be done in a computer or on an assembly line floor, but the basic concept is the same.

Let’s assume that we are putting windshields onto new cars in a production line. In addition, there are some cars that we want to rush through production faster than others. There are actually three different priorities:

1. High priority: these cars have been ordered by customers who are waiting for them.
2. Medium priority: these cars have been ordered as “fleet cars” for specific companies.
3. Low priority: these cars are cars used to fill dealer inventories.

Ideally, as cars come to the windshield station, we would be able to put their windshields in and send them to the next station before we received the next car. However, this is rarely the case. Since putting on windshields often requires special attention, cars tend to line up to get their windows installed. This is when their priority comes into account. Instead of using a simple queue to line cars up first-come, first-served in FIFO order, we would like to jump high priority cars to the head of the line.

While we could build a sophisticated queueing mechanism that would automatically insert cars in the appropriate order based on priority and then arrival time, we could also use a queue to handle each set of car priorities. A figure illustrating this situation is shown below. As cars come in, they are put in one of three queues: high priority, medium priority, or low priority. When the windshield station completes a car it then takes the next car from the highest priority queue.

The interesting part of the problem is the controller at the windshield station that determines which car will be selected to be worked on next. The controller will need to have the following interface:

function receiveCar(car, priority)
 // receives a car from the previous station and places into a specific queue

function bool isEmpty()
 // returns true if there are no more cars in the queue

function getCar() returns car
 // retrieves the next car based on priority

Using this simple interface, we will define a class to act as the windshield station controller. It will receive cars from the previous station and get cars for the windshield station.

We start by defining the internal attributes and constructor for the Controller class as follows, using the Queue functions defined earlier in this module. We first declare three separate queues, one each for high, medium, and low priority cars. Next, we create the constructor for the Controller class. The constructor simply initializes our three queues with varying capacities based on the expected usage of each of the queues. Notice, that the high priority queue has the smallest capacity while the low priority queue has the largest capacity.

class Controller
    declare HIGH as a Queue
    declare MEDIUM as a Queue
    declare LOW as a Queue

    function Controller()
        HIGH = new Queue(4)
        MEDIUM = new Queue(6)
        LOW = new Queue(8)
    end function

Next, we need to define the interface function as defined above. We start with the receiveCar function. There are three cases based on the priority of the car. If we look at the first case for priority == high, we check to see if the high queue is full before calling the enqueue function to place the car into the high queue. If the queue is full, we raise an exception. We follow the exact same logic for the medium and low priority cars as well. Finally, there is a final else that captures the case where the user did not specific either high, medium, or low priority. In this case, an exception is raised.

function receiveCar(CAR, PRIORITY)
    if PRIORITY == high
        if HIGH.isFull()
            raise exception
        else
            HIGH.enqueue(CAR)
        end if
    else PRIORITY == medium
        if MEDIUM.isFull()
            raise exception
        else
            MEDIUM.enqueue(CAR)
        end if
    else PRIORITY == low
        if LOW.isFull()
            raise exception
        else
            LOW.enqueue(CAR)
        end if
    else
        raise exception
    end if
end function

Now we will define the isEmpty function. While we do not include an isFull function due to the ambiguity of what that would mean and how it might be useful, the isEmpty function will be useful for the windshield station to check before they request another call via the getCar function.

As you can see below, the isEmpty function simply returns the logical AND of each of the individual queue’s isEmpty status. Thus, the function will return true if, and only if, each of the high, medium, and low queues are empty.

function isEmpty()
    return HIGH.isEmpty() and MEDIUM.isEmpty() and LOW.isEmpty()
end function

Finally, we are able to define the getCar function. It is similar in structure to the receiveCar function in that it checks each queue individually. In the case of getCar, the key to the priority mechanism we are developing is in the order we check the queues. In this case, we check them in the expected order from high to low. If the high queue is not empty, we get the car from that queue and return it to the calling function. If the high queue is empty, then we check the medium queue. Likewise, if the medium queue is empty, we check the low queue. Finally, if all of the queues are empty, we raise an exception.

function getCar()
    if not HIGH.isEmpty()
        return HIGH.dequeue()
    else not MEDIUM.isEmpty()
        return MEDIUM.dequeue()
    else not LOW.isEmpty()
        return LOW.dequeue()
    else
        raise exception
    end if
end function

Windshield Station Example

The following example shows how the Controller class would work, given specific calls to receiveCar and getCar.

Step	Operation	Effect
1	Constructor	Creates 3 priority queues.
2	getCar()	Raises an exception since all three queues will be empty.
3	receiveCar(a, low)	Places car a into the low queue.
4	receiveCar(b, low)	Places car b into the low queue.
5	receiveCar(f, high)	Places car f into the high queue.
6	receiveCar(d, medium)	Places car d into the medium queue.
7	receiveCar(g, high)	Raises an exception since the high queue is already full.
8	receiveCar(e, medium)	Places car e into the medium queue.
9	getCar()	Returns car f from the high queue.
10	getCar()	Returns car d from the medium queue.
11	getCar()	Returns car e from the medium queue.
12	getCar()	Returns car a from the low queue.
13	getCar()	Returns car b from the low queue.
14	getCar()	Raises an exception since there are no more cars available in any of the three queues.
15	isEmpty()	Returns true since all three queues are empty.