Unit 1 - Computational Thinking

What is decomposition

Breaking down a larger problem into smaller parts

What is abstraction

Removing unnecessary detail to focus only on main points

What is an algorithm

Set of instructions to perform a specific task

What is a subprogram

Self-contained block of code to perform specific task within larger program

What are benefits of subprograms

• Code can be reused (avoids duplication) - Multiple people can work on same project at the same time - Easier to maintain/debug code - Breaks down larger problem and makes logic clearer and easier to understand

What is the terminal symbol in a flowchart

What is the selection/decision statement in a flowchart

What is the process symbol in a flowchart

What is the input/output symbol in a flowchart

What is the subprogram symbol in a flowchart

What is sequence

Instructions exectued one after the other in a specific order

What is selection

Choosing between 2+ options (e.g. if statement)

What is repetition

Repeating set of instructions until there is a desired outcome

What is condition-controlled repetition

Number of repeats not known (e.g. while True)

What is count-controlled repetition

Repeats a known specific amount of times

What is iteration

Repeating set of instructions until outcome is met (e.g. over items in data structure)

What is a variable

Named location in memory which stores a value which can be changed when the program is running

What is a constant

Named location in memory which stores a value that cannot be changed when the program is running

What is an array

Data structure which can store multiple items of data of the same data type

What is a record

Data structure which can store multiple items of data of different data types

What is an arthimetic operator

Used to perform calculations (e.g. +, -, /, % etc.)

What is a relational operator

Compare items of data (e.g. ==, !=,

What is a logical/boolean operator

Combine relational operators

What is the logical operator AND

all statements must be true to get an overall true

What is the logical operator OR

At least one statement must be true to get an overall true

What is the logical operator NOT

Inverts boolean value of statement

What is a dry run

Mental/pen-paper run through of algorithm one step at a time to help understand it or find errors

What is a trace table

Table containing value of each variable & output to keep track

What is an error

Bug in program preventing it from running or producing unexpected results

What is a syntax error

Code doesn't conform to rules of programming language so code cannot run

What is a runtime error

Occurs while code is running if computer is asked to perform specific task causing program to crash (runs out of memory)

What is a logic error

Program runs but produces unintended or incorrect result

What is a linear search

Brute force starts at beginning and continues over each item until item found or reaches the end

What is the best case for a linear search

Item is in the first position

What is the worst case for a linear search

Last item in list or not in list

What is a binary search

Divide and conquer - splits list in half until item found

What is a binary search dependant on

List must be sorted

What is the best case for a binary search

First median position is item

What is the worst case for a binary search

Last median position is item

What is a bubble sort

Starts at beginning and checks values in pairs, swapping if in wrong order - repeats until each value in right place

What is a repeat in a bubble sort called

Pass

What is the best case for a bubble sort

Already sorted

What is the worst case for a bubble sort

Reversed sorted

What is a merge sort

Breaks down list into component parts and builds back up in correct order

What does the number of compares in a merge sort depend on

Number of items