Decision 1

Decision 1

1. Chapter 1 ~ Algorithms

   • Following instructions
   • Flow chart
     • Start/End
     • Instruction
     • Decision
   • Sorts
     • Bubble
       • Compare adjacent items
       • "Passes"
     • Quick
       • Pivots to create sub-lists
         • (n+1)/2 and round up if necessary to find pivots
   • Binary Search
     • Search an ordered list
     • Select middle item using (n+1)/2 and round up if necessary
       • Consider it compared to value searching for
   • Bin Packing
     • First-fit
       • In order given
       • Quick but not likely to lead to a good solution
     • First-fit decreasing
       • With a list in descending order
       • Fairly good solution but not always optimal
     • Full-bin
       • Uses observation to fill bins
       • Good solution but difficult, especially with lots of numbers

2. Chapter 2 ~ Graphs and Networks

   • Points - Nodes/Vertices
     • List is called the vertex set
   • Lines - Arcs/Edges
     • If numbers associated, it is a weighted graph or network
     • List is called the edge set
   • Terms: Subgraph, Degree/Valency/Order, Path, Walk, Cycle/Circuit
   • Connected, Loop, Simple Graph, Directed Edges, Digraph
   • Trees/Spanning Tree
   • (Complete) Bipartite and Complete graphs
   • Isomorphic graphs
   • Adjacency and distance matrices

3. Chapter 3 ~ Algorithms on Networks

   • Minimum Spanning Tree (no cycles)
     • Kruskal's
       • Using ascending weights
     • Prim's
       • Least weight from chosen vertex
         • Easily done with a distance matrix
   • Dijkstra's Alorithm
     • Shortest path between two vertices
     • Select smallest working value
     • Work backwards to find path

4. Chapter 4 ~ Route Inspection (Chinese Postman)

   • Is a graph traversable?
     • If all of the valencies in a graph are even, the that graph is Eulerian and therefore traversable
     • 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
     • A graph is not traversable if it has more than two odd valencies
   • Finding the shortest route in a network
     • For semi-Eulerian graph, the shortest path between the two odd vertices will have to be repeated
     • Algorithm
       • 1 ~ Identify any vertices with odd valency
         • 2 ~ Consider all possible pairings of these vertices
           • 3 ~ Select the complete pairing that has the least sum
             • 4 ~ Add a repeat of the arcs indicated by this pairing to the network
   • Traversable ~ sum of each arc's weight will be the weight of the network

5. Chapter 5 ~ Critical Path Analysis

   • Precedence Table/Dependence Table
     • Shows what must be completed for an activity to start
     • Used to create activity network
       • 0 node ~ source node
       • Last node ~ sink node
       • Often can take a couple of times to get layout correct
   • Dummies
     • Each activity must be uniquely represented
     • C depends on A but D depends on A and B
   • Early and Late event times
     • Early ~ use largest number
       • From a forward pass/forward scan
     • Late ~ use smallest number
       • From a backward pass/backward scan
     • Total float = latest finish time - duration - earliest start time
     • Cascade (Gantt) Charts
       • Shows time leeway
       • Dotted box represents float
       • Look halfway before to see how many activities
         • Consider float
   • Critical activities
     • Change to time would impact overall time
       • At each node, early event time = late event time
     • Critical path

6. Chapter 6 ~ Linear Programming

7. Chapter 7 ~ Matchings

Imagens e arquivos do mapa