Decision 1

Description

Decision 1 Mind Map
Joseph McAuliffe
Mind Map by Joseph McAuliffe, updated more than 1 year ago
Joseph McAuliffe
Created by Joseph McAuliffe about 8 years ago
33
2

Resource summary

Decision 1
  1. Chapter 1 ~ Algorithms
    1. Following instructions
      1. Flow chart
        1. Start/End
          1. Instruction
            1. Decision
            2. Sorts
              1. Bubble
                1. Compare adjacent items
                  1. "Passes"
                  2. Quick
                    1. Pivots to create sub-lists
                      1. (n+1)/2 and round up if necessary to find pivots
                  3. Binary Search
                    1. Search an ordered list
                      1. Select middle item using (n+1)/2 and round up if necessary
                        1. Consider it compared to value searching for
                      2. Bin Packing
                        1. First-fit
                          1. In order given
                            1. Quick but not likely to lead to a good solution
                            2. First-fit decreasing
                              1. With a list in descending order
                                1. Fairly good solution but not always optimal
                                2. Full-bin
                                  1. Uses observation to fill bins
                                    1. Good solution but difficult, especially with lots of numbers
                                3. Chapter 2 ~ Graphs and Networks
                                  1. Points - Nodes/Vertices
                                    1. List is called the vertex set
                                    2. Lines - Arcs/Edges
                                      1. If numbers associated, it is a weighted graph or network
                                        1. List is called the edge set
                                        2. Terms: Subgraph, Degree/Valency/Order, Path, Walk, Cycle/Circuit
                                          1. Connected, Loop, Simple Graph, Directed Edges, Digraph
                                            1. Trees/Spanning Tree
                                              1. (Complete) Bipartite and Complete graphs
                                                1. Isomorphic graphs
                                                  1. Adjacency and distance matrices
                                                  2. Chapter 3 ~ Algorithms on Networks
                                                    1. Minimum Spanning Tree (no cycles)
                                                      1. Kruskal's
                                                        1. Using ascending weights
                                                        2. Prim's
                                                          1. Least weight from chosen vertex
                                                            1. Easily done with a distance matrix
                                                        3. Dijkstra's Alorithm
                                                          1. Shortest path between two vertices
                                                            1. Select smallest working value
                                                              1. Work backwards to find path
                                                              2. Chapter 4 ~ Route Inspection (Chinese Postman)
                                                                1. Is a graph traversable?
                                                                  1. If all of the valencies in a graph are even, the that graph is Eulerian and therefore traversable
                                                                    1. If the graph has just two valencies that are odd, then the graph is semi-Eulerian. In this case, the start and finish points will be the two vertices with odd valencies
                                                                      1. A graph is not traversable if it has more than two odd valencies
                                                                      2. Finding the shortest route in a network
                                                                        1. For semi-Eulerian graph, the shortest path between the two odd vertices will have to be repeated
                                                                          1. Algorithm
                                                                            1. 1 ~ Identify any vertices with odd valency
                                                                              1. 2 ~ Consider all possible pairings of these vertices
                                                                                1. 3 ~ Select the complete pairing that has the least sum
                                                                                  1. 4 ~ Add a repeat of the arcs indicated by this pairing to the network
                                                                          2. Traversable ~ sum of each arc's weight will be the weight of the network
                                                                          3. Chapter 5 ~ Critical Path Analysis
                                                                            1. Precedence Table/Dependence Table
                                                                              1. Shows what must be completed for an activity to start
                                                                                1. Used to create activity network
                                                                                  1. 0 node ~ source node
                                                                                    1. Last node ~ sink node
                                                                                      1. Often can take a couple of times to get layout correct
                                                                                    2. Dummies
                                                                                      1. Each activity must be uniquely represented
                                                                                        1. C depends on A but D depends on A and B
                                                                                        2. Early and Late event times
                                                                                          1. Early ~ use largest number
                                                                                            1. From a forward pass/forward scan
                                                                                            2. Late ~ use smallest number
                                                                                              1. From a backward pass/backward scan
                                                                                              2. Total float = latest finish time - duration - earliest start time
                                                                                                1. Cascade (Gantt) Charts
                                                                                                  1. Shows time leeway
                                                                                                    1. Dotted box represents float
                                                                                                      1. Look halfway before to see how many activities
                                                                                                        1. Consider float
                                                                                                    2. Critical activities
                                                                                                      1. Change to time would impact overall time
                                                                                                        1. At each node, early event time = late event time
                                                                                                        2. Critical path
                                                                                                      2. Chapter 6 ~ Linear Programming
                                                                                                        1. Chapter 7 ~ Matchings
                                                                                                          Show full summary Hide full summary

                                                                                                          Similar

                                                                                                          The Weimar Republic, 1919-1929
                                                                                                          shann.w
                                                                                                          Forms of Business Ownership Quiz
                                                                                                          Noah Swanson
                                                                                                          TYPES OF DATA
                                                                                                          Elliot O'Leary
                                                                                                          Bowlby's Theory of Attachment
                                                                                                          Jessica Phillips
                                                                                                          BELIEVING IN GOD- UNIT 1, SECTION 1- RELIGIOUS STUDIES GCSE EDEXCEL
                                                                                                          Khadijah Mohammed
                                                                                                          Edexcel Biology chapter 1
                                                                                                          Anna Bowring
                                                                                                          Biology Unit 1
                                                                                                          hannahsanderson1
                                                                                                          A Level Chemistry Unit 1 - Organic Chemistry
                                                                                                          charlottehyde
                                                                                                          Unit 1: Business Studies GCSE
                                                                                                          Libby Rose
                                                                                                          MATTERS OF LIFE AND DEATH - UNIT 1, SECTION 2 - RELIGIOUS STUDIES GCSE EDEXCEL
                                                                                                          Khadijah Mohammed
                                                                                                          Globalisation Case Studies
                                                                                                          annie