problem solving with data structures and algorithms

• Table of Contents
• Scratch ActiveCode
• Navigation Help
• Help for Instructors
• About Runestone
• Report A Problem
• 1. Introduction
• 2. Analysis
• 3. Basic Data Structures
• 4. Recursion
• 5. Sorting and Searching
• 6. Trees and Tree Algorithms
• 7. Graphs and Graph Algorithms

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College (as remixed by Jeffrey Elkner)

• 1.1. Objectives
• 1.2. Getting Started
• 1.3. What Is Computer Science?
• 1.4. What Is Programming?
• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
• 1.7. Review of Basic Python
• 1.8.1. Built-in Atomic Data Types
• 1.8.2. Built-in Collection Data Types
• 1.9.1. String Formatting
• 1.10. Control Structures
• 1.11. Exception Handling
• 1.12. Defining Functions
• 1.13.1. A Fraction Class
• 1.13.2. Inheritance: Logic Gates and Circuits
• 1.14. Summary
• 1.15. Key Terms
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 2.1. Objectives
• 2.2. What Is Algorithm Analysis?
• 2.3. Big-O Notation
• 2.4.1. Solution 1: Checking Off
• 2.4.2. Solution 2: Sort and Compare
• 2.4.3. Solution 3: Brute Force
• 2.4.4. Solution 4: Count and Compare
• 2.5. Performance of Python Data Structures
• 2.7. Dictionaries
• 2.8. Summary
• 2.9. Key Terms
• 2.10. Discussion Questions
• 2.11. Programming Exercises
• 3.1. Objectives
• 3.2. What Are Linear Structures?
• 3.3. What is a Stack?
• 3.4. The Stack Abstract Data Type
• 3.5. Implementing a Stack in Python
• 3.6. Simple Balanced Parentheses
• 3.7. Balanced Symbols (A General Case)
• 3.8. Converting Decimal Numbers to Binary Numbers
• 3.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 3.9.2. General Infix-to-Postfix Conversion
• 3.9.3. Postfix Evaluation
• 3.10. What Is a Queue?
• 3.11. The Queue Abstract Data Type
• 3.12. Implementing a Queue in Python
• 3.13. Simulation: Hot Potato
• 3.14.1. Main Simulation Steps
• 3.14.2. Python Implementation
• 3.14.3. Discussion
• 3.15. What Is a Deque?
• 3.16. The Deque Abstract Data Type
• 3.17. Implementing a Deque in Python
• 3.18. Palindrome-Checker
• 3.19. Lists
• 3.20. The Unordered List Abstract Data Type
• 3.21.1. The Node Class
• 3.21.2. The Unordered List Class
• 3.22. The Ordered List Abstract Data Type
• 3.23.1. Analysis of Linked Lists
• 3.24. Summary
• 3.25. Key Terms
• 3.26. Discussion Questions
• 3.27. Programming Exercises
• 4.1. Objectives
• 4.2. What Is Recursion?
• 4.3. Calculating the Sum of a List of Numbers
• 4.4. The Three Laws of Recursion
• 4.5. Converting an Integer to a String in Any Base
• 4.6. Stack Frames: Implementing Recursion
• 4.7. Introduction: Visualizing Recursion
• 4.8. Sierpinski Triangle
• 4.9. Complex Recursive Problems
• 4.10. Tower of Hanoi
• 4.11. Exploring a Maze
• 4.12. Dynamic Programming
• 4.13. Summary
• 4.14. Key Terms
• 4.15. Discussion Questions
• 4.16. Glossary
• 4.17. Programming Exercises
• 5.1. Objectives
• 5.2. Searching
• 5.3.1. Analysis of Sequential Search
• 5.4.1. Analysis of Binary Search
• 5.5.1. Hash Functions
• 5.5.2. Collision Resolution
• 5.5.3. Implementing the Map Abstract Data Type
• 5.5.4. Analysis of Hashing
• 5.6. Sorting
• 5.7. The Bubble Sort
• 5.8. The Selection Sort
• 5.9. The Insertion Sort
• 5.10. The Shell Sort
• 5.11. The Merge Sort
• 5.12. The Quick Sort
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Programming Exercises
• 6.1. Objectives
• 6.2. Examples of Trees
• 6.3. Vocabulary and Definitions
• 6.4. List of Lists Representation
• 6.5. Nodes and References
• 6.6. Parse Tree
• 6.7. Tree Traversals
• 6.8. Priority Queues with Binary Heaps
• 6.9. Binary Heap Operations
• 6.10.1. The Structure Property
• 6.10.2. The Heap Order Property
• 6.10.3. Heap Operations
• 6.11. Binary Search Trees
• 6.12. Search Tree Operations
• 6.13. Search Tree Implementation
• 6.14. Search Tree Analysis
• 6.15. Balanced Binary Search Trees
• 6.16. AVL Tree Performance
• 6.17. AVL Tree Implementation
• 6.18. Summary of Map ADT Implementations
• 6.19. Summary
• 6.20. Key Terms
• 6.21. Discussion Questions
• 6.22. Programming Exercises
• 7.1. Objectives
• 7.2. Vocabulary and Definitions
• 7.3. The Graph Abstract Data Type
• 7.4. An Adjacency Matrix
• 7.5. An Adjacency List
• 7.6. Implementation
• 7.7. The Word Ladder Problem
• 7.8. Building the Word Ladder Graph
• 7.9. Implementing Breadth First Search
• 7.10. Breadth First Search Analysis
• 7.11. The Knight’s Tour Problem
• 7.12. Building the Knight’s Tour Graph
• 7.13. Implementing Knight’s Tour
• 7.14. Knight’s Tour Analysis
• 7.15. General Depth First Search
• 7.16. Depth First Search Analysis
• 7.17. Topological Sorting
• 7.18. Strongly Connected Components
• 7.19. Shortest Path Problems
• 7.20. Dijkstra’s Algorithm
• 7.21. Analysis of Dijkstra’s Algorithm
• 7.22. Prim’s Spanning Tree Algorithm
• 7.23. Summary
• 7.24. Key Terms
• 7.25. Discussion Questions
• 7.26. Programming Exercises

Acknowledgements ¶

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables ¶

• Module Index
• Search Page

• Runestone in social media: Follow @iRunestone Our Facebook Page
• Table of Contents
• Assignments
• Peer Instruction (Instructor)
• Peer Instruction (Student)
• Change Course
• Instructor's Page
• Progress Page
• Edit Profile
• Change Password
• Scratch ActiveCode
• Scratch Activecode
• Instructors Guide
• About Runestone
• Report A Problem
• This Chapter
• 1. Introduction' data-toggle="tooltip" >

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.

• 1.1. Objectives
• 1.2. Getting Started
• 1.3. What Is Computer Science?
• 1.4. What Is Programming?
• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
• 1.7. Review of Basic Python
• 1.8.1. Built-in Atomic Data Types
• 1.8.2. Built-in Collection Data Types
• 1.9.1. String Formatting
• 1.10. Control Structures
• 1.11. Exception Handling
• 1.12. Defining Functions
• 1.13.1. A Fraction Class
• 1.13.2. Inheritance: Logic Gates and Circuits
• 1.14. Summary
• 1.15. Key Terms
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 2.1.1. A Basic implementation of the MSDie class
• 2.2. Making your Class Comparable
• 3.1. Objectives
• 3.2. What Is Algorithm Analysis?
• 3.3. Big-O Notation
• 3.4.1. Solution 1: Checking Off
• 3.4.2. Solution 2: Sort and Compare
• 3.4.3. Solution 3: Brute Force
• 3.4.4. Solution 4: Count and Compare
• 3.5. Performance of Python Data Structures
• 3.7. Dictionaries
• 3.8. Summary
• 3.9. Key Terms
• 3.10. Discussion Questions
• 3.11. Programming Exercises
• 4.1. Objectives
• 4.2. What Are Linear Structures?
• 4.3. What is a Stack?
• 4.4. The Stack Abstract Data Type
• 4.5. Implementing a Stack in Python
• 4.6. Simple Balanced Parentheses
• 4.7. Balanced Symbols (A General Case)
• 4.8. Converting Decimal Numbers to Binary Numbers
• 4.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 4.9.2. General Infix-to-Postfix Conversion
• 4.9.3. Postfix Evaluation
• 4.10. What Is a Queue?
• 4.11. The Queue Abstract Data Type
• 4.12. Implementing a Queue in Python
• 4.13. Simulation: Hot Potato
• 4.14.1. Main Simulation Steps
• 4.14.2. Python Implementation
• 4.14.3. Discussion
• 4.15. What Is a Deque?
• 4.16. The Deque Abstract Data Type
• 4.17. Implementing a Deque in Python
• 4.18. Palindrome-Checker
• 4.19. Lists
• 4.20. The Unordered List Abstract Data Type
• 4.21.1. The Node Class
• 4.21.2. The Unordered List Class
• 4.22. The Ordered List Abstract Data Type
• 4.23.1. Analysis of Linked Lists
• 4.24. Summary
• 4.25. Key Terms
• 4.26. Discussion Questions
• 4.27. Programming Exercises
• 5.1. Objectives
• 5.2. What Is Recursion?
• 5.3. Calculating the Sum of a List of Numbers
• 5.4. The Three Laws of Recursion
• 5.5. Converting an Integer to a String in Any Base
• 5.6. Stack Frames: Implementing Recursion
• 5.7. Introduction: Visualizing Recursion
• 5.8. Sierpinski Triangle
• 5.9. Complex Recursive Problems
• 5.10. Tower of Hanoi
• 5.11. Exploring a Maze
• 5.12. Dynamic Programming
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Glossary
• 5.17. Programming Exercises
• 6.1. Objectives
• 6.2. Searching
• 6.3.1. Analysis of Sequential Search
• 6.4.1. Analysis of Binary Search
• 6.5.1. Hash Functions
• 6.5.2. Collision Resolution
• 6.5.3. Implementing the Map Abstract Data Type
• 6.5.4. Analysis of Hashing
• 6.6. Sorting
• 6.7. The Bubble Sort
• 6.8. The Selection Sort
• 6.9. The Insertion Sort
• 6.10. The Shell Sort
• 6.11. The Merge Sort
• 6.12. The Quick Sort
• 6.13. Summary
• 6.14. Key Terms
• 6.15. Discussion Questions
• 6.16. Programming Exercises
• 7.1. Objectives
• 7.2. Examples of Trees
• 7.3. Vocabulary and Definitions
• 7.4. List of Lists Representation
• 7.5. Nodes and References
• 7.6. Parse Tree
• 7.7. Tree Traversals
• 7.8. Priority Queues with Binary Heaps
• 7.9. Binary Heap Operations
• 7.10.1. The Structure Property
• 7.10.2. The Heap Order Property
• 7.10.3. Heap Operations
• 7.11. Binary Search Trees
• 7.12. Search Tree Operations
• 7.13. Search Tree Implementation
• 7.14. Search Tree Analysis
• 7.15. Balanced Binary Search Trees
• 7.16. AVL Tree Performance
• 7.17. AVL Tree Implementation
• 7.18. Summary of Map ADT Implementations
• 7.19. Summary
• 7.20. Key Terms
• 7.21. Discussion Questions
• 7.22. Programming Exercises
• 8.1. Objectives
• 8.2. Vocabulary and Definitions
• 8.3. The Graph Abstract Data Type
• 8.4. An Adjacency Matrix
• 8.5. An Adjacency List
• 8.6. Implementation
• 8.7. The Word Ladder Problem
• 8.8. Building the Word Ladder Graph
• 8.9. Implementing Breadth First Search
• 8.10. Breadth First Search Analysis
• 8.11. The Knight’s Tour Problem
• 8.12. Building the Knight’s Tour Graph
• 8.13. Implementing Knight’s Tour
• 8.14. Knight’s Tour Analysis
• 8.15. General Depth First Search
• 8.16. Depth First Search Analysis
• 8.17. Topological Sorting
• 8.18. Strongly Connected Components
• 8.19. Shortest Path Problems
• 8.20. Dijkstra’s Algorithm
• 8.21. Analysis of Dijkstra’s Algorithm
• 8.22. Prim’s Spanning Tree Algorithm
• 8.23. Summary
• 8.24. Key Terms
• 8.25. Discussion Questions
• 8.26. Programming Exercises

Acknowledgements ¶

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables ¶

Search Page

• Computers & Technology
• Programming

Enjoy fast, free delivery, exclusive deals, and award-winning movies & TV shows with Prime Try Prime and start saving today with fast, free delivery

Amazon Prime includes:

Fast, FREE Delivery is available to Prime members. To join, select "Try Amazon Prime and start saving today with Fast, FREE Delivery" below the Add to Cart button.

• Cardmembers earn 5% Back at Amazon.com with a Prime Credit Card.
• Unlimited Free Two-Day Delivery
• Streaming of thousands of movies and TV shows with limited ads on Prime Video.
• A Kindle book to borrow for free each month - with no due dates
• Listen to over 2 million songs and hundreds of playlists
• Unlimited photo storage with anywhere access

Important:  Your credit card will NOT be charged when you start your free trial or if you cancel during the trial period. If you're happy with Amazon Prime, do nothing. At the end of the free trial, your membership will automatically upgrade to a monthly membership.

Buy new: .savingPriceOverride { color:#CC0C39!important; font-weight: 300!important; } .reinventMobileHeaderPrice { font-weight: 400; } #apex_offerDisplay_mobile_feature_div .reinventPriceSavingsPercentageMargin, #apex_offerDisplay_mobile_feature_div .reinventPricePriceToPayMargin { margin-right: 4px; } -30% $34.91 $ 34 . 91 FREE delivery Thursday, May 9 on orders shipped by Amazon over $35 Ships from: Amazon.com Sold by: Amazon.com

Return this item for free.

Free returns are available for the shipping address you chose. You can return the item for any reason in new and unused condition: no shipping charges

• Go to your orders and start the return
• Select the return method

Save with Used - Very Good .savingPriceOverride { color:#CC0C39!important; font-weight: 300!important; } .reinventMobileHeaderPrice { font-weight: 400; } #apex_offerDisplay_mobile_feature_div .reinventPriceSavingsPercentageMargin, #apex_offerDisplay_mobile_feature_div .reinventPricePriceToPayMargin { margin-right: 4px; } $22.78 $ 22 . 78 FREE delivery Monday, May 13 on orders shipped by Amazon over $35 Ships from: Amazon Sold by: Amazon Warehouse

Download the free Kindle app and start reading Kindle books instantly on your smartphone, tablet, or computer - no Kindle device required .

Read instantly on your browser with Kindle for Web.

Using your mobile phone camera - scan the code below and download the Kindle app.

Image Unavailable

• To view this video download Flash Player

Follow the author

Problem Solving with Algorithms and Data Structures Using Python 2nd Edition 2nd Edition

There is a newer edition of this item:.

Purchase options and add-ons

• ISBN-10 1590282574
• ISBN-13 978-1590282571
• Edition 2nd
• Publisher Franklin, Beedle & Associates
• Publication date August 22, 2011
• Language English
• Dimensions 7.5 x 0.99 x 9.25 inches
• Print length 438 pages
• See all details

Frequently bought together

Similar items that may ship from close to you

Product details

• Publisher ‏ : ‎ Franklin, Beedle & Associates; 2nd edition (August 22, 2011)
• Language ‏ : ‎ English
• Paperback ‏ : ‎ 438 pages
• ISBN-10 ‏ : ‎ 1590282574
• ISBN-13 ‏ : ‎ 978-1590282571
• Item Weight ‏ : ‎ 1.7 pounds
• Dimensions ‏ : ‎ 7.5 x 0.99 x 9.25 inches
• #18 in Data Structure and Algorithms
• #716 in Python Programming
• #757 in Microsoft Programming (Books)

About the author

Bradley n. miller.

Discover more of the author’s books, see similar authors, read author blogs and more

Customer reviews

Customer Reviews, including Product Star Ratings help customers to learn more about the product and decide whether it is the right product for them.

To calculate the overall star rating and percentage breakdown by star, we don’t use a simple average. Instead, our system considers things like how recent a review is and if the reviewer bought the item on Amazon. It also analyzed reviews to verify trustworthiness.

Reviews with images

• Sort reviews by Top reviews Most recent Top reviews

Top reviews from the United States

There was a problem filtering reviews right now. please try again later..

Top reviews from other countries

• Amazon Newsletter
• About Amazon
• Accessibility
• Sustainability
• Press Center
• Investor Relations
• Amazon Devices
• Amazon Science
• Sell on Amazon
• Sell apps on Amazon
• Supply to Amazon
• Protect & Build Your Brand
• Become an Affiliate
• Become a Delivery Driver
• Start a Package Delivery Business
• Advertise Your Products
• Self-Publish with Us
• Become an Amazon Hub Partner
• › See More Ways to Make Money
• Amazon Visa
• Amazon Store Card
• Amazon Secured Card
• Amazon Business Card
• Shop with Points
• Credit Card Marketplace
• Reload Your Balance
• Amazon Currency Converter
• Your Account
• Your Orders
• Shipping Rates & Policies
• Amazon Prime
• Returns & Replacements
• Manage Your Content and Devices
• Recalls and Product Safety Alerts
• Conditions of Use
• Privacy Notice
• Consumer Health Data Privacy Disclosure
• Your Ads Privacy Choices

Data Structures

Arrays - ds easy problem solving (basic) max score: 10 success rate: 93.18%, 2d array - ds easy problem solving (basic) max score: 15 success rate: 93.15%, dynamic array easy problem solving (basic) max score: 15 success rate: 86.85%, left rotation easy problem solving (basic) max score: 20 success rate: 91.31%, sparse arrays medium problem solving (basic) max score: 25 success rate: 97.28%, array manipulation hard problem solving (intermediate) max score: 60 success rate: 61.35%, print the elements of a linked list easy problem solving (basic) max score: 5 success rate: 97.16%, insert a node at the tail of a linked list easy problem solving (intermediate) max score: 5 success rate: 95.27%, insert a node at the head of a linked list easy problem solving (basic) max score: 5 success rate: 98.32%, insert a node at a specific position in a linked list easy problem solving (intermediate) max score: 5 success rate: 96.97%, cookie support is required to access hackerrank.

Seems like cookies are disabled on this browser, please enable them to open this website

OpenDSA Data Structures and Algorithms Modules Collection

Chapter 21 senior algorithms course.

Show Source |    | About    «   21. 1. Data and Algorithm Analysis   ::   Contents   ::   21. 3. Semester Overview   »

21. 2. An Introduction to Problem Solving ¶

21. 2.1. an introduction to problem solving ¶.

This document presents a brief overview of selected material from four textbooks (see [FL95, Lev94, WL99, Zei07] in the bibliography). Reading any of these books should help you to become a better problem solver.

To successfully solve any problem, the most important issue to get actively involved. Levine [Lev94] calls this “The Principle of Intimate Engagement”. Writers on problem solving often use terms like “roll up your sleeves” and “get your hands dirty”. It means actively engaging with the problem, and doing some work to get it done. For easier problems, you will “see” an answer fairly quickly once you actively engage, and the issue then is to work through to completion. For most problems, the ones matter most, you won’t “see” an answer right away. For these problems, you will have to use various strategies to come up with a potential solution for even getting started.

Problem solvers can be categorized as either “engagers” or “dismissers”. Engagers typically have a history of success with problem solving. Dismissers have a history of failure. Of course, you might be an engager for one type of problem, and a dismisser for another. Many students do significant problem solving for recreation—Sodoku puzzles, computer games with meaningful problem solving tasks, and all sorts of “puzzles”. They might spend hours engaged with “interesting” problems. Yet, these same students might dismiss math and analytical computer science problems due to a historical lack of success. If you have this problem, then to be successful in life you will need to find ways to get over what is obviously a mental block. You need to learn to transfer successful problem-solving strategies from one part of your life to other parts.

Levine uses examples of trying to repair a clothes dryer or a wobbly table. How to solve the problem might not be immediately obvious. The first step is to take the effort to look at the problem. In this example, it starts by opening the back of the dryer, or looking under the table. This initial investigation can often lead to a solution. It is a matter of adopting the mental attitude of being willing to take the risk and the effort. Then it is a matter of working with the problem for awhile to see what can be done. At that point, a possible solution path might open up. But nothing can be solved unless you are willing to take the time and make the effort. All of the heuristics for solving problems start with that.

Fogler and LeBlanc [FL95] discuss the differences between effective and ineffective problem solvers.

The most important factors that distinguish between ineffective and effective problem solvers are the attitudes with which they approach the problem, their aggressiveness in the problem-solving process, their concern for accuracy, and the solution procedures they use. For example, effective problem solvers believe that problems can be solved through the use of heuristics and careful persistent analysis, while ineffective problem solvers think, “You either know it or you don’t”. Effective problem solvers become very active in the problem-solving process: They draw figures, make sketches, and ask questions of themselves and others. Ineffective problem solvers don’t seem to understand the level of personal effort needed to solve the problem. Effective problem solvers take great care to understand all the facts and relationships accurately. Ineffective problem solvers make judgments without checking for accuracy… By approaching a situation using the characteristic attitudes and actions of an effective problem solver, you will be well on your way to finding the real problem and generating an outstanding solution.

21. 2.1.1. Investigation and Argument ¶

Problem solving has two parts [Zei07]: the investigation and the argument. Students are too used to seeing only the argument in their textbooks and lectures. Unfortunately, to be successful in school (and in life after school), one needs to be good at both, and to understand the differences between these two phases of the process. To solve the problem, you must investigate successfully. Then, to give the answer to your client (solution on homework or exam, or report to boss), you need to be able to make the argument in a way that gets the solution across clearly and succinctly. The argument phase involves good technical writing skills—the ability to make a clear, logical argument. Understanding standard proof techniques can help you. The three most-used proof techniques are deduction (direct proof), contradiction, and induction.

21. 2.1.2. Heuristics for Problem Solving “In the Small” ¶

Write it down After motivation and mental attitude, the most important limitation on your ability to solve problems is biological: While you have lots of storage capacity, your “working memory” is tiny. For active manipulation, you can only store \(7\pm 2\) pieces of information. You can’t change this biological fact. All you can do is take advantage of your environment to get around it. That means, you must put things into your environment to manipulate them. Most often, that translates to writing things down, and doing it in a way that lets you manipulate aspects of the problem (correct representation).

Look for special features Examples include cryptogram addition problems. You might recognize that something on one end must be a 1, in other circumstances one of the numbers must be a zero. Consider the following cryptogram puzzle where you must replace the letters with numbers to make a legal addition problem. In this case, we should recognize two special features: (1) The leading digit of the answer must be a one, and (2) One of the right most digits must be a zero. Recognizing these special features puts us well on the way to solving the full problem.

Go to the extremes Study boundary conditions of the problem. For lots of problems, it helps to start with the small cases, which are one form of boundary condition.

Simplify A version of going to extremes is to simplify the problem. This might give a partial solution that can be extended to the original problem.

Penultimate step What precondition must take place before the final solution step is possible? If you recognize this, then getting to the penultimate step leads to the final solution, and solving the penultimate problem might be easier. Towers of Hanoi gives an excellent example of finding a solution from looking at the penultimate step.

Lateral thinking Be careful about being lead into a blind alley. Using an inappropriate problem-solving strategy might blind you to the solution.

Get your hands dirty Sometimes you need to just “play around” with the problem to get some initial insight. For example, when trying to see the closed form solution to a summation, its often a good place to start writing the first few sums down.

Wishful thinking A version of simplifying the problem. Sometimes you can transform the problem into something easy, or see how to get the start position to something that you could “wish” was the solution. That might be a smaller step to the actual solution.

Symmetry Look for symmetries in the problem. They might give clues to the solution.

21. 2.1.3. Problem Solving “In the Large” ¶

There are lots of standard techniques for solving larger and messier “real-world” problems (the type of problems often encountered by engineers in their professional lives). Fogler and LeBlanc [FL95] discuss such techniques in detail. Here is a brief outline of an overall process for disciplined problem solving of “real world” problems.

Problem Definition The client for a problem will often not state it in the correct way. Your first step toward solution is often to define the “real” problem that needs to be solved. It might not be obvious what this is. To get at the “real” problem, you will need to begin by studying it, collecting information about it, and talking to people familiar with the problem. You might consider restating the problem in a number of ways. Define the desired state. Then make restatements of the current problem formulation that can trigger new insights. Consider looking at the problem statement by making the opposite statement. Alternatively, perhaps we can change the surrounding situation such that the current problem can be “made OK” rather than solved directly.

Generate solutions Once you have settled on a problem statement, you need to generate and analyze a range of possible solutions. Blockbusting and brainstorming techniques can generate a list of possible solutions to study.

Decide the Course of Action There are a number of standard techniques for select from a given list of potential actions (e.g., situation analysis, Pareto analysis, K.T. Problem analysis, decision analysis).

Implement the Solution Getting approval may be the necessary first step to implementation. Once that is taken care of, again there are a number of standard techniques for planning implementations (e.g., Gannt charts, critical path analysis).

Evaluation Evaluation should be built into all phases of the problem solving process.

21. 2.1.4. Pairs Problem Solving ¶

Whimbey & Lochhead [WL99] discuss a technique for pair problem solving that separates the pair into a solver and a listener. The listener plays an active role, being responsible for keeping the problem solver on track and requiring the problem solver to vocalize their process. The listener is actively checking for errors by the problem solver. See the handout for more details on this.

21. 2.1.5. Errors in Reasoning ¶

Again from Whimbey & Lochhead [WL99] comes a description of how people go wrong in problem solving. Specifically related to homework and tests, typical problems stem from failing to read the problem carefully. Thus, students will often fail to use all relevant facts, or plain mis-interpret the problem. Other typical mistakes come from failing to be systematic, or worse yet being just plain careless. All of this indicates that many of the points lost by students on tests and homeworks are not caused by “not knowing the material”, but rather are caused by not executing problem solving effectively. Those are points that don’t need to be lost.

Comprehension in reading is a major factor to success. Proper comprehension of technical material requires careful reading, and often re-reading. There is no such thing as speed reading with comprehension. The mythology of the speed reading advocates, such as “read in thought groups”, “skim for concepts”, and “don’t re-read”, are all ineffective.

21. 2.1.6. References ¶

[FL95] H. Scott Fogler and Steven E. LeBlanc. Strategies for Creative Problem Solving. Prentice Hall, 1995.

[Lev94] Marvin Levine. Effective Problem Solving. Prentice Hall, second edition, 1994.

[WL99] Arthur Whimbey and Jack Lochhead. Problem Solving & Comprehension. Lawrence Erlbaum Associates, sixth edition, 1999.

[Zei07] Paul Zeitz. The Art and Craft of Problem Solving. John Wiley & Sons, second edition, 2007.

Contact Us | | Privacy | | License    «   21. 1. Data and Algorithm Analysis   ::   Contents   ::   21. 3. Semester Overview   »

Contact Us | | Report a bug

Problem Solving with Algorithms and Data Structures

by Brad Miller, David Ranum

Subscribe to new books via dBooks.org telegram channel

Book description.

This open book is licensed under a Creative Commons License (CC BY). You can download Problem Solving with Algorithms and Data Structures ebook for free in PDF format (4.9 MB).

Table of Contents

Book details.

Book Hashtags

Related books.

Learn Data Structures and Algorithms in 48 Hours

In the realm of software development, mastering Data Structures and Algorithms could be a critical step towards securing your dream job.

We just posted a course on the freeCodeCamp.org YouTube channel that will equip you with the knowledge to excel in coding interviews and problem-solving. You will learn the important data structures and algorithms you need to know to  develop efficient code. Dinesh Varyani created this course. He is an expereinced cloud engineer at Google.

Course Overview

The course is designed to cover the breadth and depth of topics necessary for placement preparations, coding interviews, and enhancing logical thinking capabilities. With a focus on real-world applications, the course ensures learners are not just memorizing code but truly understanding the principles behind the solutions. It walks you through various Java algorithms and data structure problems, accompanied by step-by-step visualizations to foster genuine learning.

Java, known for its versatility and widespread use, is the primary language used in this course. However, students with backgrounds in other programming languages like Javascript, Python, C#, C++, or C can also easily grasp the concepts taught. The course uniquely utilizes animated slides to demonstrate the implementation of various algorithms and data structures, making complex topics accessible and engaging.

What You Will Learn

This comprehensive course covers a wide array of topics to prepare you for technical interviews and software development challenges, including:

• Algorithm Analysis : Understanding the efficiency and scalability of algorithms.
• Data Structures : Diving into arrays, matrices, linked lists (singly, doubly, and circular), stacks, queues, binary trees, binary search trees, graphs, priority queues, heaps, and the Trie data structure.
• Core Concepts : Exploring recursion, searching, sorting, strings, and dynamic programming.

Each section is crafted to address common interview questions and scenarios, ensuring learners are well-prepared for the questions they might face in an actual interview setting.

Why Choose This Course?

• Real-World Problem Solving : Learn how to approach and solve complex problems with optimal solutions.
• Visual Learning : Animated slides and step-by-step visualizations make learning interactive and effective.
• Comprehensive Coverage : From basic to advanced topics, this course has everything covered.
• Language Versatility : While Java is used, concepts are applicable across various programming languages.
• Interview Preparation : Specifically designed to tackle the most common interview challenges in the IT industry.

Whether you're aiming to land a software engineering job or simply wish to deepen your understanding of data structures and algorithms, this course is for you. Watch the full course on the freeCodeCamp.org YouTube channel (48-hour watch).

I'm a teacher and developer with freeCodeCamp.org. I run the freeCodeCamp.org YouTube channel.

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

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching
• 30 OOPs Interview Questions and Answers (2024)
• C++ Interview Questions and Answers (2024)
• Top 100 C++ Coding Interview Questions and Answers (2024)
• Top 50+ Python Interview Questions and Answers (Latest 2024)
• Java Interview Questions and Answers
• Java Collections Interview Questions and Answers
• Top 20 Java Multithreading Interview Questions & Answers
• Top 100 Data Structure and Algorithms DSA Interview Questions Topic-wise
• Top 50 Array Coding Problems for Interviews

Most Asked Problems in Data Structures and Algorithms | Beginner DSA Sheet

• Top 10 Algorithms in Interview Questions
• Machine Learning Interview Questions
• Top 50 Problems on Linked List Data Structure asked in SDE Interviews
• Top 50 Problems on Heap Data Structure asked in SDE Interviews
• Data Analyst Interview Questions and Answers
• SQL Query Interview Questions
• Top Linux Interview Questions With Answer
• MySQL Interview Questions
• Top 50 Django Interview Questions and Answers
• Top 50 Networking Interview Questions (2024)
• Software Testing Interview Questions

In this Beginner DSA Sheet for Data Structures and Algorithms, we have curated a selective list of problems for you to solve as a beginner for DSA. After learning the fundamentals of programming, choosing a programming language, and learning about Data Structure and Algorithms and their space-time complexity, it becomes necessary to practice the problem based on different data structures and algorithms. 

DSA Interview problems

The problem on the sheet includes:

Linked List:

Dynamic programming:, please login to comment..., similar reads.

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

EnjoyMathematics

Steps of Problem Solving in Data Structures and Algorithms

Every solution starts with a strategy, and an algorithm is a strategy for solving a coding problem. So, we must learn to design an efficient algorithm and translate this 'algorithm' into the correct code to get the job done.

But there are many coding problems available in data structures and algorithms, and most of the time, these problems are new to us. So as programmers, we need to develop ourselves as confident problem-solvers who are not intimidated by the difficulty of the given problem. 

Our long-term goal should be simple: Learn to design correct and efficient code within a given time. As we practice more and more, we will gain experience in problem-solving, and our work will become easier. Here are some essential skills that we should practice for every DSA problem:

• Developing an approach to understanding the problem
• Thinking of a correct basic solution
• Designing step-by-step pseudocode solutions
• Analyzing the efficiency of a solution
• Optimizing the solution further
• Transforming pseudocode into correct code

Now, the critical question would be: Is there a well-defined, guided strategy to approach and solve a coding problem? If yes, then what are the critical steps? Let's think and explore!

Step 1: Understanding the problem

Solving a problem requires a clear understanding of the problem. Unfortunately, sometimes we read only the first few lines and assume the rest of the problem or ignore this step because we have seen something similar in the past. We should view these as unfair practices and develop a clear approach to understanding problems.

During problem-solving, every small detail can help us design an efficient solution. Sometimes, a small change in the question can alter the solution approach. Taking extra time to understand the problem will give us more confidence later on. The fact is, we never want to realize halfway through that we misunderstood the problem.

It doesn't matter if we have encountered a question before or not; we should read the question several times. So, take a paper and write down everything while going through the problem. Exploring some examples will also help us clarify how many cases our algorithm can handle and the possible input-output patterns. We should also explore scenarios for large input, edge cases, and invalid input.

Sometimes, it is common for problem descriptions to suffer from these types of deficiencies:

• The problem description may rely on undefined assumptions
• The problem description may be ambiguous or incomplete
• The problem description may have various contradictions.

These deficiencies may be due to the abstract explanation of the problem description in our natural languages. So, it is our responsibility to identify such deficiencies and work with the interviewer or problem provider to clarify them. We should start by seeking answers to the following questions:

• What are the inputs and outputs?
• What type of data is available?
• What is the size or scale of the input?
• How is the data stored? What is the data structure?
• Are there any special conditions or orders in the data?
• What rules exist for working with the data?

Step 2: Thinking of a correct basic solution

The best approach would be to think of a correct solution that comes immediately to our mind. It does not matter even if it is an inefficient approach. Having a correct and inefficient answer is much better than an incorrect solution or significant delay in finding the solution. This could help us in so many ways:

• Help us to build good confidence or motivation at the start.
• Provide an excellent point to start a conversation with the interviewer.
• Sometimes, it provides a hint to improve efficiency by reducing some loops, removing some intermediate steps, or performing some operations efficiently.

Here are some examples of brute force patterns: three nested loops, two nested loops, solution using extra memory, solution using sorting, double traversal in the binary tree, considering all sub-arrays or substrings, exhaustive search, etc.

After thinking and communicating the brute force idea, the interviewer may ask for its time and space complexity. We need to work on paper, analyze each critical operation, and write it in the form of Big-O notation. Clear conceptual idea of time and space complexity analysis is essential at this stage.

Step 3: Designing efficient solution with pseudocode

This is a stage to use the best experience of DSA problem-solving and apply various problem-solving strategies . One practical truth is: moving from a basic algorithm to the most efficient algorithm is a little difficult in a single step. Each time, we need to optimize the previous algorithm and stop when there is no further optimization possible. Revisiting the problem description and looking for some additional information can help a lot in further optimization. For example:

• If the input array is sorted or nearly sorted, we can apply optimized algorithms such as a single loop, two-pointer approach, or binary search.
• If we need to find a subarray of size k, we can use the sliding window technique, which involves maintaining a window of size k over the array and sliding it over the elements to find the desired subarray.
• When searching is a critical operation, we can use optimized search algorithms or data structures like binary search, BST, or hash table.
• For optimization problems, we can consider divide and conquer, dynamic programming, or greedy algorithm approaches.
• If we need to find a solution with a given constraint, we can use backtracking.
• When working with string data, direct address tables, hash tables, or trie data structures can be useful.
• To frequently access and process max or min elements, we can use a priority queue or heap data structure.
• For dictionary operations such as insert, search, and delete, we can use hash tables or BST.
• If we need to perform both dictionary and priority queue operations, a BST may be useful.
• For range query operations such as range max, range min, or range sum, we can use data structures like segment trees or Fenwick trees.
• To process binary tree data level by level, BFS or level-order traversal can be used.

The idea would be simple: we should learn the use case of efficient problem-solving patterns on various data structures. Continuously thinking, analyzing, and looking for a better solution is the core idea. 

Here are some best examples of problems where several levels of optimisations are feasible. Practicing such types of coding questions helps a lot in building confidence.

Find equilibrium index of an array

• Using nested loops: Time = O(n²), Memory = O(1)
• Using prefix sum array: Time = O(n), Memory = O(n)
• Using single scan: Time = O(n), Memory = O(1)

Trapping rain water

• Using Dynamic Programming: Time = O(n), Memory = O(n)
• Using Stack: Time = O(n), Memory = O(n)
• Using two pointers: Time = O(n), Memory = O(1)

Check for pair with a given sum

• Using sorting and binary search: Time = O(nlogn), Memory = O(1)
• Using sorting and Two Pointers: Time = O(nlogn), Memory = O(1)
• Using a Hash Table: Time = O(n), Memory = O(n)

Find the majority element in an array

• Using two nested loops: Time = O(n²), Memory = O(1)
• Using Sorting: Time = O(nlogn), Memory = O(1)
• Using the divide and conquer: Time = O(nlogn), Memory = O(logn)
• Using Bit Manipulation: Time = O(n), Memory = O(1)
• Using Randomisation: Time = O(nlogn), Memory = O(1) Note: If value of n is very large.
• Boyer-Moore Voting Algorithm: Time = O(n), Memory = O(1)

Maximum Subarray Sum

• Using three nested loops: Time = O(n^3), Memory = O(1)
• Using two nested loops: Time = O(n^2), Memory = O(1)
• Using divide and conquer: Time = O(nlogn), Memory = O(logn)
• Using dynamic programming: Time = O(n), Memory = O(n)
• Kadane algorithm: Time = O(n), Memory = O(1)

Before you jump into the end-to-end code implementation, it’s good practice to write pseudocode on paper. It would be helpful in defining code structure and critical operations. Some programmers skip this step, but writing the final code becomes easier when we have well-designed pseudocode.

Step 4: Transforming pseudocode into a clean, correct, and optimized code

Finally, we need to replace each line of pseudocode with actual code in our favorite programming languages like C++, Java, Python, C#, JavaScript, etc. Never forget to test actual code with sample test data and check if the actual output is equal to the expected output. When writing code in your interviews, discuss sample data or test cases with the interviewer.

Simplifying and optimizing the code may require a few iterations of observation. We need to ask these questions once we are done writing the code: 

• Does this code run for every possible input, including the edge cases?
• Can we optimize the code further? Can we remove some variables or loop or some extra space?
• Are we repeating some steps a lot? Can we define it separately using another function?
• Is the code readable or written with a good coding style?

Enjoy learning, Enjoy coding, Enjoy algorithms!

Share Your Insights

Don’t fill this out if you’re human:

More from EnjoyAlgorithms

Self-paced courses and blogs, coding interview, machine learning, system design, oop concepts, our newsletter.

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

1.1: Activity 1 - Introduction to Algorithms and Problem Solving

• Last updated
• Save as PDF
• Page ID 48194

Introduction

In this learning activity section, the learner will be introduced to algorithms and how to write algorithms to solve tasks faced by learners or everyday problems. Examples of the algorithm are also provided with a specific application to everyday problems that the learner is familiar with. The learners will particularly learn what is an algorithm, the process of developing a solution for a given task, and finally examples of application of the algorithms are given.

An algorithm is a finite sequence of steps for accomplishing some computational task. It must

• Have steps that are simple and definite enough to be done by a computer, and
• Terminate after finitely many steps.

An algorithm can be considered as a computational procedure that consists of a set of instructions, that takes some value or set of values, as input, and produces some value or set of values, as output, as illustrated in Figure 1.3.1 . It can also be described as a procedure that accepts data, manipulate them following the prescribed steps, so as to eventually fill the required unknown with the desired value(s). The concept of an algorithm is best illustrated by the example of a recipe, although many algorithms are much more complex; algorithms often have steps that repeat (iterate) or require decisions (such as logic or comparison) until the task is completed. Correctly performing an algorithm will not solve a problem if the algorithm is flawed or not appropriate to the problem. A recipe is a set of instructions that show how to prepare or make something, especially a culinary dish.

Different algorithms may complete the same task with a different set of instructions in more or less time, space, or effort than others. Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform (in what specific order) in order to carry out a specified task.

Algorithmic problem solving comes in two phases. These include:

• derivation of an algorithm that solves the problem, and
• conversion of the algorithm into code.

It is worth noting that:

• an algorithm is a sequence of steps, not a program.
• same algorithm can be used in different programs, or the same algorithm can be expressed in different languages, because an algorithm is an entity that is abstracted from implementation details.

An algorithm can be expressed in the following ways:

• human language
• pseudo code

Example \(\PageIndex{1}\)

Problem: Given a list of positive numbers, return the largest number on the list.

Inputs: A list L of positive numbers. This list must contain at least one number.

Outputs: A number n, which will be the largest number of the list.

• Set max to 0.
• For each number x in the list L, compare it to max. If x is larger, set max to x.
• max is now set to the largest number in the list.

The learner was introduced to the concept of algorithms and the various ways he/she can develop a solution to a task. In particular, the learner was introduced to the definition/s of an algorithm, the three main ways of developing or expressing an algorithm which are the human language, Pseudo code and the flow chart. An example was also given to reinforce the concept of the algorithm.

• Outline the algorithmic steps that can be used to add two given numbers.
• By using an example, describe how the concept of algorithms can be well presented to a group of students being introduced to it.

• Even more »

Account Options

• Try the new Google Books
• Advanced Book Search
• Barnes&Noble.com
• Books-A-Million
• Find in a library
• All sellers  »

Get Textbooks on Google Play

Rent and save from the world's largest eBookstore. Read, highlight, and take notes, across web, tablet, and phone.

Go to Google Play Now »

Other editions - View all

Bibliographic information.