Computational Thinking for Problem Solving (University of Pennsylvania)

Module 1

1.1 Introduction

Four Pillars of Computation thinking

1.2 Decomposition

• Breaking a complex problem into more manageable sub-problems
• Putting the solutions to the subproblems together gives a solution to the original, complex problem
• Decomposition example: Outline a Paper
• Introduction, Body, Conclusion

1.3 Pattern Recognition

• Finding similarities or shared characteristics within or between problems
• Makes the problem easier to solve since the same solution can be used for each occurrence of the pattern
• Example – All dogs look different but they have similarities. A head, ears, body, legs, and a tail.
• Example 2 – Mulching the Yard – All the beds of flower all need to be cleaned and weeding, bringing mulch, and then laying mulch. The pattern is the shared process even though they all are different looking.
• By finding the basic patterns inherent in things, you can create algorithms that solve many generic problems.
• The same solution can be used for each occurrence of the pattern.

1.4 Data Representation and Abstraction

• Determining what characteristics of the problem are important and filtering out those that are not.
• Use these to create a representation of what we are trying to solve
• Example 1 – Data representation for University Students. You need to gather specific data so that officials can easily pull up relevant information about a student. Important data would be name, billing address, student i.d., on-campus address, phone number, etc. Non-important information would be favorite color, shoe size, food preferences, etc.
• Example 2 – Mulching a garden. Data that might be important for mulching your yard. You’ll need to determine how much mulch you need. You’ll need to get the square footage of each garden bed and how many inches of mulch you want in each. That will determine how much mulch you need to purchase. Secondly, you might want data on the distance of each garden bed from each other to minimize the amount of walking to each one. If minimizing walking isn’t a priority, maybe maximizing satisfaction is and since the project might take multiple days, you would determine which garden bed has the most visibility. Thus, you can assign a satisfaction value on each and operate according to increasing your total satisfaction value.
• Example 3 – An e-commerce company for books. You’ll want data on author list, title, ISBN, publication date, edition, category, ratings, summary, etc. Non-important information would be color of the cover, birthplace of authors, complete contents of the book.
• Summary – In data representation and abstraction, we determine what characteristics of the problem are important and filter out those that are not.
• Use these to create a representation of what we are trying to solve.

1.5 Algorithms

• Step-by-step instructions of how to solve a problem
• Identifies what is to be done (the instructions), and the order in which they should be done.
• Algorithms are the starting point for software development.
• Example – Flowchart for making a cup of tea

• If you want to change the algorithm so that it factors in making different types of tea then you’ll add input from user depicted with a parallelogram.
• The diamond indicates yes or no response.

• Example 2 – Mulching the Yard

• An algorithm is a set of step-by-step instructions of how to solve a problem
• Identifies what is to be done (the instructions), and the order in which they should be done
• Can be described in English, as a flowchart, or by using pseudocode.

1.6 Case Studies