problem solving process code.org

Pilot - U1L02 - The Problem Solving Process

I am including the slide deck I used to help deliver the lesson

I prepared the lesson as recommended by the plans but very shortly into the lesson I changed gears and modified it because it was clear that I was losing student interest.

Modifications: Students seemed unmotivated by the information because it was something that they were familiar with because it is late in the year)… I decided to instead ask them to compare the model for problem solving being presented with any other system they could find and document.

Students were asked to present an artifact comparing them and create hypothesis of why there were differences between them.

Here is a sample project https://goo.gl/Q2Tq1f

The discussions were very insightful particularly when students were discussing the value of simple models vs. more complete or complex models.

Notes: Even though the lesson did not go well as originally planed I am aware of how important it is and I am sure that when I do it again at the beginning of the year it will run much better.

I am teaching six classes, three seventh grade and three eighth grade. The classes are one hour in length and meet every other day. They have had computer classes every year since first grade, but they have not done any computer science other than “hour of code” type activities. Each student has a computer to use during class. They are keeping journals, grade seven on line, grade eight on paper. I am doing this to see which method gets more meaningful results. I followed this lesson pretty closely using a slide presentation as a guide. User “spear” posted a very helpful slide show on this forum.

I think the lesson went well, but it took longer than I thought. I had the students answer a journal prompt at the beginning. Prompt: We use the term “problem” to refer to lots of different situations. I could say I have a problem for homework, a problem with my brother, and a problem with my car, and all three mean very different things. In your journal, I want you to brainstorm as many different kinds of problems as you can and be ready to share with the class. Next they shared examples and I wrote them on the board and we created categories and placed the problems into the created categories. This led to the idea of having a strategy and the activity guide. We did all activities in the guide and shared some responses. In the next class instead of making posters. I gave each group 8 sticky notes and wrote the four steps on the board. I then asked them to write two strategies for each step and post them in the appropriate place on the board. We read what was written and I consolidated the responses in a document. I will post this in the classroom. Strategies I think this lesson went well. It was straightforward. Students seem to understand the four steps and the importance of having a strategy to solve problems. I think the journal entry helped them brainstorm problem types.

Once again thanks everyone for the awesome feedback and sharing your resources! Its great to see that some people are using the resources others have shared!

I teach at a high school in SLC, Utah. My class is very diverse in that we have multiple languages in the class, English is not the native language of 95% of my students, I have pretty close to 50/50 boy, girl ratio and the class is a good representation of students from the entire school ranging from grades 9-12. Our class period is 90 minutes every other day.

Things that went well: The activity guide did a great job of helping students organize their thoughts with the 4 steps. It also gave students the chance to see that the process can work forwards and backwards.

Things to reflect on: It took some brain storming for students to come up with things they are good at. Perhaps have them think about the prompt the previous day so they can talk with a friend or family member about it.

I was gone the 2nd half of the lesson where the were to find a classmate to solve a problem with, so this part of the activity was a little tricky because the students are new to the course and haven’t built strong relationships yet to feel completely safe sharing what they are/are not good at.

Related Topics

How to Solve Coding Problems with a Simple Four Step Method

I had fifteen minutes left, and I knew I was going to fail.

I had spent two months studying for my first technical interview.

I thought I was prepared, but as the interview came to a close, it hit me: I had no idea how to solve coding problems.

Of all the tutorials I had taken when I was learning to code, not one of them had included an approach to solving coding problems.

I had to find a method for problem-solving—my career as a developer depended on it.

I immediately began researching methods. And I found one. In fact, what I uncovered was an invaluable strategy. It was a time-tested four-step method that was somehow under the radar in the developer ecosystem.

In this article, I’ll go over this four-step problem-solving method that you can use to start confidently solving coding problems.

Solving coding problems is not only part of the developer job interview process—it’s what a developer does all day. After all, writing code is problem-solving.

A method for solving problems

This method is from the book How to Solve It by George Pólya. It originally came out in 1945 and has sold over one million copies.

His problem-solving method has been used and taught by many programmers, from computer science professors (see Udacity’s Intro to CS course taught by professor David Evans) to modern web development teachers like Colt Steele.

Let’s walk through solving a simple coding problem using the four-step problem-solving method. This allows us to see the method in action as we learn it. We'll use JavaScript as our language of choice. Here’s the problem:

Create a function that adds together two numbers and returns that value. There are four steps to the problem-solving method:

• Understand the problem.
• Devise a plan.
• Carry out the plan.

Let’s get started with step one.

Step 1: Understand the problem.

When given a coding problem in an interview, it’s tempting to rush into coding. This is hard to avoid, especially if you have a time limit.

However, try to resist this urge. Make sure you actually understand the problem before you get started with solving it.

Read through the problem. If you’re in an interview, you could read through the problem out loud if that helps you slow down.

As you read through the problem, clarify any part of it you do not understand. If you’re in an interview, you can do this by asking your interviewer questions about the problem description. If you’re on your own, think through and/or Google parts of the question you might not understand.

This first step is vital as we often don’t take the time to fully understand the problem. When you don’t fully understand the problem, you’ll have a much harder time solving it.

To help you better understand the problem, ask yourself:

What are the inputs?

What kinds of inputs will go into this problem? In this example, the inputs are the arguments that our function will take.

Just from reading the problem description so far, we know that the inputs will be numbers. But to be more specific about what the inputs will be, we can ask:

Will the inputs always be just two numbers? What should happen if our function receives as input three numbers?

Here we could ask the interviewer for clarification, or look at the problem description further.

The coding problem might have a note saying, “You should only ever expect two inputs into the function.” If so, you know how to proceed. You can get more specific, as you’ll likely realize that you need to ask more questions on what kinds of inputs you might be receiving.

Will the inputs always be numbers? What should our function do if we receive the inputs “a” and “b”? Clarify whether or not our function will always take in numbers.

Optionally, you could write down possible inputs in a code comment to get a sense of what they’ll look like:

//inputs: 2, 4

What are the outputs?

What will this function return? In this case, the output will be one number that is the result of the two number inputs. Make sure you understand what your outputs will be.

Create some examples.

Once you have a grasp of the problem and know the possible inputs and outputs, you can start working on some concrete examples.

Examples can also be used as sanity checks to test your eventual problem. Most code challenge editors that you’ll work in (whether it’s in an interview or just using a site like Codewars or HackerRank) have examples or test cases already written for you. Even so, writing out your own examples can help you cement your understanding of the problem.

Start with a simple example or two of possible inputs and outputs. Let's return to our addition function.

Let’s call our function “add.”

What’s an example input? Example input might be:

// add(2, 3)

What is the output to this? To write the example output, we can write:

// add(2, 3) ---> 5

This indicates that our function will take in an input of 2 and 3 and return 5 as its output.

Create complex examples.

By walking through more complex examples, you can take the time to look for edge cases you might need to account for.

For example, what should we do if our inputs are strings instead of numbers? What if we have as input two strings, for example, add('a', 'b')?

Your interviewer might possibly tell you to return an error message if there are any inputs that are not numbers. If so, you can add a code comment to handle this case if it helps you remember you need to do this.

Your interviewer might also tell you to assume that your inputs will always be numbers, in which case you don’t need to write any extra code to handle this particular input edge case.

If you don’t have an interviewer and you’re just solving this problem, the problem might say what happens when you enter invalid inputs.

For example, some problems will say, “If there are zero inputs, return undefined.” For cases like this, you can optionally write a comment.

// check if there are no inputs.

// If no inputs, return undefined.

For our purposes, we’ll assume that our inputs will always be numbers. But generally, it’s good to think about edge cases.

Computer science professor Evans says to write what developers call defensive code. Think about what could go wrong and how your code could defend against possible errors.  

Before we move on to step 2, let’s summarize step 1, understand the problem:

-Read through the problem.

-What are the inputs?

-What are the outputs?

Create simple examples, then create more complex ones.

2. Devise a plan for solving the problem.

Next, devise a plan for how you’ll solve the problem. As you devise a plan, write it out in pseudocode.

Pseudocode is a plain language description of the steps in an algorithm. In other words, your pseudocode is your step-by-step plan for how to solve the problem.

Write out the steps you need to take to solve the problem. For a more complicated problem, you’d have more steps. For this problem, you could write:

// Create a sum variable.

Add the first input to the second input using the addition operator .

// Store value of both inputs into sum variable.

// Return as output the sum variable. Now you have your step-by-step plan to solve the problem. For more complex problems, professor Evans notes, “Consider systematically how a human solves the problem.” That is, forget about how your code might solve the problem for a moment, and think about how you would solve it as a human. This can help you see the steps more clearly.

3. Carry out the plan (Solve the problem!)

The next step in the problem-solving strategy is to solve the problem. Using your pseudocode as your guide, write out your actual code.

Professor Evans suggests focusing on a simple, mechanical solution. The easier and simpler your solution is, the more likely you can program it correctly.

Taking our pseudocode, we could now write this:

Professor Evans adds, remember not to prematurely optimize. That is, you might be tempted to start saying, “Wait, I’m doing this and it’s going to be inefficient code!”

First, just get out your simple, mechanical solution.

What if you can’t solve the entire problem? What if there's a part of it you still don't know how to solve?

Colt Steele gives great advice here: If you can’t solve part of the problem, ignore that hard part that’s tripping you up. Instead, focus on everything else that you can start writing.

Temporarily ignore that difficult part of the problem you don’t quite understand and write out the other parts. Once this is done, come back to the harder part.

This allows you to get at least some of the problem finished. And often, you’ll realize how to tackle that harder part of the problem once you come back to it.

Step 4: Look back over what you've done.

Once your solution is working, take the time to reflect on it and figure out how to make improvements. This might be the time you refactor your solution into a more efficient one.

As you look at your work, here are some questions Colt Steele suggests you ask yourself to figure out how you can improve your solution:

• Can you derive the result differently? What other approaches are there that are viable?
• Can you understand it at a glance? Does it make sense?
• Can you use the result or method for some other problem?
• Can you improve the performance of your solution?
• Can you think of other ways to refactor?
• How have other people solved this problem?

One way we might refactor our problem to make our code more concise: removing our variable and using an implicit return:

With step 4, your problem might never feel finished. Even great developers still write code that they later look at and want to change. These are guiding questions that can help you.

If you still have time in an interview, you can go through this step and make your solution better. If you are coding on your own, take the time to go over these steps.

When I’m practicing coding on my own, I almost always look at the solutions out there that are more elegant or effective than what I’ve come up with.

Wrapping Up

In this post, we’ve gone over the four-step problem-solving strategy for solving coding problems.

Let's review them here:

• Step 1: understand the problem.
• Step 2: create a step-by-step plan for how you’ll solve it .
• Step 3: carry out the plan and write the actual code.
• Step 4: look back and possibly refactor your solution if it could be better.

Practicing this problem-solving method has immensely helped me in my technical interviews and in my job as a developer. If you don't feel confident when it comes to solving coding problems, just remember that problem-solving is a skill that anyone can get better at with time and practice.

If you enjoyed this post, join my coding club , where we tackle coding challenges together every Sunday and support each other as we learn new technologies.

If you have feedback or questions on this post, feel free to tweet me @madisonkanna ..

Read more posts .

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

How it works

For Business

Join Mind Tools

Article • 4 min read

The Problem-Solving Process

Looking at the basic problem-solving process to help keep you on the right track.

By the Mind Tools Content Team

Problem-solving is an important part of planning and decision-making. The process has much in common with the decision-making process, and in the case of complex decisions, can form part of the process itself.

We face and solve problems every day, in a variety of guises and of differing complexity. Some, such as the resolution of a serious complaint, require a significant amount of time, thought and investigation. Others, such as a printer running out of paper, are so quickly resolved they barely register as a problem at all.

Despite the everyday occurrence of problems, many people lack confidence when it comes to solving them, and as a result may chose to stay with the status quo rather than tackle the issue. Broken down into steps, however, the problem-solving process is very simple. While there are many tools and techniques available to help us solve problems, the outline process remains the same.

The main stages of problem-solving are outlined below, though not all are required for every problem that needs to be solved.

1. Define the Problem

Clarify the problem before trying to solve it. A common mistake with problem-solving is to react to what the problem appears to be, rather than what it actually is. Write down a simple statement of the problem, and then underline the key words. Be certain there are no hidden assumptions in the key words you have underlined. One way of doing this is to use a synonym to replace the key words. For example, ‘We need to encourage higher productivity ’ might become ‘We need to promote superior output ’ which has a different meaning.

2. Analyze the Problem

Ask yourself, and others, the following questions.

• Where is the problem occurring?
• When is it occurring?
• Why is it happening?

Be careful not to jump to ‘who is causing the problem?’. When stressed and faced with a problem it is all too easy to assign blame. This, however, can cause negative feeling and does not help to solve the problem. As an example, if an employee is underperforming, the root of the problem might lie in a number of areas, such as lack of training, workplace bullying or management style. To assign immediate blame to the employee would not therefore resolve the underlying issue.

Once the answers to the where, when and why have been determined, the following questions should also be asked:

• Where can further information be found?
• Is this information correct, up-to-date and unbiased?
• What does this information mean in terms of the available options?

3. Generate Potential Solutions

When generating potential solutions it can be a good idea to have a mixture of ‘right brain’ and ‘left brain’ thinkers. In other words, some people who think laterally and some who think logically. This provides a balance in terms of generating the widest possible variety of solutions while also being realistic about what can be achieved. There are many tools and techniques which can help produce solutions, including thinking about the problem from a number of different perspectives, and brainstorming, where a team or individual write as many possibilities as they can think of to encourage lateral thinking and generate a broad range of potential solutions.

4. Select Best Solution

When selecting the best solution, consider:

• Is this a long-term solution, or a ‘quick fix’?
• Is the solution achievable in terms of available resources and time?
• Are there any risks associated with the chosen solution?
• Could the solution, in itself, lead to other problems?

This stage in particular demonstrates why problem-solving and decision-making are so closely related.

5. Take Action

In order to implement the chosen solution effectively, consider the following:

• What will the situation look like when the problem is resolved?
• What needs to be done to implement the solution? Are there systems or processes that need to be adjusted?
• What will be the success indicators?
• What are the timescales for the implementation? Does the scale of the problem/implementation require a project plan?
• Who is responsible?

Once the answers to all the above questions are written down, they can form the basis of an action plan.

6. Monitor and Review

One of the most important factors in successful problem-solving is continual observation and feedback. Use the success indicators in the action plan to monitor progress on a regular basis. Is everything as expected? Is everything on schedule? Keep an eye on priorities and timelines to prevent them from slipping.

If the indicators are not being met, or if timescales are slipping, consider what can be done. Was the plan realistic? If so, are sufficient resources being made available? Are these resources targeting the correct part of the plan? Or does the plan need to be amended? Regular review and discussion of the action plan is important so small adjustments can be made on a regular basis to help keep everything on track.

Once all the indicators have been met and the problem has been resolved, consider what steps can now be taken to prevent this type of problem recurring? It may be that the chosen solution already prevents a recurrence, however if an interim or partial solution has been chosen it is important not to lose momentum.

Problems, by their very nature, will not always fit neatly into a structured problem-solving process. This process, therefore, is designed as a framework which can be adapted to individual needs and nature.

Join Mind Tools and get access to exclusive content.

This resource is only available to Mind Tools members.

Already a member? Please Login here

Try Mind Tools for FREE

Get unlimited access to all our career-boosting content and member benefits with our 7-day free trial.

Sign-up to our newsletter

Subscribing to the Mind Tools newsletter will keep you up-to-date with our latest updates and newest resources.

Subscribe now

Business Skills

Personal Development

Leadership and Management

Member Extras

Most Popular

Newest Releases

What Is Gibbs' Reflective Cycle?

Team Briefings

Mind Tools Store

About Mind Tools Content

Discover something new today

Onboarding with steps.

Helping New Employees to Thrive

NEW! Pain Points Podcast - Perfectionism

Why Am I Such a Perfectionist?

How Emotionally Intelligent Are You?

Boosting Your People Skills

Self-Assessment

What's Your Leadership Style?

Learn About the Strengths and Weaknesses of the Way You Like to Lead

Recommended for you

Simplex thinking.

8 Steps for Solving Complex Problems

Business Operations and Process Management

Strategy Tools

Customer Service

Business Ethics and Values

Handling Information and Data

Project Management

Knowledge Management

Self-Development and Goal Setting

Time Management

Presentation Skills

Learning Skills

Career Skills

Communication Skills

Negotiation, Persuasion and Influence

Working With Others

Difficult Conversations

Creativity Tools

Self-Management

Work-Life Balance

Stress Management and Wellbeing

Coaching and Mentoring

Change Management

Team Management

Managing Conflict

Delegation and Empowerment

Performance Management

Leadership Skills

Developing Your Team

Talent Management

Problem Solving

Decision Making

Member Podcast

The Code.org Platform in the Developing of Computational Thinking with Elementary School Students

• Conference paper
• First Online: 09 October 2021
• Cite this conference paper

• Rolando Barradas   ORCID: orcid.org/0000-0001-9399-9981 8 , 9 , 11 ,
• José Alberto Lencastre   ORCID: orcid.org/0000-0002-7884-5957 10 ,
• Salviano Soares   ORCID: orcid.org/0000-0001-5862-5706 8 , 11 &
• António Valente   ORCID: orcid.org/0000-0002-5798-1298 8 , 9  

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1473))

Included in the following conference series:

• International Conference on Computer Supported Education

790 Accesses

1 Citations

1 Altmetric

Computational thinking is the thinking process involved in formulating problems to admit a computational solution. This article describes a study in which the code.org platform was used to develop computational thinking with Elementary school students. After proper introduction and contextualization, we describe the 198 students from 4th grade involved in the study, following the process of collecting and analyzing data from the code.org platform. We conclude with the evaluation carried out by the students. The main conclusion of this study is that code.org is a valid option for developing computational thinking with Elementary school students. Also, a reliable way for students to start solving real-life problems, stimulating the capacity for abstraction through simulated and experienced practice.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Wing, J.M.: Computational thinking. Commun. ACM 49 , 33–35 (2006)

Article   Google Scholar  

Resnick, M.: Point of view: reviving Papert’s dream. Educ. Technol. 52 (4), 42–46 (2012)

Google Scholar  

Brennan, K., Resnick, M.: New frameworks for studying and assessing the development of computational thinking. In: Annual American Educational Research Association Meeting, Vancouver, BC, Canada, pp. 1–25 (2012). https://doi.org/10.1.1.296.6602

Puiu, T.: Your smartphone is millions of times more powerful than all of NASA’s combined computing in 1969. https://www.zmescience.com/research/technology/smartphone-power-compared-to-apollo-432/ . Accessed 21 Feb 2019

Popular Mechanics Website. https://www.popularmechanics.com/technology/a22007431/smallest-computer-world-smaller-than-grain-rice/ . Accessed 01 Aug 2020

BizzCommunity Website. https://www.bizcommunity.com/Article/196/423/195991.html . Accessed 01 Aug 2020

Partnership For 21ST Century Skills: Framework for 21st Century Learning (2009). http://www.p21.org/storage/documents/docs/P21_framework_0816.pdf

Resnick, M., et al.: Scratch: programming for all. Commun. ACM 52 , 60–67 (2009). https://doi.org/10.1145/1592761.1592779

Wing, J.M.: Computational thinking (2007). https://www.cs.cmu.edu/afs/cs/usr/wing/www/Computational_Thinking.pdf . Accessed 01 May 2019

Wing, J.: Computational thinking’s influence on research and education for all. Ital. J. Educ. Technol. 25 (2), 1–12 (2017). https://doi.org/10.17471/2499-4324/922

Cuny, J., Snyder, L., Wing, J.M.: Demystifying computational thinking for non-computer scientists (2010). http://www.cs.cmu.edu/~CompThink/resources/TheLinkWing.pdf

Brennan, K., Chung, M., Hawson, J.: Scratch curriculum guide draft. Nature 341 (6241), 73 (2011)

Jonassen, D.: Learning to Solve Problems. A Handbook for Designing Problem-Solving Learning Environments. Routledge, New York (2011)

Papert, S.: The Children Machine. BasicBooks, New York (1993)

Echeverría, M., Pozo, J.: Aprender a resolver problemas e resolver problemas para aprender. In: Pozo, J. (ed.) A Solução de Problemas: Aprender a Resolver, Resolver Para Aprender. Artmed, Porto Alegre (1998)

Code.org Website. https://Code.org/about . Accessed 05 Apr 2019

Kapp, K.M., Blair, L., Mesch, R.: The Gamification of Learning and Instruction Fieldbook. Wiley, San Francisco (2012)

Barradas, R., Lencastre, J.A.: Gamification e game-based learning: estratégias eficazes para promover a competitividade positiva nos processos de ensino e de aprendizagem. In: Revista Investigar em Educação (Issue Mundo digital e Educação), pp. 11–37. Sociedade Portuguesa de Ciências da Educação, Porto (2017)

Barradas, R., Lencastre, J.A., Soares, S., Valente, A.: Developing computational thinking in early ages: a review of the code.org platform. In: Chad Lane, H., Zvacek, S., Uhomoibhi, J. (eds.) Proceedings of the 12th International Conference on Computer Supported Education (CSEDU2020), vol. 2, pp. 157–168. SCITEPRESS – Science and Technology Publications, Prague (2020)

CS Education Research Group Website. http://csunplugged.org . Accessed 7 Sept 2015

Bell, T., Witten, I.H., Fellows, M.: CS unplugged. University of Canterbury, NZ (2015). http://csunplugged.org/wp-content/uploads/2015/03/CSUnplugged_OS_2015_v3.1.pdf

Jonassen, D.: Learning to Solve Problems - An Instructional Design Guide. Pfeiffer, São Francisco (2004)

Kalelioğlu, F.: A new way of teaching programming skills to K-12 students: code.org. Comput. Hum. Behav. 52 , 200–210 (2015)

Bardin, L.: Análise de conteúdo, p. 70. Edições, Lisboa (1979)

Resnick, M.: Learn to Code, Code to Learn (2013). https://www.edsurge.com/news/2013-05-08-learn-to-Code-Code-to-learn . Accessed 07 Feb 2019

Likert, R.: A technique for the measurement of attitudes. Arch. Psychol. 140 , 1–55 (1932)

Jamieson, S.: Likert scales: how to (ab) use them. Med. Educ. 38 (12), 1217–1218 (2004)

Download references

Acknowledgments

This work was partially financed by the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, through national funds, and co-funded by the FEDER, where applicable.

This work was partially funded by CIEd – Research Centre on Education, project UID/CED/01661/2019, Institute of Education, University of Minho, through national funds of FCT/MCTES-PT.

We would like to thank the Colégio Paulo VI (Gondomar, Portugal) the authorization to carry out this study on its premises, and students of the 4th grade of the school years of 2017/18, 2018/19 and 2019/20 by their collaboration.

Author information

Authors and affiliations.

School of Sciences and Technology, University of Trás-os-Montes and Alto Douro, Quinta de Prados, Vila Real, Portugal

Rolando Barradas, Salviano Soares & António Valente

INESC TEC, Porto, Portugal

Rolando Barradas & António Valente

CIEd - Research Centre On Education, Institute of Education, University of Minho, Campus de Gualtar, Braga, Portugal

José Alberto Lencastre

IEETA, UA Campus, Aveiro, Portugal

Rolando Barradas & Salviano Soares

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Rolando Barradas .

Editor information

Editors and affiliations.

University of Illinois, Urbana-Champaign, IL, USA

H. Chad Lane

University of Denver, Denver, CO, USA

Susan Zvacek

School of Engineering, University of Ulster, Newtownabbey, UK

James Uhomoibhi

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Cite this paper.

Barradas, R., Lencastre, J.A., Soares, S., Valente, A. (2021). The Code.org Platform in the Developing of Computational Thinking with Elementary School Students. In: Lane, H.C., Zvacek, S., Uhomoibhi, J. (eds) Computer Supported Education. CSEDU 2020. Communications in Computer and Information Science, vol 1473. Springer, Cham. https://doi.org/10.1007/978-3-030-86439-2_7

Download citation

DOI : https://doi.org/10.1007/978-3-030-86439-2_7

Published : 09 October 2021

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-86438-5

Online ISBN : 978-3-030-86439-2

eBook Packages : Computer Science Computer Science (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Your browser is not supported. Please upgrade your browser to one of our supported browsers . You can try viewing the page, but expect functionality to be broken.

CS in Algebra curriculum and content is being deprecated. Within the next few months, this lab will no longer be available. Please check out Bootstrap: Algebra instead. Learn More .

Help | Advanced Search

Computer Science > Discrete Mathematics

Title: solving the graph burning problem for large graphs.

Abstract: We propose an exact algorithm for the Graph Burning Problem ($\texttt{GBP}$), an NP-hard optimization problem that models the spread of influence on social networks. Given a graph $G$ with vertex set $V$, the objective is to find a sequence of $k$ vertices in $V$, namely, $v_1, v_2, \dots, v_k$, such that $k$ is minimum and $\bigcup_{i = 1}^{k} \{u\! \in\! V\! : d(u, v_i) \leq k - i\} = V$, where $d(u,v)$ denotes the distance between $u$ and $v$. We formulate the problem as a set covering integer programming model and design a row generation algorithm for the $\texttt{GBP}$. Our method exploits the fact that a very small number of covering constraints is often sufficient for solving the integer model, allowing the corresponding rows to be generated on demand. To date, the most efficient exact algorithm for the $\texttt{GBP}$, denoted here by $\texttt{GDCA}$, is able to obtain optimal solutions for graphs with up to 14,000 vertices within two hours of execution. In comparison, our algorithm finds provably optimal solutions approximately 236 times faster, on average, than $\texttt{GDCA}$. For larger graphs, memory space becomes a limiting factor for $\texttt{GDCA}$. Our algorithm, however, solves real-world instances with almost 200,000 vertices in less than 35 seconds, increasing the size of graphs for which optimal solutions are known by a factor of 14.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .