Computational Thinking_ A Beginner’s Guide to Problem-Solving and Programming ( PDFDrive )

COMPUTATIONAL THINKING Nielsen, J. (2012) Usability 101: introduction to usability. Nielsen Norman Group. Available at: www.nngroup.com/articles/usability-101-introduction-to-usability/ [11 November 2016]. OpenStreetMap (2017) OpenStreetMap copyright and license. Open Street Map. Available from: www.openstreetmap.org/copyright [19 June 2017]. O’Reilly, L. (2016) Netflix lifted the lid on how the algorithm that recommends you titles to watch actually works. Business Insider. Available from: www.businessinsider.de/how- the-netflix-recommendation-algorithm-works-2016-2 [19 June 2017]. Pane, J. F. et al. (2001) Studying the language and structure in non-programmer’s solu- tions to programming problems. International Journal of Human-Computer Studies, 54 (2). 237. Papert, S. (1980) Mindstorms: children, computers, and powerful ideas. New York, USA: Basic Books Inc. Pea, R. et al. (1987) The buggy path to the development of programming expertise. Focus on Learning Problems in Mathematics, 9 (1). 5. Petre, M. (2013) 35th International Conference on Software Engineering. San Francisco, CA, USA, 18 May. 722. Pierce, B. C. (2002) Types and programming languages. Massachusetts, MA, USA: MIT Press. Pólya, G. (1973) How to solve it (second edition). Princeton, NJ, USA: Princeton University Press. Python.org (2016) Python.org mercurial repository – List Code. Python. Available from: https://hg.python.org/cpython/file/31342913fb1e/Objects/listobject.c#l139 [16 November 2016]. Python.org (2017) Python 3 documentation. Python. Available from: https://docs.python. org/3/ [19 June 2017]. Scapy (2017) Scapy website. Scapy. Available from: www.secdev.org/projects/scapy/ [19 June 2017]. Selby, C. C. (2013) Computational thinking: the developing definition. Eprints. Available from: https://eprints.soton.ac.uk/356481/ [19 June 2017]. Selic, B. (2003) The pragmatics of model-driven development. IEEE Software, 20 (5). 19. Shalloway, A. and Trott, J. R. (2005) Design patterns explained: a new perspective on object-oriented design 2nd edn. Boston, MA, USA: Addison-Wesley. 282

REFERENCES Tanenbaum, A. (2010) MINIX 3: a modular, self-healing posix-compatible operating system. YouTube. Available from: www.youtube.com/watch?v=bx3KuE7UjGA [19 June 2017]. Tutorials Point (2017). What is system testing? Available from: www.tutorialspoint.com/ software_testing_dictionary/system_testing.htm [3 Jul 2017]. US Air Force (1967) Offutt air force base operator. Wikimedia. Available from: https:// commons.wikimedia.org/wiki/File:Offutt_Air_Force_Base_operator.jpg [19 June 2017]. Voogt, J. et al. (2015) Computational thinking in compulsory education: towards an agenda for research and practice. Education and Information Technologies, 20 (4). 715. Wikimedia Commons (2006) Koenigsberg, map by Merian-Erben 1652. Wikimedia. Available from: https://commons.wikimedia.org/wiki/File:Image-Koenigsberg,_Map_ by_Merian-Erben_1652.jpg [19 June 2017]. Wikimedia Commons (2012) Orrery. Wikimedia. Available from: https://commons.wiki- media.org/wiki/File:Orrery_-_Nov._2010.jpg [19 June 2017]. Wikipedia (2017) Python syntax and semantics. Wikipedia. Available from: https:// en.wikipedia.org/wiki/Python_syntax_and_semantics [19 June 2017]. Wiki Python (2017) Python debugging tools. Wiki Python. Available from: https://wiki. python.org/moin/PythonDebuggingTools [19 June 2017]. Wilkes, M. (1985) Memoirs of a computer pioneer. Massachusetts, MA, USA: MIT Press. Wing, J. (2006) Computational thinking. Communications of the ACM, 49 (3). 33. Wing, J. (2011) Research notebook: computational thinking -- what and why? The Link. Available from: https://www.cs.cmu.edu/link/research-notebook-computational-think- ing-what-and-why [19 June 2017]. Wing, J. (2014) Computational thinking benefits society. Social Issues in Computing. Available from: https://socialissues.cs.toronto.edu/ [1 September 2016]. Yadav, A. et al. (2014) Computational thinking in elementary and secondary teacher education. ACM Transactions on Computing Education, 14 (1). 1–16. 283

INDEX Diagrams and tables are in italics abstraction truth table 21 as models 200 compared to concrete Venn diagram 22 Python 167–75, 207 problem-solving 48 arguments 15–17 Unified Modelling Language context 60–3 assertion methods 212 (UML) 186–7, 233, 234, 235 definition xiv, 58 assignment xiv, 27 climate models 69, 70 examples 9, 58–60, 61–3, associations (UML) 191–3, 198 collaboration 42, 47 232–3 assumptions 48, 80, 86 complexity 40, 95–6 generalisation 57 components (UML) 188 importance of 58, 74 Barr, V. 12 composition instantiation 167, 171–2 Behave 216–17 objects 174–5 layers 60–3, 74 behaviour-driven development Unified Modelling Language programming 162, 164, 167–8, (BDD) 217–18 (UML) 191–3 182 see also object-oriented behavioural patterns 179, 180–1 compound propositions 18, 115 programming behaviours (modelling) 66 comprehensions 133–4 risks 63–4 Beizer, B. 80, 121 computational thinking biconditional statements xiv, definition 7–9, 11, 13 acceptance testing 216–19 19, 24 misunderstandings about accuracy (modelling) 72, 199 ‘Big-O’ 96–7 11–12 actions (modelling) 67, 231 Boolean logic 17–19, 110, 165–6 shortcomings 12 activity diagrams (UML) 196, 236 bottom-up testing 82–3, 210–14 usage examples 9–10 actors (UML) 198 brainstorming 42 computers, precision of 30–1 aggregation (UML) 192 break statement 123–4 concerns 141–5, 154, 159 algorithmic thinking 9, 25–31 breakpoints 224 conditional expressions 120 algorithms bugs see also errors; testing conditionals as abstractions 164 compared to logic 25, 37 debugging 85–8, 90 algorithm use 28–9, 117 complexity classes 95–6 definition 76 bugs 79–80 definition xiv, 25, 26–7, 276n1 mitigation 80–2, 90, 208–9 complex 32–6, 118–19 efficiency 94–7 prevention 77–80, 90, 203–4 definition xiv execution 27–9 testing 82–5, 90 Python 118–20 exhaustiveness 79–80 types 77–80, 204–5 as rule identifier 54 if-then-else 31–2, 120 UML activity diagrams 196 modelling 71 cardinality xiv, 71 conjunction Python 116–24, 137 class diagrams 186–7 definition xiv, 18–19 ambiguity 17–18, 19–20, 77–8 class variables 168–9 truth table 21 AND classes continue statement 121–3 definition xiv, 18–19 correctness 93–4, 104 natural language errors 31 exceptions 207 symbolic logic 20 284

creational patterns 179–80 severity 89–90, 220–1 improvement options 246 critical thinking 47–8, 79 types 77–80, 204–5 modelling 233–7 users 100 pattern recognition 229–32 data attributes 168 Euler, Leonard 67–9 problem definition 227–8 data compression 101–4 evaluation see also testing source code 237–42 data representation (modelling) correctness 93–4, 104 testing 243–6 71 efficiency 94–7, 104 debuggers 88, 222–5 elegance 97–9, 104 IF AND ONLY IF debugging 85–8, 90, 206–7, overview 92 definition 19 219–25 program evaluation 203 logic compared to algorithms declarative programming 131–3 trade-offs 101–4, 105 31–2 decomposition see also pattern usability 99–101, 104, 248 symbolic logic 20 recognition events (modelling) 67 Venn diagram 24 except block 206, 207, 220 home automation system exceptions 117–18, 206–7, 209, if-statements 118–20 example 228–9, 230 225 ignition system example 177–81 principles 43–7, 54–5, 57, 139 exhaustiveness 79–80 image compression 101–4 deductive reasoning xiv, 15–16 expressions (Python) 115–16, immutability see mutability defensive programming 80–1, 137 imperative programming 132, 208, 225 133 definiteness 26 facade pattern 177–9 imperialism 12 Denning, P. 8, 12 factory pattern 179–80 IMPLIES (implication) dependencies (UML) 189–91 fallacies 16 disjunction filter function 133, 136, 137, definition xiv, 19 definition xiv, 19 278n55 symbolic logic 20 truth table 22 finally block 208 truth table 23, 24 dissertation example 45–6, 49 FizzBuzz game 84–5 Venn diagram 24 divide-and-conquer 86 see also float variable type 165–6 importing 151–2, 158 decomposition for-loop 121 inconsistency 78 dot notation 158 formality (modelling) 72 indentation 112, 118 drawing 140 format parameter 222 inductive reasoning xiv, 16–17 Dromey, R. G. 48, 49 function signature xiv, 152 information hiding xv, 156–7, 159 dynamic models 66–7, 184 functional primitives 136–7 inheritance 170–2, 174, 175, dynamic typing 187 functions (Python) 112–13, 190–1 134–7, 144, 151–2, 168, 172–3 initialisers 168–9, 173–4, 177, edges (graphs) 68 Furber, S. 8 179, 180 effectiveness 97–8 instance variables 168, 169, 170 efficacy of computational games, difficulty of definition 7 instantiation 63, 167, 171–2 thinking 12 Gauss, Carl Friedrich 97–8 interactions efficiency 94–7, 100, 104 generalisation 50–5, 57 error reactions 81–2 elegance 97–9, 104 grammar bugs 77–8 modelling 72 elif blocks 119 graph models 68–9 interfaces 155–6, 173 else block 207 guard conditions 195, 196 Interpreter Prompt 110 emails 59–60, 61 intuition 14, 25 empirical testing 93–4 hasattr method 174 iteration 27–8, 43, 80, 117, 120–4 entities (modelling) 65–6, 68, Hemmendinger, David 8, 11–12 186–9, 229 heuristics xiv, 43 Jobs, Steve 98 equivalence classes 84–5 home automation system errors see also bugs; testing example Königsberg bridges 68–9 definition 77 abstraction 232–3 lazy initialisation 177 exceptions 206 decomposition 228–9, 230 learnability 100 logical 78–9 library modules xv, 152, 153 priority 89–90 285

list comprehensions 131, 136, interactions 72 modelling 70 164 precision 72 self 168, 170 load testing 216, 217 purpose 72, 184–5, 199–200 subroutines 54 logging 87, 219–22 static models 66, 184, 186 parentheses 116 logical errors 78–9 usages 67–71, 200–1 pattern categories 179 logical operators modules (Python) 150–7, 160, pattern recognition 50–4, 139, 188 162–4, 175–82, 229–32 natural language errors 31, 33 mutability xv, 126–30, 248 pedantry 30–1 principles 18–19 performance testing 216, 217 propositions 115 negation Pierce, B. C. 162 Python 116, 137 definition xv, 19 pixels xv, 101–4 logical propositions see truth table 22 Pólya, George 39–40, 43 propositions polymorphism 172–4 logical thinking Netflix 62 precedence 33–6, 116, 247 arguments 15–17 Nielsen, Jakob 100, 248 precision 19, 26, 30–1, 72 see Boolean logic 17–19 nodes also ambiguity natural language errors 31, 33 premises principles 15 graphs 68 deductive reasoning 16 symbolic logic 19–24 Unified Modelling Language definition xv, 15 Logo 8 (UML) 189 probability 16–17 loops see also iteration NOT problem-solving see also as abstractions 164 complex conditionals 32–3 decomposition bugs 80 definition xv, 19 collaboration 42 concept 27–8, 52–3 natural language errors 33 computational thinking 11 definition xv symbolic logic 20 concrete instances 48–9 imperative programming 133 truth table 22 creativity 39 Python 120–4 Venn diagram 23 critical thinking 47–8 selection 28–9 Noughts and Crosses example goal definition 40–2 18–19, 29–30 iteration 43 quality 42 machine language 164 object composition 174–5 related problems 49 map function 136–7 object-oriented programming working backwards 49–50 maturity of computational (OOP) 166–75 procedural thinking 8 thinking 12 Occam’s Razor 86, 88 processes (UML) 194–6 memorability 100 operations 51, 186–7 programming see also Python memory (human) 58 optimisation, trade-offs 101–4, abstraction 162, 164, 167–8 method chaining 180–1 105 compared to computational methods (Python) 168–9, 174, OR thinking 11 212, 213–14 declarative compared to model-driven development 200 definition xiv, 19 imperative 131–3 modelling see also Unified symbolic logic 20 dynamic typing 187 Modelling Language truth table 22 object-oriented programming Venn diagram 23 (OOP) 166–75 abstraction 58, 199 order of precedence 33–6, 116, pattern recognition 175–6 accuracy 72, 199 247 properties advantages 200 orreries 69, 70 modelling 66 algorithms 71 pattern recognition 51, dynamic models 66–7, 184 packages 231–2 effective characteristics 199 Python 157–9, 160 propositions examples 67–70, 229–32 Unified Modelling Language compound 18, 115 exceptions 233–7 (UML) 187–8 definition xv formality 72 logical operators 18–19 fundamentals 65–6, 74 parameters general-purpose modelling definition xv, 51 language 185 format 222 loops 53 286

properties 17–18 pattern recognition 52, 54, 232 symbolic logic 19–24, 33–6 Python 115–16 syntax errors 77–8, 94, 204–5 pseudocode 29 safety 81 system testing 214–16, 244–6 Python scepticism 47, 93 abstraction 164, 182 scoping 147–9 tearDown method 211–12 acceptance testing 218–19 scripts xv, 152–3 temporary variable swap 176–7 algorithms 116–24, 137 security testing 217 testing see also bugs; errors; classes 167–75, 207 Selby, Cynthia 8, 9, 12 evaluation comments 113 selection 28–9 comprehensions 133–4 self parameter 168, 170 bottom-up 82–3, 210–14 data types 110–11, 130, 248 semantic errors 205 home automation system debugger 222–5 separation of concerns 144, 154, example 243–6 expressions 115–16, 137 159 purpose 82 functions 112–13, 135–7, 144, sequencing 26, 117–18 system testing 214–16 151–2, 168, 172–3 server/client module 151 test phases 210 home automation system setUp method 213–14 test plans 93, 216, 217 example 237–42 severity (debugging) 89–90, top-down 82–3 Interpreter Prompt 110 220–1 unit tests 83–5, 210–14 logging 220–2 signature see function signature user testing 100–1, 217 methods 174, 212 simplicity 98–9 validation 209–10, 216–19 modules 150–7, 159, 188 simulation see modelling verification 209 operations 111 sink traps 97, 98 top-down testing 82–3 order of precedence 116, 247 skills, transferable 11 tracing 87–8 packages 157–9, 160, 188 smiley face example 48–9, transactions, error reactions 81 pattern recognition 175–82 141–5, 153–5, 163–4 transferable skills 11 scoping 147–9 Socrates 15 transitions (modelling) 67 separation of concerns 141–5, solar system models 65, 69, 70 tree (structure) xv, 44–6 154, 159 solution evaluation see truth tables state 124–31, 137 evaluation AND 21 statements 116, 130–1 solutions, non-obvious 98–9 IF AND ONLY IF 24 system testing 212–14, 244–6 specifications 42, 93, 209, 216, IMPLIES 23 unit tests 211–14, 243–4 217 NOT 22 variable types 165–6 specificity 41 OR 22 stability testing 217 overview 21 quality 42 state truth values xv, 15 try block 206 raise 209 algorithms 26–7, 137 tuples 130, 165–6 ranges 121 modelling 67, 194–6, 234–7 turnstile example 67, 194–6 reasoning xiv, 15–17 see also Python 124–31 types algorithmic thinking; logical state machine diagrams 67, modelling 66 thinking 194–6, 235, 236, 237 Python 165–6, 182 see also recipe analogy 26–7, 30–1, 135 statements classes recursion 44 ordering 130–1 typos 77 reduce function 136, 137 Python definition 116 relationships (modelling) 65–6, static models 66, 184, 186 underground maps 58–9, 66 68, 189–93 Stephenson, C. 12 Unified Modelling Language rendering 142, 144–5 strings 110, 165–6 (UML) reusability 152, 166, 182 structural patterns 179 ‘rubber duck debugging’ 88, student grading example 31–6 entities 186–9 277n39 student records example 71, 72, introduction 185 rules 198–9, 213 processes 194–6 subroutines xv, 52, 53–4, 112 relationships 189–93 modelling 66 switchboard metaphor 155–6 usage 196–8, 200–1 287

unit tests 83–5, 210–14, 243–4 global 146–7, 148–9 IMPLIES 24 unittest library 211, 214 instance 168, 169, 170 NOT 23 usability 99–101, 104, 248 local 148–9 OR 23 use case diagrams 197–9 mutability 126–30, 248 verification 209, 214–16 user input, error reactions 81–2 Python 110, 124–30, 146–7, visualisation see modelling user interfaces 72 165–6, 176–7 Voogt, J. et al. 7, 8 user satisfaction 100 temporary variable swap user scenarios 217–18 176–7 while loop 120–1 user testing 100–1, 217 types 110, 165–6 Wilkes, M. 76 vehicle rental example 61–2, 166, Wing, Jeannette 2–3, 7, 8, 11, 58 validation 209–10, 216–19 167, 168–75, 186–7 workflows (UML) 196, 234–7 variables vending machines 81, 93, 218–19 Venn diagrams Yadav, A. et al. 8 as abstractions 164 AND 22 YouTube 62 class 168–9 IF AND ONLY IF 24 definition 27 288