Algorithms for graphs 5

Long term plan unit:

School:

Data:

Teacher’s name:

Class:

The number of attendees:

absentees:

Lesson theme

Algorithms on graphs 

Learning objectives that are achieved in this lesson (Subject Programme ref)

Implementation of search algorithms for graphs to solve the practical tasks

Lesson objectives

Complete program for finding the shortest path using Dijkstra algorithm

Evaluation criteria

Knowledge

·     Know what the adjacency matrix is

Comprehension

·     Describe the shortest path algorithm

Application

·     Complete program for finding the shortest path using Dijkstra algorithm

Language objectives

Learners able to …

·         State what is the shortest path in graph representation

·         Describe the search process in shortest path algorithm

Vocabulary and terminology specific to the subject:

Adjacency matrix, adjacency list,  initial node, path, root, vertices, edge, weighted graph, shortest path

Useful expressions for dialogs and letters:

Well, the Dijkstra algorithm is used when… .

For example, in C# there is Main  …. .

Obviously, finding the shortest path between initial node and ….

Cultivating values

collaboration, mutual respect, academic honesty, perseverance, responsibility, lifelong learning

Cross curricular links

English, Math

Prior knowledge

Intro to graphs

During the classes

Planned stages of the lesson

Planned activities in the classroom

Resources

Beginning

5 min

1.Greetings

Starter

1.      Teacher presents the question to revise previous lesson knowledge

2.      Teacher introduces topic and learning objectives

3.      Students make their own evaluation criteria

4.      Useful language pieces

Slides 1-4

Middle

10 min

20 min

3 min

Task 1. Students add the weight (distance) to given graph and create the new adjacency matrix for weighted graph

Teacher gives feedback and comments when necessary

Task 2. (Handout 1)

(P) Students are given the codes of Shortest Path In Graph – Dijkstra’s Algorithm. Each member of the pair has different version of algorithm implementation in C# code.

Students have to:

·         There are missing points in those codes, so students must to complete the codes.

·         Create the adjacency matrix for the new input for program to completely understand the Dijkstra’s Algorithm.

Note: considering the complexity and size of Dijkstra’s Algorithm implementation in programming, students are given functional, tested code.

Differentiation

Smart students help others

Peer Assessment

Students assess each other’s code according to given descriptors.  

Teacher gives feedback when necessary

Summary

Teacher provides questions for enforcement of lesson knowledge

Slides 5

Appendix 1

Slide 6

Slides 7-8

End

   2 min

Reflections

Blob tree

Slide 9

Differentiation - how do you plan to provide more support? What tasks do you plan to put before more able learners?

Evaluation - how do you plan to check the level of mastering the material by learners?

Health and safety practices

Дифференциация может быть выражена в подборе заданий, в ожидаемом результате от конкретного ученика, в оказании индивидуальной поддержки учащемуся, в подборе учебного материала и ресурсов с учетом индивидуальных способностей учащихся (Теория множественного интеллекта по Гарднеру).

Дифференциация может быть использована на любом этапе урока с учетом рационального использования времени.

Use this section to record the methods that you will use to assess what students have learned during the lesson.

Health-saving technologies.

Used body and physical exercises.

Points applied from the Safety Rules in this lesson.

Reflection on the lesson

Were the goals of lesson/ learning objectives realistic?

Have all the students reached the LO?

If not, why?

Is the differentiation done correctly in the lesson?

Were the time stages of the lesson sustained?

What were the deviations from the lesson plan and why?

Use this section to reflect on the lesson. Answer the most important questions about your lesson from the left column.

Overall assessment

What two aspects of the lesson went well (think about both teaching and learning)?

1:

2:

What could help improve the lesson (think about both teaching and learning)?

1:

2:

What I found during the lesson related to the class or the achievements / difficulties of individual students, what should I look for in subsequent lessons?