Chapter 2.1: Algorithms
Computational thinking
● Computational thinking: process of turning problem into something computer can solve
● Processes involved:
○ Abstraction:
■ Removing unnecessary detail and focusing only on what is important
■ Result is algorithm that represents world with symbols, variables etc to
represent real world
○ Decomposition:
■ Breaking problem into smaller parts so it becomes possible to solve problem
using computation
○ Algorithmic thinking:
■ Writing step-by-step instructions that uses sequence, selection and iteration
so problem is solved effectively
○ Pattern recognition:
■ Finding patterns in complex data which helps to solve problem
Abstraction
● Removing unnecessary detail and focusing only on what is important
● Use abstraction to:
○ Make problem easier to solve (simplifies problem)
○ Helps making good use of resources
● Graphics: simplify objects or icons to be easier to process
● Maps: removes unnecessary detail eg. individual houses to communicate info clearly
Decomposition
● Break down complex problem into subproblems until they are manageable
● Eg. learning a part of a song at a time rather than whole song at once
● When problems are decomposed:
○ Easier to solve than trying to tackle a problem in one go
○ Each part of problem can be solved by itself
○ Parts can be combined to solve bigger problem
○ Each part of problem can be tested by itself - helps making sure each part is robust
○ Each part can be reused in other projects
Algorithmic thinking
● How programming constructs can be used to solve a problem
● Step-by-step instructions designed to solve problem
● Algorithms in our lives:
○ Maps: use algorithms to program shortest route
○ Product recommendations: algorithms to recommend what to buy or advert based on
web browsing activities
● Problems are solvable using computational methods if it has inputs, processes and outputs
●
● Computer accepts inputs, processes data, uses storage to load and store data and produces
outputs
○ Storage can be used to temporarily or permanently store data
○ Processes: performing calculations and logical reasoning
, ● Programming constructs:
○ Sequence: running one instruction after another
○ Selection: running different code depending on evaluation of a condition
○ Iteration: running the same code a number of times, while a condition is true or until a
condition is true (count-controlled or condition-controlled)
○
● Importance:
○ Algorithmic thinking is about getting to a solution through clearly defined steps that
are needed
○ If mistakes in algorithm then computer won’t do what it’s meant to
○ Some are more efficient than others
● Generalisation:
○ Algorithm involving a specific task can be adapted to smaller tasks
○ Good programmers will create programs with generalisation in mind so code can be
adapted to work for similar programs
● Algorithms are refined over time to be more efficient, secure and robust
● Successful algorithms:
○ Relatively easy to understand and follow
○ Produces correct result
○ Works efficiently by only using necessary resources
○ Works safely
Inputs, processes and outputs
● Inputs: data entered into system
● Processes: any calculations or logic that happens
● Outputs: how data is communicated to user (could be sent to storage device)
●
Structure diagrams
● Visual tool to help understand how individual parts of systems make up whole
● Decomposing problem into modules is good:
○ Easier to get different people to work on different parts of problem at once
○ Each module can be tested in isolation
○ Modules can be reused
○ Clear what each part of program does
Common errors
● Logical error: code makes logical sense but produces wrong result
● Syntax error: code doesn’t comply with writing rules of programming language
Flowcharts
● Visual representation of a process that communicates to others how problem can be solved
and uses standard symbols so everyone knows what they mean
● Used when analysing, designing or documenting solutions to problems
, ●
Searching algorithms
● Keyword/search phrase: thing you’re searching for (needle)
● Data: to search keyword through (haystack)
● Search algorithm can programmed to tell:
○ Whether keyword is in list (true or false)
○ Position of keyword in list (-1 if not found)
Binary search
● Used to look for an item in an alphabetically ordered
list
● Decomposition method used to come up with binary
search method is known as “divide and conquer”
because size of problem is halved with each
comparison made
● How algorithm determines search item not in list:
eventually will be one item left in list to compare
against and if doesn’t match, then item not in list
● Benefits:
○ Very fast - size of problem is halved each
time a comparison is made
● Drawbacks:
○ Slightly tricker to programme than linear search
○ List must be sorted to begin with
Linear search
● Used to look for an item in an unordered list
● Go through each item in list until the keyword is found
or the end of the list is reached
● Common errors:
○ SyntaxError: invalid syntax - computer doesn’t
understand code (check spelling, brackets are
correct and no colons are missing)
○ NameError: name “word” is not defined -
identifier is probably misspelt (check spelling of
identifiers)
○ IndentationError: expected an indented block -
code isn’t indented properly (check indentation
of code)
○ Nothing happens - last three lines are indented (make last three lines not indented)
● How algorithm determines search item not in list: will get to end of list and if no more items left
to compare against, then item not in list
● Benefits:
○ Relatively easy to programme and understand
○ Works on unsorted lists
● Drawback:
○ Lot slower than binary search since size of problem only reduces by one each time
Computational thinking
● Computational thinking: process of turning problem into something computer can solve
● Processes involved:
○ Abstraction:
■ Removing unnecessary detail and focusing only on what is important
■ Result is algorithm that represents world with symbols, variables etc to
represent real world
○ Decomposition:
■ Breaking problem into smaller parts so it becomes possible to solve problem
using computation
○ Algorithmic thinking:
■ Writing step-by-step instructions that uses sequence, selection and iteration
so problem is solved effectively
○ Pattern recognition:
■ Finding patterns in complex data which helps to solve problem
Abstraction
● Removing unnecessary detail and focusing only on what is important
● Use abstraction to:
○ Make problem easier to solve (simplifies problem)
○ Helps making good use of resources
● Graphics: simplify objects or icons to be easier to process
● Maps: removes unnecessary detail eg. individual houses to communicate info clearly
Decomposition
● Break down complex problem into subproblems until they are manageable
● Eg. learning a part of a song at a time rather than whole song at once
● When problems are decomposed:
○ Easier to solve than trying to tackle a problem in one go
○ Each part of problem can be solved by itself
○ Parts can be combined to solve bigger problem
○ Each part of problem can be tested by itself - helps making sure each part is robust
○ Each part can be reused in other projects
Algorithmic thinking
● How programming constructs can be used to solve a problem
● Step-by-step instructions designed to solve problem
● Algorithms in our lives:
○ Maps: use algorithms to program shortest route
○ Product recommendations: algorithms to recommend what to buy or advert based on
web browsing activities
● Problems are solvable using computational methods if it has inputs, processes and outputs
●
● Computer accepts inputs, processes data, uses storage to load and store data and produces
outputs
○ Storage can be used to temporarily or permanently store data
○ Processes: performing calculations and logical reasoning
, ● Programming constructs:
○ Sequence: running one instruction after another
○ Selection: running different code depending on evaluation of a condition
○ Iteration: running the same code a number of times, while a condition is true or until a
condition is true (count-controlled or condition-controlled)
○
● Importance:
○ Algorithmic thinking is about getting to a solution through clearly defined steps that
are needed
○ If mistakes in algorithm then computer won’t do what it’s meant to
○ Some are more efficient than others
● Generalisation:
○ Algorithm involving a specific task can be adapted to smaller tasks
○ Good programmers will create programs with generalisation in mind so code can be
adapted to work for similar programs
● Algorithms are refined over time to be more efficient, secure and robust
● Successful algorithms:
○ Relatively easy to understand and follow
○ Produces correct result
○ Works efficiently by only using necessary resources
○ Works safely
Inputs, processes and outputs
● Inputs: data entered into system
● Processes: any calculations or logic that happens
● Outputs: how data is communicated to user (could be sent to storage device)
●
Structure diagrams
● Visual tool to help understand how individual parts of systems make up whole
● Decomposing problem into modules is good:
○ Easier to get different people to work on different parts of problem at once
○ Each module can be tested in isolation
○ Modules can be reused
○ Clear what each part of program does
Common errors
● Logical error: code makes logical sense but produces wrong result
● Syntax error: code doesn’t comply with writing rules of programming language
Flowcharts
● Visual representation of a process that communicates to others how problem can be solved
and uses standard symbols so everyone knows what they mean
● Used when analysing, designing or documenting solutions to problems
, ●
Searching algorithms
● Keyword/search phrase: thing you’re searching for (needle)
● Data: to search keyword through (haystack)
● Search algorithm can programmed to tell:
○ Whether keyword is in list (true or false)
○ Position of keyword in list (-1 if not found)
Binary search
● Used to look for an item in an alphabetically ordered
list
● Decomposition method used to come up with binary
search method is known as “divide and conquer”
because size of problem is halved with each
comparison made
● How algorithm determines search item not in list:
eventually will be one item left in list to compare
against and if doesn’t match, then item not in list
● Benefits:
○ Very fast - size of problem is halved each
time a comparison is made
● Drawbacks:
○ Slightly tricker to programme than linear search
○ List must be sorted to begin with
Linear search
● Used to look for an item in an unordered list
● Go through each item in list until the keyword is found
or the end of the list is reached
● Common errors:
○ SyntaxError: invalid syntax - computer doesn’t
understand code (check spelling, brackets are
correct and no colons are missing)
○ NameError: name “word” is not defined -
identifier is probably misspelt (check spelling of
identifiers)
○ IndentationError: expected an indented block -
code isn’t indented properly (check indentation
of code)
○ Nothing happens - last three lines are indented (make last three lines not indented)
● How algorithm determines search item not in list: will get to end of list and if no more items left
to compare against, then item not in list
● Benefits:
○ Relatively easy to programme and understand
○ Works on unsorted lists
● Drawback:
○ Lot slower than binary search since size of problem only reduces by one each time
