Difference between revisions of "D1"
(→Revision) |
(→Revision) |
||
| Line 15: | Line 15: | ||
[[Category: Module]] | [[Category: Module]] | ||
[[File:Revision_quiz_-d1_q2.pptx]] | [[File:Revision_quiz_-d1_q2.pptx]] | ||
| + | [[File:Revision_quiz_-_Mon.pdf]] | ||
Revision as of 09:00, 11 July 2014
Contents
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
