D1

Algorithms

• Idea of an algorithm and implementation by flowchart
• Bin packing (first fit, first fit decreasing, full bin)
• Bubble sort
• Quick sort
• Binary search

Critical Path Analysis

• Modelling of a project by an activity network, from a precedence table
• Completion of precedence table for a given activity network
• Algorithm for finding the critical path
• Total float. Gantt (cascade) charts. Scheduling

Linear Programming

• Formulation of linear programming problems
• Solution of two variable linear programming problems by ruler or vertex methods
• Consideration of problems with integer solutions

Matchings

• Use of bipartite graphs for modelling matchings
• Complete matchings and maximal matchings
• Algorithm for obtaining a maximum matching

Networks

• The minimum connector (minimum spanning tree) problem
• Prim's algorithm (on graph or on matrix)
• Kruskal's algorithm
• Dijkstra's shortest path algorithm

Route Inspection

• Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex. The network will have up to four odd nodes

Revision

File:Revision quiz -d1 q2.pptx

File:Revision quiz - Mon.pdf