Поделиться
Algorithms for graphs 5 - var2.docx
|
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
4 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 |
Theory Students watch video about Dijkstra’s Shortest Path applied to Graph data structure.
Task 1. After being introduced with its algorithm, students write a program for Dijkstra’s Shortest Path algorithm.
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
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? |
|||||||||||
Appendix 1 (handout 1)
namespace DijkstraAlgorithm
{
class Dijkstra
{
private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount)
{
int min = int.MaxValue;
int minIndex = 0;
for (int v = 0; v < verticesCount; ++v)
{
if (shortestPathTreeSet[v] == false && distance[v] <= min)
{
min = distance[v];
minIndex = v;
}
}
return minIndex;
}
private static void Print(int[] distance, int verticesCount)
{
Console.WriteLine("Vertex Distance from source");
_________________________________________________________________ // write here
Console.WriteLine("{0}\t {1}", i, distance[i]);
}
public static void DijkstraAlgo(int[,] graph, int source, int verticesCount)
{
int[] distance = new __________________________________;
bool[] shortestPathTreeSet = new bool[verticesCount];
for (int i = 0; i < verticesCount; ++i)
{
distance[i] = int.MaxValue;
shortestPathTreeSet[i] = false;
}
distance[source] = 0;
for (int count = 0; count < verticesCount - 1; ______________________)
{
int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount);
shortestPathTreeSet[u] = true;
for (int v = 0; v < verticesCount; ++v)
if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v])
distance[v] = distance[u] + graph[u, v];
}
Print(______________________________________);
}
static void Main(string[] args)
{
int[,] graph = {
{ 0, 6, 0, 0, 0, 0, 0, 9, 0 },
{ 6, 0, 9, 0, 0, 0, 0, 11, 0 },
{ 0, 9, 0, 5, 0, 6, 0, 0, 2 },
{ 0, 0, 5, 0, 9, 16, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 6, 0, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 16, 0, 2, 0, 1, 6 },
{ 9, 11, 0, 0, 0, 0, 1, 0, 5 },
{ 0, 0, 2, 0, 0, 0, 6, 5, 0 }
};
__________________________(graph, 0, 9);
}
}
}
Скачано с www.znanio.ru
![PathTreeSet[u] = true; for (int v = 0; v < verticesCount; ++v) if (!shortestPathTreeSet[v] &&](https://fs.znanio.ru/d5af0e/87/11/dbd7c78d510062bbbf0fb017bbbd1f2274.jpg)
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
