Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.
For the best experience please use the latest Chrome, Safari or Firefox browser.
Computational Thinking
Russ Feldhausen
russfeld@ksu.edu
My Story
- B.S. CS 2008; M.S. CS 2018
- Ph.D. CS someday
- 7 years computer support for KSRE
- 9 semesters teaching @ K-State CS
Intro CS, Sysadmin, Problem Solving
- not an expert in education, but an experienced teacher of CS and CT
My Research
- STEM Outreach to Middle Schools
- Pre-service Teacher Training
- Teaching HPC to Young Students
- Introducing CS at all Ages
- Computational Thinking
What is Computational Thinking?
“Computational thinking is a fundamental skill for everyone, not just for computer scientists. To reading, writing, and arithmetic, we should add computational thinking to every child’s analytical ability.”
Jeannette M. Wing (2006)
Carnegie Mellon University
Jeannette M. Wing. Computational Thinking. Commun. ACM, 49(3):33-35, March 2006. ISSN 0001-0782. doi: 10:1145/1118178:1118215. URL http://doi:acm:org/ 10:1145/1118178:1118215.
“Computational thinking is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processing agent”
Jeannette M. Wing (2011)
Carnegie Mellon University
Jeannette M. Wing. Research notebook: Computational thinking - What and why? The Link Magazine, 2011. URL http://www:cs:cmu:edu/link/research-notebook-computational-thinking-what-and-why. [Online; accessed 21 July 2017]
Computational Thinking Concepts
- Algorithmic Thinking - sequence of steps that complete a task. Operators and expressions are also included
- Abstraction - generalized representation of a complex problem, ignoring extraneous information
- Problem Decomposition - breaking a problem into smaller, more manageable parts that can be solved independently of each other
- Data - collection, representation, and analysis of data
- Parallelization - simultaneous processing of a task
Joshua Levi Weese and Russell Feldhausen. STEM Outreach: Assessing Computational Thinking and Problem Solving. In 2017 ASEE Annual Conference & Exposition, Columbus, Ohio, June 2017. ASEE Conferences. URL https://peer:asee:org/28845.
Computational Thinking Concepts
- Control Flow - directs an algorithm's steps when to complete
- Incremental and Iterative - building small parts of the program at each step instead of the whole program at once
- Testing and Debugging - performing intermediate testing and fi xing problems while developing
- Questioning - working to understand each part of the code instead of using code that is not understood well
- Reuse and Remix - making use of other people's work and resources to solve a problem
Joshua Levi Weese and Russell Feldhausen. STEM Outreach: Assessing Computational Thinking and Problem Solving. In 2017 ASEE Annual Conference & Exposition, Columbus, Ohio, June 2017. ASEE Conferences. URL https://peer:asee:org/28845.
Computational thinking is not:
- programming
- problem solving
- mathematics
- engineering
- learned through memorization
- learned by satisfying requirements
Theory: Cognitive Apprenticeship
- Piaget: Constructivism & Papert: Constructionism
- Brown & Collins: Situated Cognition (framing), Cognitive Apprenticeship
- Observe a master at work, talking through thought processes
- Student performs scaffolded activities of increasing difficulty
- Master asks questions and corrects errors to direct learning
Algorithm
A finite list of specific instructions for carrying out a procedure or solving a problem
Euclid's Algorithm (GCD)
- Start with 2 numbers, A and B
- If either one is zero, the answer is the other number
- Subtract the smaller number from the larger number
- Repeat steps 2 - 4 until an answer is found
Example: GCD of 1071 & 462
Example: GCD of 1071 & 462
- 1071, 462
- 609, 462
- 147, 462
- 147, 315
- 147, 168
- 147, 21
- 126, 21
- 105, 21
- 84, 21
- 63, 21
- 42, 21
- 21, 21
- 21, 0
- 21
Sorting Algorithms
- Insertion Sort
- Bubble Sort
- Merge Sort
- Quicksort
Insertion Sort
Image Source: Wikipedia
- Choose an element from the source
- Place it in the correct place in the destination
- Repeat until source is emtpy
Bubble Sort
Image Source: Wikipedia
- Compare the first two elements
- If they are out order, swap them
- Move one element over and repeat
- When the end is reached, start over
- Continue until no more swaps are made
Big O Notation
- A way to express the complexity of an algorithm
- Approximates the number of steps needed based on the size of the input
- Assumes the input is a "worst case" input
Bubble Sort - Worst Case?
- 3, 2, 5, 4, 7, 6, 9, 8, J, 10, K, Q, A
- A, 2, K, 3, Q, 4, J, 5, 10, 6, 9, 7, 8
- A, Q, K, 10, J, 8, 9, 6, 7, 4, 5, 3, 2
- A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2
- 2, 4, 6, 8, 10, Q, A, 3, 5, 7, 9, J, K
Bubble Sort - Worst Case?
- 3, 2, 5, 4, 7, 6, 9, 8, J, 10, K, Q, A - 6
- A, 2, K, 3, Q, 4, J, 5, 10, 6, 9, 7, 8 - 42
- A, Q, K, 10, J, 8, 9, 6, 7, 4, 5, 3, 2 - 73
- A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2 - 78
- 2, 4, 6, 8, 10, Q, A, 3, 5, 7, 9, J, K - 21
Bubble Sort - Worst Case?
Sorting Algorithms
- Insertion Sort - O(n2)
- Bubble Sort - O(n2)
- Merge Sort
- Quicksort
Merge Sort
- Split the items into two halves
- Repeat step 1 until each has 1 item
- Choose 2 parts and merge them together by choosing the smallest item repeatedly from the front of each part
- Continue merging parts together until no more remain
Quicksort
- Choose an item from the list as a "pivot"
- Put all items less than that item to its left, and put all items greater to its right
- Repeat these steps for the items on each side of the pivot.
Sorting Algorithms
- Insertion Sort - O(n2)
- Bubble Sort - O(n2)
- Merge Sort - O(n log n)
- Quicksort - O(n2) - avg. O(n log n)
Computational Thinking Concepts
- Algorithmic Thinking
- Abstraction
- Problem Decomposition
- Data
- Control Flow
