Classwork and homework for D1

Notes.


HOUSEKEEPING

Please:

  • Hand in your notebook for me to mark your classwork and homework each Tuesday morning. If you don’t see me in Assembly, bring your book to the maths office and leave it in my blue tray.
  • Before you hand in your notebook:
    • Check your work against the answers in the back of the book, or (for questions not in the book) https://mathsmartinthomas.wordpress.com/answers/ and mark it yourself
    • Write your response to comments I’ve written in your book the previous week.
  • Glue all worksheets into your notebook.
  • Come and see me any time I’m available if you have questions you have not been able to ask in class. I work part-time at CoLA, and am in school Thursdays and Fridays, and early Tuesday morning.

LESSON 1: WE WILL LEARN HOW COMPUTERS SORT LISTS

Starter activity

Lists of counters are set out in the classroom. The class will divide into groups, and each group’s task is to sort its list of counters into ascending order. But you have to find a sorting method which a computer can do. Write your sorting method up on a whiteboard.

A computer can only do one simple thing at a time. It can compare two numbers to see which is bigger. It can swap the positions of two numbers in the list. It can move numbers from your starting list into a reserve list (initially blank). It can tag a number. That’s all.

It can do those simple things reliably and fast, and keep on doing them without getting distracted or tired.

Choose one person from your group to be the computer. The rest of your group are the programmers telling her or him what to do.

We will discuss the ideas you come up with, and then discuss a method which is actually used on computers, Quicksort, and a method which might be used on computers but isn’t, called Bubble Sort. And which is better, and why.

Optional activities

Activity

Ex.1C Q.1,2

Activity

Ex.1F Q.2

Ex.1C Q.3,4

plus:

*1. How many comparisons are needed to do a Bubble Sort on a list of seven items?

*2. Supposing we’re lucky and the pivot always divides the list into equal halves, how many comparisons are needed in Quicksort on a list of seven items?

*3. If the pivots are unluckily chosen, so that each time the pivot turns out to be the smallest number in the list or sublist, and the pass moves all items to the right of the pivot and none to the left, how many comparisons are needed to do a Quicksort on a list of seven items?

*4. It would be a bit easier to do Quicksort if we always took the first item in a list or sublist as pivot, rather than the middle one. So why make it more complicated and take the middle item? (Hint: it’s to do with reducing the probability that our choices of pivots turn out to be unlucky.)

LESSON 2: MAKING SURE WE’RE GOOD WITH BUBBLE SORT AND QUICKSORT

Starter activity: Write on the whiteboard the step by step rules for Quicksort and Bubble Sort.
When we’re sure we’ve got them correct and clear, you’ll write them into your notebooks.

Then we practice writing those sorts on paper (rather than doing them with counters).

For Quicksort: as you scan through each list, and create the list for the next pass, place items which come after the pivot by filling up from the right of the new (and items which come before the pivot by filling up from the left). Then the pivot goes into the last empty space. (This is a bit different from the method in the book).

Homework

Ex.1F Q.1,2

Page 77 Q.1

Page 80 Q.13

Ex.1C Q.5

Plus:

Extra: *5. How many comparisons are needed to do a Bubble Sort on a list of 1023 items?

Extra: *6. Supposing the pivot always divides the list into equal halves, how many comparisons are needed in Quicksort on a list of 1023 items? 1023 is 210-1.

Extra: *7. Roughly how many comparisons will be needed for 1,048,575 items (that’s 220-1), by Bubble Sort and by Quicksort?

Extra: *8. You already know an algorithm for sorting lists of data by hand. It’s called stem-and-leaf plot. What does that algorithm have in common with Quicksort which makes it relatively efficient? Why can’t computers be programmed to do stem-and-leaf instead of Quicksort?

LESSON 3: WE WILL LEARN WHAT AN ALGORITHM IS, AND ABOUT BINARY SEARCH

In this course you learn 15 or so new how-to-calculate instruction lists (called algorithms) and how to use them. The main thing you need for the exam is to be confident and fluent with those algorithms.

Starter activity

Read the following definitions of “algorithm”. Write on a whiteboard the one you find clearest, and write a sentence explaining why you find it clearest.

definitions_of_algorithm

“An algorithm is an abstract recipe, prescribing a process that might be carried out by a human, by a computer, or by other means” – David Harel, Algorithmics

“An algorithm is a specific set of instructions for carrying out a procedure or solving a problem… with the requirement that the procedure terminate at some point” – Eric Weisstein, mathworld.wolfram.com/Algorithm.html

“An algorithm

1. describes the method how a task is to be accomplished;

2. consists of a finite sequence of steps;

3. which if performed will result in a process being carried out” – Behzad Bordbar, notes for Introduction to Computer Science course at Birmingham University

“An algorithm is an effective procedure, a way of getting something done in a finite series of discrete steps” – David Berlinski, The Advent of the Algorithm

“An algorithm is a list of instructions for solving a problem which has these properties:

1. The list has a unique starting action

2. Each action in the list has a unique successor

3. The list terminates after a finite number of actions with either a solution or a statement that the problem is insoluble” – adapted from Ralston, Reilly, and Hemmendinger, Encyclopedia of Computer Science

“An algorithm is a precise set of instructions that is so clear that it will allow anyone, or even a computer, to use it to achieve a particular goal in a specified number of steps” – your textbook.

We will discuss which definitions you find clearest. Then write into your notebook what you think, after discussion, is the clearest definition. Give a whole page over to it. Leave the rest of that page blank.

Activity: explanation and examples on binary search.

Activity

Write on a whiteboard whether each of these is or is not an algorithm, and why or why not. If it is an algorithm, write a flowchart for it and an example of using it. (For example, if you think A is an algorithm, you might write an example using P=2, Q=3, and R=5).

which_is_algorithm

A. To solve the equation Px+Q=R

1. Subtract R from Q

2. Divide the answer from (1) by P

B. To find the remainder when Q is divided by P, if Q and P are both positive whole numbers

1. Set n=0

2. Set S=nP and T=(n+1)P

3. If S is less than Q and T is more than Q, calculate m=Q-S, output m and terminate the calculation

4. Otherwise increase n by 1 and go to step (2)

C. To solve the equation x2=2

1. Set n=0

2. Set m=1

3. Calculate n2

4. If the answer from (3) is less than 2, increase n by m and go back to step (3).

If the answer from (3) is more than 2, go to step 5.

5. Decrease m to m/10 and n to n−9m/10

6. Go to step 3

D. To find an approximate solution to the equation x2=200 within 1 unit of the correct answer

1. Set n=0

2. Set m=1

3. Calculate n2

4. If the answer from (3) is less than 200, increase n by m and go back to step (3). If the answer from (3) is more than 200, print out n and terminate the calculation.

E. To make vanilla cupcakes

1. Get 150g butter, 150g caster sugar, 175 self-raising flour, 3 eggs, 1 teaspoon vanilla extract, a bun tray, cake cases, a bowl, an electric whisk, and an oven

2. Heat the oven to 180 degrees C

3. Put the cake cases in the tray

4. Soften the butter

5. Put all the ingredients in the bowl, mix with the electric whisk for 2 minutes, and put the mixture into the cake cases

6. Put the tray in the oven and bake for 20 minutes

7. Turn the oven off, take the tray out of the oven, and set it to cool.

F. To be happy

1. Dress every day as if you expect to meet the love of your life

2. Hugs, not drugs

3. Take it easy on yourself

What’s special about the algorithms studied in this course? You’ve been studying algorithms ever since primary school, without calling them that.

There are three things which make this course’s how-to-calculate instruction lists a bit different.

  • They are mostly for problems where in everyday life you might think of yourself as just deciding an answer rather than calculating it (e.g. sorting a list; finding whether an item is or is not in a list).
  • The instruction lists (algorithms) are typically built up from very simple and clear-cut steps (comparing two numbers to see which is bigger; adding one number to another; chosing one or another branch in a tree…), even though you may have to do those steps many times over.
  • The data are mostly whole-number data, or just yes/no data (e.g. is this vertex connected to that one, yes or no?)

Activity

Skim through the D1 textbook to get an idea of what sort of algorithms are in it, and then do this activity in your notebook.

Look at this list of algorithms. Classify them into two groups:

(A) the sort of algorithm you might study in “decision mathematics” (which could also be called “discrete mathematics”, “algorithmics”, or “introduction to computer science”)

(B) the sort of algorithm which you might study in other branches of mathematics (like Further Pure mathematics)

For each one, write a couple of words on why you have classified it that way.

1. An algorithm to calculate a timetable for CoLA so that no student or teacher has two different classes at the same time, no classroom has two different classes at the same time, each student has classes in the subjects she or he wants, and each teacher has classes in the subjects she or he is qualified to teach

2. An algorithm to find the speed of a falling object after time t

3. An algorithm to find the distance a falling object has fallen after time t

4. An algorithm to calculate the number of checkouts a supermarket needs in order to keep maximum queues below a certain number, given a known flow of customers

5. An algorithm to decide, given the code for a computer program, whether it will terminate or just go on for ever

6. An algorithm to find the shape of raindrops, given knowledge of the laws of surface tension

Extra 1. Give one other example of an algorithm of type A, and one other example of an algorithm of type B.

Extra 2. Read this about the further areas which this course is designed to lead into https://mathsmartinthomas.wordpress.com/2014/08/24/decision-maths-what-it-is-and-where-it-comes-from/ and write a short summary of it into your notebook.

Extra 3. Read this about the actress Hedy Lamarr https://mathsmartinthomas.wordpress.com/2014/08/24/the-gender-politics-of-computer-science/ and write a short summary of it in your notebook.

LESSON 4: FLOW CHARTS. HOW TO DO BIN PACKING

Starter activity: Look at sample flow charts from http://www.rff.com/flowchart_samples.htm and write flow charts for:

1. deciding whether the temperature is below freezing in Celsius (not Fahrenheit)

2. finding the smallest number in a list of numbers

3. calculating 2n

Activity: Bin packing with cardboard boxes and books.

Activity: Write definitions of:
First Fit
First Fit Decreasing
Full-Bin

Activity

Ex.1D Q.1. Ex.1E Q.1

Homework will be selected from: Ex.1D Q.2, Ex.1E Q.2, Ex.1F Q.3,4. Ex.1C Q.3,4; Ex.1D, Q.5; Ex.1E Q.4; p.81 Q.15

Extra 3. Read https://mathsmartinthomas.wordpress.com/2014/08/23/bin-packing-algorithms/ and write a short summary of it in your notebook.

LESSON 5: WHAT DO WE MEAN BY “GRAPH” WHEN WE DO “GRAPH THEORY”? WHAT ARE THESE GRAPHS FOR? HOW TO READ AND WRITE THEM

Starter activity

Write into your notebook, under the heading “Graph theory”, the definitions of graph, vertex/node, edge/arc

When we do “graph theory”, the word “graph” does not (despite what your textbook says) have “a broader meaning” than the sort of graph you draw with axes to describe a mathematical function. It has a different meaning, in the same way that the word “club” in “chess club” has a different meaning from “club” meaning cosh or cudgel.

Demonstration: Bridges of Konigsberg

sevenbridges

sevenbridgesgraph

Demonstration: Faces+Vertices-Edges=2 for network drawn on a sphere or similar (e.g. football)

We’ll review definitions of other terms: subgraph, degree/valency/order, path, walk, cycle/circuit, connected, simple graph, digraph, and you should write them into your notebook as homework.

Activity

Ex.2A Q.1-3

We’ll review definitions of more terms: tree, spanning tree, bipartite graph, complete graph, kn, complete bipartite graph, kr,s, isomorphic graphs, and you should write them into your notebook as homework.

Activity

Ex.2B Q.1-4

Ex.2A Q.4b,c,d,e,5,6 (not Q.4a)

Activity

Remember to write all the definitions into your notebook for homework.

LESSON 6: HOW TO WRITE GRAPHS AS MATRICES (I.E., BASICALLY, TABLES OF NUMBERS)

Starter activity

Shut your notebooks and textbooks. On a piece of paper write your name and then the most important definitions:

Graph; Vertex/node; and Edge/arc (one sentence defines all three)

Degree

Tree

Spanning tree

Pass your paper to your right, and mark the answers from your neighbour on the left.

We will see how graphs can be described by tables of numbers (matrices).

Activity

Ex.2B Q.6,7,9,10a (not Q.10b)

Ex.2C Q.1,2,3,5, 6 (not Q.4)

Homework activity

Draw a weighted graph (network) representing the following vertices

A. The main entrance of CoLA

B. The entrance to the library

C. The entrance to the hall

D. The maths office

E. The Sixth Form Study Area. (For this purpose regard the whole of the Sixth Form Study Area as a single point, and assume you have arrived at that same single point whether you come by the South staircase or the West staircase).

You should include 15 edges:

– the routes between the main entrance, the library, and the hall across the ground floor of CoLA;

– routes via the West and North staircases from all three to the maths office;

– routes via the West and South staircases from all three to the Sixth Form Study Centre.

Measure them by pacing them out, and for this purpose assume one pace equals one metre.

SCAN0001

Extra: Read http://www.cs.sfu.ca/~ggbaker/zju/math/planar.html and write a couple of sentences in your notebook to say:

1. what a planar graph is

2. why being able to tell whether a graph is planar is important in designing integrated circuits.

LESSON 7: HOW TO DO THE KRUSKAL AND PRIM ALGORITHMS FOR A MINIMUM SPANNING TREE

Starter activity: same as previous lesson

Shut your notebooks. On a piece of paper write your name and then the most important definitions:

Graph; Vertex/node; and Edge/arc (one sentence defines all three)

Degree

Tree

Spanning tree

Pass your paper to your right, and mark the answers from your neighbour on the left.

We will take a graph of CoLA as constructed for the homework activity and learn about Kruskal’s algorithm by using it to find a minimum spanning tree for that graph.

SCAN0001

Activity

Ex.3A Q.1(a), ex.3B Q.1(a)

We will take the graph of CoLA as constructed for the homework activity and learn about Prim’s algorithm by using it to find a minimum spanning tree for that graph.

Homework

Ex.3A Q.1(b) and (c), Q.2

Ex.3B Q.1(b) and (c), Q.2

Why two algorithms, Kruskal and Prim, for the same problem, minimum spanning tree?

Your textbook says that Prim’s algorithm is better suited for use on computers because it can be applied more easily to a distance matrix, and (make sure you read the answer given on p.191 to Review Exercise 1, Q.5d) because it is hard to check for cycles in a large network.

I’m not convinced the book is correct. Other sources say that Kruskal is easier to run than Prim, and as good for most graphs. Prim is quicker if the graph is “dense”, i.e. the number of edges is high relative to the number of vertices (which of course means lots of cycles to check for). However, for the exam you should learn the answer given in the book.

I think the textbook tells you about two algorithms for sorting, Bubble Sort and Quicksort, so that you can see that an algorithm which looks neater and simpler may in fact be worse than a more complicated-looking one.

It gives you both First Fit and First Fit Decreasing for bin packing (I think) to show that where there is no exact algorithm, there can be a trade-off between the easier but worse-approximation algorithm and the more difficult but better-approximation one. I cannot imagine why it gives you the Full Bin algorithm for bin packing, but there you go, it does.

LESSON 8: HOW TO DO PRIM’S ALGORITHM FROM A DISTANCE MATRIX

Starter activity

Ex.2C Q.4 (p.38 – calculating a distance matrix for a network)

Ex.2B Q.9b (p.37 – drawing a network from a distance matrix)

We will work through Example 4 on pages 48-9 to demonstrate how to do Prim’s algorithm from a distance matrix.

Activity

Ex.3C Q.1,2,3a,3b,4a (not 3c and 4b)

LESSON 9: HOW TO USE DIJKSTRA’S ALGORITHM TO FIND THE SHORTEST PATH BETWEEN TWO VERTICES

Starter activity: Ex.2A Q.4a (identifying paths in a network)

We will take the graph of CoLA as constructed for the homework activity and learn about Dijkstra’s [ ] algorithm by using it to find the shortest path from the Sixth Form Study Area to the maths office.

Activity

Ex.3C Q.1,2,3

Diagram sheet for Ex.3C

Ex.3D Q.8

Diagram sheet for Ex.3D

Extra: p.79 Q.7,8. (Q.7b is especially important).

Worksheets for Q.7,8 on p.79, aznd other Review Exercises

LESSON 10: MAKING SURE YOU CAN DO KRUSKAL’S, PRIM’S, AND DIJKSTRA’S ALGORITHMS

Starter activity: For this weighted graph showing US airports, find:

1. a minimum selection of routes which would still allow planes to reach every airport, even if sometimes in roundabout ways, using Kruskal’s algorithm

2. ditto using Prim’s algorithm

3. the shortest path from Boston (BOS) to Los Angeles (LAS), using Dijkstra’s algorithm.

us_airports

Activity

Ex.3E, Q.1-4 and Q.6-8

Diagram sheets for Ex.3E

During the lesson we will go through Q.5 as a class.

LESSON 11: HOW TO FIND A PATH TRAVERSING EVERY EDGE (THE “CHINESE POSTMAN”)

postie

In Australia all mail is delivered to a postbox on the street (not through a letterbox in your front door), and posties ride down the sidewalk on bikes. But sadly they don’t use graph theory.

The algorithm is called “the Chinese postman” because a Chinese mathematician first studied it, not because Chinese postal delivery workers use it. I’ve asked Australia Post. They work out their delivery rounds just by rule of thumb, without using any of these algorithms, and I’d guess the same is true of other postal services. But anyway…

Starter activity: Ex.4A Q.7a and b (the Bridges of Konigsberg). We did this back in lesson 5. Without looking back at your notes, try to do this problem on the whiteboard.

sevenbridges

The Chinese postman algorithm for the shortest path which goes along every edge is explained a bit obscurely in the book, so here are some notes. It goes as follows:

1. If all the vertices in the graph are even, then you can start wherever you like and find a path which goes along each edge just once and comes back to that start (an “Eulerian cycle”). That is the shortest path.

2. If just two vertices are odd, then you can find a path going along each edge just once which starts from one odd vertex and ends at the other (an “Eulerian walk”). That is the shortest path (as long as the problem allows you to start at one odd vertex and end at the other).

3. If more vertices are odd, or if you have to end at the same place as you started, then the shortest path will have to repeat some edges. You find the edges to be repeated by:

a) Listing the vertices which are odd (other than the start and end ones)

b) Making them even, by choosing the pairs of odd vertices which have the shortest connecting paths, and adding those paths in as extra edges. That takes you back to case 1.

Step 3(b) assumes that the odd vertices come in pairs. But you can assume that. Why?

Strictly speaking, in step 3(b), you can’t choose the shortest-connection pairs one by one (because committing yourself to a particular short-connection pair might oblige you to add in a very long connection for another pair, and maybe if you’d paired the odd vertices differently you could have had two medium-connection pairs with a smaller total shortest-connection time.

In practice, with the sort of problems we have here, you can look for shortest-connection pairs one by one, and then double-check and write out the full rigmarole (all possible pairs). Also, you don’t have to do a full Dijkstra-algorithm thing to find the shortest paths between the pairs: just look.

You will only have four odd vertices, at most, so three ways of pairing of odd vertices to check.

Just as well. If there were 10 odd vertices, you would have 7560 ways of pairing to check. If there were 16 odd vertices, you would have 129,729,600 ways of pairing to check, and if you worked on it 12 hours a day, non-stop, seven days a week, it would take you over 40 years.

Activity

Ex.4B Q.1,2,3

Extra: p.75 Q.6

LESSON 12: MAKING SURE WE’RE GOOD WITH THE “CHINESE POSTMAN” ALGORITHM

Starter activity: You have visitors from overseas, and they want to take a walk round the City of London.

  • Look at the map of the City, choose six roads you want to include in the walk, and draw a weighted graph showing those roads and their intersections. Choose roads so that all the intersections (vertices) are even, or just two are odd.
  • Make a good guess from the map for the length of the edges in your weighted graph. From St Paul’s to the Monument is about 1000 metres.
  • Design a walk which travels each chosen road exactly once.

cityoflondonmap

Activity

Ex.4C Q.1,2,3,4,5

We’ll do Q.6 with the whole class as an example.

Extra: p.81 Q.18

p.85 Q.29

LESSON 13: USING CRITICAL PATH ANALYSIS TO FIND THE SHORTEST TIME FOR A PROJECT

Starter activity: To get to school in the morning you have to do the following activities. What is the quickest time in which you can do it all? Assume you have an unlimited ability to multi-task, but still you can’t dress until after you’ve showered, and you can’t walk to school until you’ve dressed, etc. Do your working on the whiteboard.

  • Shower (5 minutes)
  • Dress (5 minutes)
  • Eat breakfast (10 minutes)
  • Feed your baby sister her breakfast (10 minutes)
  • Finish your homework (10 minutes)
  • Help your younger brother finish his homework (10 minutes)
  • Field your parents’ congratulations or complaints about your recent behaviour (10 minutes)
  • Wash up the family breakfast (5 minutes)
  • Pack your bag (2 minutes)
  • Take a phone call from a friend (2 minutes)
  • Walk to school (10 minutes)

baby

Critical path analysis is a way of doing the same “quickest time” calculation for huge projects with lots of workers.

We will discuss how to write a precedence table and a weighted and directed graph for a project.

Activity

Ex.5A Q.2

We will discuss the use of dummy edges.

Activity

Ex.5B Q.1,2

Activity

We will discuss how to forward-scan and backward-scan the graph.

Activity

Ex.5C Q.1,2,3

We will discuss what a critical path is, and what critical activities are.

Activity

Ex.5D Q.1,2,3

Ex.5A Q.1,3,4

Ex.5B Q.3,4

LESSON 14: MAKING SURE YOU’RE GOOD WITH CRITICAL PATH ANALYSIS TO FIND THE SHORTEST TIME FOR A PROJECT, AND CALCULATING FLOAT

Starter activity

Please do this activity on a whiteboard.

You and a team of friends are organising a party. Assume you know in advance near enough the numbers at the party.

It takes you 24 hours to decide the date

It takes 24 hours to decide on and book a place to hold it.

It takes 24 hours to decide the guest list.

It takes 144 hours to design the invitations, get them printed, and send them out.

It takes 144 hours to get replies to the invitations

It takes 72 hours to order the food and drink and plates and glasses and fix for them to be delivered. (Assume you can start doing this just as soon as you have booked the place for the party).

It takes 4 hours to set up the place for the party.

It takes 4 hours to have the actual party.

It takes 4 hours to clean up afterwards.

Do a critical path analysis for this project.

Activity

Ex.5E, Q.1,2; Ex.5I, Q.1, 2, 3.a to c. Extra: Ex.5I, Q.4.a to d, 5.a to c

LESSON 15: GANTT CHARTS: HOW TO READ THEM, HOW TO CONVERT A CRITICAL-PATH WEIGHTED GRAPH INTO A GANTT CHART AND A GANTT CHART INTO A WEIGHTED GRAPH, HOW TO USE A GANTT CHART TO FIND WHAT ACTIVITIES MUST BE HAPPENING AT A PARTICULAR TIME

Starter activity: Look at the Gantt chart for making teddy bears. This is a simpler and much older way of doing something like critical path analysis for short projects. Working on the whiteboard, rewrite the Gantt chart as a weighted and directed graph.

bears

Activity

Ex.5F Q.1

Activity

Ex.5F Q.2-3

Ex.5G Q.1-3

LESSON 16: HOW TO DO SCHEDULING DIAGRAMS WHEN THERE ARE NOT ENOUGH WORKERS FOR THE QUICKEST SCHEDULE

Starter activity: Look at the teddy-bear Gantt chart again.

  • Assuming that each activity takes one worker, how many workers does this schedule need?
  • Redraw the Gantt chart (on a whiteboard) so that it has only two rows and so gives a schedule which two workers can cover.
  • How much longer does it take with two workers than with three?

bears

Activity

Ex.5H Q.1-3

Extra: p.170 Q.23

LESSON 17: HOW BEST TO MATCH WORKERS AGAINST JOBS

Starter activity: In your notebook, under the heading “Bipartite graphs”, work through Example 1 on page 150.

Activity

Ex.7A Q.1

We’ll go through Example 5 on page 154-5 as a class.

Activity

Ex.7A Q.2-3

Ex.7B Q.1-4

Extra: Ex.7B Q.5-8

LESSON 18: HOW TO USE LINEAR PROGRAMMING. (1) HOW TO FORMULATE LINEAR PROGRAMMING PROBLEMS

Starter activity: Under the heading, “Linear programming”, write down in your notebook from pages 114-5 of the book:

  • The table summarising the info
  • The definition of the variables f and c
  • The statement of what we want to maximise, with a sentence to explain it in words
  • The four constraints, with a sentence in words to explain each one.

Activity

Ex.6A Q.1

Activity

Ex.6A Q.2-4

Extra: Ex.6A Q.5-7

LESSON 19: HOW TO USE LINEAR PROGRAMMING. (2) REGIONS AND INEQUALITIES

Starter activity: In your notebook, work through Example 5 on page 123-4. (The book uses colour to show the region which does not satisfy an inequality. You can do this instead by cross-hatching just a fringe of the non-satisfying region, as below).

linearprogramming-crosshatch

Activity

Ex.6B Q.1

Activity

Ex.6A Q.2-6

LESSON 20: HOW TO USE LINEAR PROGRAMMING. (3) OBJECTIVE LINE AND CHOOSING-VERTEX METHODS

Starter activity: In your notebook:

  • draw the diagram for example 7 on page 128 of your textbook
  • use a ruler to draw an objective line for the problem of maximising 2x+y, somewhere over on the right of the diagram, well outside the feasible area
  • aligning a non-hypotenuse side of a set square with the the objective line you’ve drawn
  • place a ruler under the other non-hypotenuse side of the set square
  • keeping the ruler fixed, slide the set square down it to the left (yes, slide the set square, not the ruler as pictured in the book)
  • stop when the edge of the set square just touches the feasible region
  • write down the value of x and y there. Check against p.130 in the textbook

Activity

Write in your notebook definitions of:

  • constraint
  • feasible region
  • objective function
  • objective line

in the sense that they’re used in linear programming.

Activity

Ex.6A Q.2-4

Extra: Ex.6A Q.5-7

Ex.6C Q.1a and 1b

Activity

Draw the diagram for Example 11 (page 135) in your notebook, and follow the instructions there to find the optimal value by vertex testing.

Activity

Ex.6C Q.1c and 1d

Ex.6C Q.2-5

Extra: Ex.6C Q.6-7

LESSON 21: HOW TO USE LINEAR PROGRAMMING. (4) HOW TO DO IT WHEN YOU HAVE TO HAVE A WHOLE-NUMBER (INTEGER) ANSWER

Starter activity:

Shut your notebook and your textbook. Write on a piece of paper definitions of:

  • constraint
  • feasible region
  • objective function
  • objective line

in the sense that they’re used in linear programming.

Pass your paper to your right, and mark the answers from your neighbour on the left.

Activity

In your notebook, under the heading “Integer values”, work through Example 13 on pages 141 and 142.

Activity

The textbook’s Method 1 (page 142) is easier than Method 2. Draw a new diagram for Example 14 (page 143) so that you can use Method 1 for it instead of Method 2. It looks like this:

integersolutions

Click here to download pdf.

Activity

Ex.6D Q.1-6

LESSON 21: HOW TO USE LINEAR PROGRAMMING. (5) MAKING SURE WE’VE GOT IT RIGHT

Starter activity: the same as lesson 20.

Shut your notebook and your textbook. Write on a piece of paper definitions of:

  • constraint
  • feasible region
  • objective function
  • objective line

in the sense that they’re used in linear programming.

Pass your paper to your right, and mark the answers from your neighbour on the left.

Activity

Ex.6E Q.1-5

Extra: Ex.6D Q.6-8