Decision 1

Chapter 1 ~ Algorithms
1. Following instructions
2. Flow chart
  1. Start/End
  2. Instruction
  3. Decision
3. Sorts
  1. Bubble
    1. Compare adjacent items
    2. "Passes"
  2. Quick
    1. Pivots to create sub-lists
      1. (n+1)/2 and round up if necessary to find pivots
4. Binary Search
  1. Search an ordered list
  2. Select middle item using (n+1)/2 and round up if necessary
    1. Consider it compared to value searching for
5. Bin Packing
  1. First-fit
    1. In order given
    2. Quick but not likely to lead to a good solution
  2. First-fit decreasing
    1. With a list in descending order
    2. Fairly good solution but not always optimal
  3. Full-bin
    1. Uses observation to fill bins
    2. Good solution but difficult, especially with lots of numbers
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
  2. List is called the edge set
3. Terms: Subgraph, Degree/Valency/Order, Path, Walk, Cycle/Circuit
4. Connected, Loop, Simple Graph, Directed Edges, Digraph
5. Trees/Spanning Tree
6. (Complete) Bipartite and Complete graphs
7. Isomorphic graphs
8. Adjacency and distance matrices
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
2. Dijkstra's Alorithm
  1. Shortest path between two vertices
  2. Select smallest working value
  3. Work backwards to find path
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
  2. 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
  3. 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
  2. Algorithm
    1. 1 ~ Identify any vertices with odd valency
      1. 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
3. Traversable ~ sum of each arc's weight will be the weight of the network
Chapter 5 ~ Critical Path Analysis
1. Precedence Table/Dependence Table
  1. Shows what must be completed for an activity to start
  2. Used to create activity network
    1. 0 node ~ source node
    2. Last node ~ sink node
    3. Often can take a couple of times to get layout correct
2. Dummies
  1. Each activity must be uniquely represented
  2. C depends on A but D depends on A and B
3. 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
  3. Total float = latest finish time - duration - earliest start time
  4. Cascade (Gantt) Charts
    1. Shows time leeway
    2. Dotted box represents float
    3. Look halfway before to see how many activities
      1. Consider float
4. Critical activities
  1. Change to time would impact overall time
    1. At each node, early event time = late event time
  2. Critical path
Chapter 6 ~ Linear Programming
Chapter 7 ~ Matchings

Media attachments

28c1d65b-29fa-4864-82ec-f160e85812b6 (image/png)

Next up

Decision 1

Description

Resource summary

Media attachments

Similar

	Created by Joseph McAuliffe almost 9 years ago