Algorithms and Problem Solving
43 Pages16037 Words2 Views
Added on 2023-01-09
About This Document
This lecture notes cover the topic of algorithms and problem solving. It includes an introduction to the problem-solving cycle and various algorithms such as hashing algorithms, sorting algorithms, and searching algorithms. The notes also touch upon topics like sequences, series, matrices, and limits. The content is suitable for the course Computational Problem Solving.
Algorithms and Problem Solving
Added on 2023-01-09
ShareRelated Documents
Lecture Notes
Computational Problem Solving
Week 1:
Algorithms and Problem Solving and
Fundamentals
Contents
Introduction ..................................................................................................................................................................2
Week 1: Algorithms and Problem Solving and Fundamentals ...................................... Error! Bookmark not defined.
Problem Solving ........................................................................................................................................................3
Algorithms ..............................................................................................................................................................11
Hashing Algorithms .................................................................................................................................................12
Sorting Algorithms ..................................................................................................................................................12
Bubble Sort .............................................................................................................................................................13
Insertion Sort ..........................................................................................................................................................15
Selection Sort ..........................................................................................................................................................16
Radix Sort ................................................................................................................................................................16
Quick Sort ...............................................................................................................................................................16
Searching Algorithms ..............................................................................................................................................18
Linear Search ..........................................................................................................................................................19
Binary Search ..........................................................................................................................................................19
Bin Packing Algorithms ...........................................................................................................................................20
Extension Topic: Numerical Algorithms..................................................................................................................41
Sequences ...............................................................................................................................................................24
Series ......................................................................................................................................................................29
Matrices ..................................................................................................................................................................31
Limits.......................................................................................................................................................................36
Application: Shannon Entropy ................................................................................................................................37
Application: Google Interviews ..............................................................................................................................38
Extension Topic: Infinite Series’ ..............................................................................................................................39
Computational Problem Solving
Week 1:
Algorithms and Problem Solving and
Fundamentals
Contents
Introduction ..................................................................................................................................................................2
Week 1: Algorithms and Problem Solving and Fundamentals ...................................... Error! Bookmark not defined.
Problem Solving ........................................................................................................................................................3
Algorithms ..............................................................................................................................................................11
Hashing Algorithms .................................................................................................................................................12
Sorting Algorithms ..................................................................................................................................................12
Bubble Sort .............................................................................................................................................................13
Insertion Sort ..........................................................................................................................................................15
Selection Sort ..........................................................................................................................................................16
Radix Sort ................................................................................................................................................................16
Quick Sort ...............................................................................................................................................................16
Searching Algorithms ..............................................................................................................................................18
Linear Search ..........................................................................................................................................................19
Binary Search ..........................................................................................................................................................19
Bin Packing Algorithms ...........................................................................................................................................20
Extension Topic: Numerical Algorithms..................................................................................................................41
Sequences ...............................................................................................................................................................24
Series ......................................................................................................................................................................29
Matrices ..................................................................................................................................................................31
Limits.......................................................................................................................................................................36
Application: Shannon Entropy ................................................................................................................................37
Application: Google Interviews ..............................................................................................................................38
Extension Topic: Infinite Series’ ..............................................................................................................................39
Introduction
In this strand, you will be learning about sets with its related topics of tuples, relations and functions, number
theory, logic (both predicate and propositional) and finally basic graph theory and matrices. This section
introduces some of the “basics” that we will be using throughout the course.
Week 1: Algorithms and the Problem-Solving Cycle and Fundamentals (Matrices, sequences and series)
Week 2: Basic Number Theory, Cryptography + ciphers
Week 3: Proof + Proof by induction / Lists in Python and mutability
Week 4: Intro to Graphs & Graph Algorithms / Intro to Object Oriented Programming
Week 5: sets and tuples / dictionaries in Python / String and File Manipulation
Week 6: Reading week
Week 7: Recurrence Relations and Recursion
Week 8: Languages, FSA, Regular Expressions / Testing strategies, execution and debugging
Week 9: Algorithms + complexity / More Object-Oriented Programming
Week 10: Coding graphs and algorithms in Python
Week 11: Simple Games in Python
Week 12: Consolidation and revision
In this strand, you will be learning about sets with its related topics of tuples, relations and functions, number
theory, logic (both predicate and propositional) and finally basic graph theory and matrices. This section
introduces some of the “basics” that we will be using throughout the course.
Week 1: Algorithms and the Problem-Solving Cycle and Fundamentals (Matrices, sequences and series)
Week 2: Basic Number Theory, Cryptography + ciphers
Week 3: Proof + Proof by induction / Lists in Python and mutability
Week 4: Intro to Graphs & Graph Algorithms / Intro to Object Oriented Programming
Week 5: sets and tuples / dictionaries in Python / String and File Manipulation
Week 6: Reading week
Week 7: Recurrence Relations and Recursion
Week 8: Languages, FSA, Regular Expressions / Testing strategies, execution and debugging
Week 9: Algorithms + complexity / More Object-Oriented Programming
Week 10: Coding graphs and algorithms in Python
Week 11: Simple Games in Python
Week 12: Consolidation and revision
Problem Solving
Solving problems is hard. Most problems you have encountered before having known solutions and indeed most
of the problems within this course. Nevertheless, it is important to learn how to break down problems with
unknown solutions to see how to tackle these. Often in work or research situations you might have to solve a task
which you may use pre-existing solutions to help but they might not solve the problem. Therefore, these solutions
might need to be adapted. Sometimes, there are no pre-existing solutions.
When you are presented with a problem you will follow a problem-solving cycle. Once you have a (potential)
solution, you might improve your model, generalise, and then solve this or move to the next problem (dependent
on the task). Therefore, the problem-solving cycle is iterative.
The following breakdown of problem solving is taken from “How to Think Like a Programmer” by Paul Vickers
(The HTTLAP approach). It provides a useful framework in how to break down an unknown and unseen problem.
Solving problems is hard. Most problems you have encountered before having known solutions and indeed most
of the problems within this course. Nevertheless, it is important to learn how to break down problems with
unknown solutions to see how to tackle these. Often in work or research situations you might have to solve a task
which you may use pre-existing solutions to help but they might not solve the problem. Therefore, these solutions
might need to be adapted. Sometimes, there are no pre-existing solutions.
When you are presented with a problem you will follow a problem-solving cycle. Once you have a (potential)
solution, you might improve your model, generalise, and then solve this or move to the next problem (dependent
on the task). Therefore, the problem-solving cycle is iterative.
The following breakdown of problem solving is taken from “How to Think Like a Programmer” by Paul Vickers
(The HTTLAP approach). It provides a useful framework in how to break down an unknown and unseen problem.
We will illustrate this process with the solution to noughts and crosses.
This is a game for two players. It consists of a 3x3 grid into which a O or an X is placed by each player in turn. This
is also called tic tac toe. Each player takes turns to place their symbol onto the grid.
The object of the game is to be the first to obtain a winning straight line consisting of their set of symbols, these
either being 3 O’s or 3 X’s.
Using an appropriate strategy, establish the number of winning lines when playing noughts and crosses on a 3x3
board. Include each of the stages: problem understanding, problem solution and implementation in terms of an
algorithm.
Once you have completed the above, extend your solution to describe the number of winning lines when playing
noughts and crosses on an 𝑚 × 𝑛 grid, where 𝑚 and 𝑛 are positive whole numbers given that a winning line is 𝑝
units long.
We can then follow the approach of HTTLAP to help us break down the problem.
Understanding the problem
Q. What are you being asked to do?
A. Find the number of ways to have a winning line in the game
Q. What is required?
This is a game for two players. It consists of a 3x3 grid into which a O or an X is placed by each player in turn. This
is also called tic tac toe. Each player takes turns to place their symbol onto the grid.
The object of the game is to be the first to obtain a winning straight line consisting of their set of symbols, these
either being 3 O’s or 3 X’s.
Using an appropriate strategy, establish the number of winning lines when playing noughts and crosses on a 3x3
board. Include each of the stages: problem understanding, problem solution and implementation in terms of an
algorithm.
Once you have completed the above, extend your solution to describe the number of winning lines when playing
noughts and crosses on an 𝑚 × 𝑛 grid, where 𝑚 and 𝑛 are positive whole numbers given that a winning line is 𝑝
units long.
We can then follow the approach of HTTLAP to help us break down the problem.
Understanding the problem
Q. What are you being asked to do?
A. Find the number of ways to have a winning line in the game
Q. What is required?
A. The number of winning lines in noughts and crosses
Q. What is the unknown?
A. The size of the board, the number of moves
Q. Can the problem be better expressed by drawing a diagram or picture?
A. Yes, playing the game and then looking at diagrams of this might help
Q. What are the principal parts of the problem?
A. 1) count the size of the grid, 2) find the number of winning lines
Q. Are there several parts to the problem?
A. Not sure, we can start with a simpler version but it looks relatively simple.
Q. Have you made any assumptions?
A. Not so far, we are assuming that we can play the game and know the rules. We are also assuming we do not
care how those moves are made, just the number of possible lines that need to be either a O or a X to win.
Q. What can you do about the assumptions?
A. We do not need to do anything
Devising a Plan
Q. Have you solved this type of problem before / is it similar to one you have solved before?
A. No not really, though most of us played this game as a child
Q. Are some parts of the problem more easily solved than others?
A. As the number of columns and rows increase the problem might become harder
Q. If the problem is too hard, can you solve a simpler version of it, or a related problem?
A. Yes, I could simplify the problem. I can look at the classic 3x3 grid
Q. Does restating the problem help? Try restating it in a different language.
A. I could look at the problem in a slightly different way, instead of looking at the problem as a concurrent one (the
number of ways to win a line), I could look at it in a sequential way, so what happens if I add an extra column, row
or number needed to win.
So, we can then look for patterns in the 3x3 grid, 3x4 grid, 4x3 grid and 4x4 grid keeping the number of winning
lines as 3. Then we can generalise further by looking at the 4x4 case but this time with 4 in a row. We will keep this
information in a table. For this we will do this via brute force (at least for the 3x3 case) but try to see also how many
ways it is to help us generalise it.
We will then look for a pattern in the table using the number of winning ways to win at each column, row and
diagonal and see if we can work out the number of ways this can be achieved in a formula using what we know
about it.
Finally, we shall write pseudo-code to demonstrate how to check whether a game has been won.
Q. Did you make use of all the information in the problem statement?
A. Yes.
Q. Can you satisfy all the conditions of the problem?
A. Yes if I know how the size of the grid
Q. What is the unknown?
A. The size of the board, the number of moves
Q. Can the problem be better expressed by drawing a diagram or picture?
A. Yes, playing the game and then looking at diagrams of this might help
Q. What are the principal parts of the problem?
A. 1) count the size of the grid, 2) find the number of winning lines
Q. Are there several parts to the problem?
A. Not sure, we can start with a simpler version but it looks relatively simple.
Q. Have you made any assumptions?
A. Not so far, we are assuming that we can play the game and know the rules. We are also assuming we do not
care how those moves are made, just the number of possible lines that need to be either a O or a X to win.
Q. What can you do about the assumptions?
A. We do not need to do anything
Devising a Plan
Q. Have you solved this type of problem before / is it similar to one you have solved before?
A. No not really, though most of us played this game as a child
Q. Are some parts of the problem more easily solved than others?
A. As the number of columns and rows increase the problem might become harder
Q. If the problem is too hard, can you solve a simpler version of it, or a related problem?
A. Yes, I could simplify the problem. I can look at the classic 3x3 grid
Q. Does restating the problem help? Try restating it in a different language.
A. I could look at the problem in a slightly different way, instead of looking at the problem as a concurrent one (the
number of ways to win a line), I could look at it in a sequential way, so what happens if I add an extra column, row
or number needed to win.
So, we can then look for patterns in the 3x3 grid, 3x4 grid, 4x3 grid and 4x4 grid keeping the number of winning
lines as 3. Then we can generalise further by looking at the 4x4 case but this time with 4 in a row. We will keep this
information in a table. For this we will do this via brute force (at least for the 3x3 case) but try to see also how many
ways it is to help us generalise it.
We will then look for a pattern in the table using the number of winning ways to win at each column, row and
diagonal and see if we can work out the number of ways this can be achieved in a formula using what we know
about it.
Finally, we shall write pseudo-code to demonstrate how to check whether a game has been won.
Q. Did you make use of all the information in the problem statement?
A. Yes.
Q. Can you satisfy all the conditions of the problem?
A. Yes if I know how the size of the grid
Q. Have you left anything out?
A. No I do not appear to have.
Possible Solution
How many ways can we win the game? For now, we are ignoring how we can win, just the number of winning lines
to win.
So, there are 8 different winning lines. This was solved by brute force – we looked at all possible winning
combinations.
So, we know that there are 8 possible ways to win. But how can we check this? If we let our grid be the matrix
𝑔𝑟𝑖𝑑[𝑖, 𝑗] for the 𝑖𝑡ℎ row and 𝑗𝑡ℎ column. Then, we have If grid[1,1] == “X” and grid[2,2] == “X” and grid[3,3]==“X”
will check if X has won on the diagonal. Similarly, for “O”. We would then need to do the same for the other diagonal
and each row and column. The other diagonal is cells grid[1,3]; grid[2,2]; grid[3,1].
We can then write some code to check for a winner (this is using Python constructs that you might not have learnt
next; however, this is not important yet as we are not doing any programming yet):
A. No I do not appear to have.
Possible Solution
How many ways can we win the game? For now, we are ignoring how we can win, just the number of winning lines
to win.
So, there are 8 different winning lines. This was solved by brute force – we looked at all possible winning
combinations.
So, we know that there are 8 possible ways to win. But how can we check this? If we let our grid be the matrix
𝑔𝑟𝑖𝑑[𝑖, 𝑗] for the 𝑖𝑡ℎ row and 𝑗𝑡ℎ column. Then, we have If grid[1,1] == “X” and grid[2,2] == “X” and grid[3,3]==“X”
will check if X has won on the diagonal. Similarly, for “O”. We would then need to do the same for the other diagonal
and each row and column. The other diagonal is cells grid[1,3]; grid[2,2]; grid[3,1].
We can then write some code to check for a winner (this is using Python constructs that you might not have learnt
next; however, this is not important yet as we are not doing any programming yet):
Suppose rather than having a 3x3 grid, we instead have a 𝑚 × 𝑛 grid where 𝑚 is the number of rows and 𝑛 is the
number of columns. How many different winning lines are there now? As you can probably see, this is harder to
solve by brute force.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3
Next is to fill in the table row by row and see if we can find a pattern. Looking at the 3x4 case with 3 in a row,
We then have 2 different ways per row 3 rows = 6 ways; 4 columns = 4 ways; 2 different ways per diagonal, 2
diagonals = 4 ways. Total is 6 + 4 + 4 = 14 ways. Filling this information into the table produces:
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
number of columns. How many different winning lines are there now? As you can probably see, this is harder to
solve by brute force.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3
Next is to fill in the table row by row and see if we can find a pattern. Looking at the 3x4 case with 3 in a row,
We then have 2 different ways per row 3 rows = 6 ways; 4 columns = 4 ways; 2 different ways per diagonal, 2
diagonals = 4 ways. Total is 6 + 4 + 4 = 14 ways. Filling this information into the table produces:
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
Next, we may look at the 4x3 case.
This has 4 rows and 4 ways to fill these in. We have three columns, two ways per column resulting in a total of 6
ways. For the diagonals, we have two different ways per diagonal and with two diagonals is 4 ways. In total, this is
4+6+4 which is 14 ways. Again, we can fill this information into the table.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
4 3 3 4 6 4 14
This is like the 3x4 case except that the number of ways to win over the vertical and horizontal lines have
swapped. We can notice this as well by geometry. Therefore, the game is symmetrical, and we can use this to
help us find a pattern. We can now look at the 4x4 case keeping the number of winning lines as 3 in a row.
This time, we have 2 different ways per column and row resulting in 8 different ways to win for each column and
row. For the diagonals, we have 4 different ways to win and with 2 diagonals is 8 different ways. So, in total there
are 24 different ways to win.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
4 3 3 4 6 4 14
4 4 3 8 8 8 24
This has 4 rows and 4 ways to fill these in. We have three columns, two ways per column resulting in a total of 6
ways. For the diagonals, we have two different ways per diagonal and with two diagonals is 4 ways. In total, this is
4+6+4 which is 14 ways. Again, we can fill this information into the table.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
4 3 3 4 6 4 14
This is like the 3x4 case except that the number of ways to win over the vertical and horizontal lines have
swapped. We can notice this as well by geometry. Therefore, the game is symmetrical, and we can use this to
help us find a pattern. We can now look at the 4x4 case keeping the number of winning lines as 3 in a row.
This time, we have 2 different ways per column and row resulting in 8 different ways to win for each column and
row. For the diagonals, we have 4 different ways to win and with 2 diagonals is 8 different ways. So, in total there
are 24 different ways to win.
m n p Number of
winning
vertical lines
Number of
winning
horizonal
lines
Number of
winning
diagonal
lines
Total number
of winning
lines
3 3 3 3 3 2 8
3 4 3 6 4 4 14
4 3 3 4 6 4 14
4 4 3 8 8 8 24
End of preview
Want to access all the pages? Upload your documents or become a member.