Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Decision > Vocab > Flashcards

Vocab Flashcards

1
Q

Algorithm

A

A finite sequence of step-by-step instructions carried out to solve a problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Trace table

A

Used to record the values of each variable as the algorithm is run

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Pros and Cons of First Fit Bin Packing

A

Pro: Quick and easy
Con: Is unlikely to generate the optimal solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Optimal Solution

A

A solution that cannot be improved upon

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Pros and Cons of First Fit Decreasing Bin Packing

A

Pro: Easy to implement; often generates a better solution than first fit.
Con: Doesn’t guarantee an optimal solution; the list first needs to be sorted into decreasing order which makes the problem more complex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Pros and Cons of Full Bin Packing

A

Pro: Usually generates the optimal solution.
Con: Difficult, especially with long lists.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Efficiency of an algorithm

A

A measure of the run-time of the algorithm and is normally proportional to the number of operations that need to be carried out.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Size of the problem

A

A measure of the complexity of a problem. In sorting algorithms, it is usually the number of elements in the list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Order of an algorithm (complexity)

A

A measure of the efficiency as a function of the size of the problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Graph

A

Consists of nodes/vertices that are connected by edges/arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Subgraph

A

A subgraph of G only contains edges and vertices that belong to G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Directed edges

A

Edges that have a direction associated with them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Digraph

A

A graph that contains 1 or more directed edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Weight

A

Number associated with an edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Weighted graph

A

A graph which only contains edges that have numbers associated with them (weights)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Degree/valency

A

The number of edges that are incident on a vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Odd vertex

A

A vertex of odd degree i.e. an odd number of edges is incident on it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Even vertex

A

A vertex of even degree, i.e. an even number od edges is incident on it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Euler’s Handshaking Lema

A

Every finite undirected graph has an even number of vertices of odd degree.
The sum of the valencies of all the vertices of a graph is equal to twice the total number of edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Path

A

A finite sequence of edges, where the end vertex of one edge is the start vertex of the next edge and no vertex appears more than once.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Cycle/Circuit

A

A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Simple graph

A

Contains no loops and there is at most 1 edge connecting a pair of vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Hamiltonian cycle

A

A cycle that passes through every vertex of a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Walk

A

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Tour

A

A walk that visits every vertex and returns to the start vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Trail

A

A walk where no edge is visited more than once

27
Q

Loop

A

An edge that starts and finishes at the same vertex

28
Q

Connected

A

Vertices are connected if there is a path between them. A graph is connected if every vertex is connected

29
Q

Tree

A

A graph with no cycles

30
Q

Spanning tree

A

A spanning tree of G is a subgraph of G that contains all of the vertices of G and is a tree

31
Q

Complete graph

A

Every vertex is connected to every other vertex exactly once. A simple graph

32
Q

Eulerian graph

A

Every vertex has even degree

33
Q

Semi-eulerian graph

A

Exactly 2 vertices have odd degree

34
Q

Eulerian cycle

A

Cycle that contains every edge of a graph exactly once

35
Q

Planar graph

A

A graph that can be drawn in a single plane such that no edges meet each other, except at vertices to which they are both incident.

36
Q

Isomorphic

A

Two graph that have the same number of edges and the degrees of the corresponding edges are the same.

37
Q

How to check that graphs are isomorphic

A

Write down the valencies of all vertices. Check pairings of valencies. i.e. all vertices in 1 graph must be connected to vertices that have the same valencies as on the 2nd graph

38
Q

Adjacency Matrix

A

Describes the number of arcs joining the corresponding vertices. Loops = 2; 0 in leading diagonal = no loops; symmetry in leading diagonal = no directed edges

39
Q

Distance matrix

A

Every entry corresponds to the weight of each arc. If no loops, dashes down leading diagonal. Dash = no edge

40
Q

Decision Variables

A

Numbers of each of the things that can be varied

41
Q

Objective

A

Aim of the problem

42
Q

Objective function

A

The objective of a problem written as an equation using the decision variables

43
Q

Constraints

A

Prevent you from using/making an infinite number of each of the things represented by the decision variables. Each one gives rise to 1 inequality.

44
Q

Feasible solution

A

Satisfies all the constraints

45
Q

Feasible region

A

Contains all possible feasible solutions

46
Q

Optimal solution

A

A feasible solution that meets the objective. There can be multiple

47
Q

Slack variable

A

Represents the difference between the amount of the resources available and the amount used

48
Q

Basic variable

A

Variables that don’t have a value of 0

49
Q

Non-basic variables

A

Variables that have a value of 0

50
Q

Basic solution

A

Feasible solution with no profit. i.e. all variables in objective function are non-basic variables

51
Q

Surplus variable

A

Represent the difference between the minimum amount of resource available and the amount used

52
Q

Artificial variable

A

Used to ensure that surplus variables are greater than or equal to 0.

53
Q

Source node

A

Represents the start of a project

54
Q

Sink node

A

Represents the end of a project

55
Q

Event

A

Completion of 1 or more activities

56
Q

Dummy Activity

A

Has 0 duration

57
Q

When to use dummies

A

1) To represent dependency

2) Each activity must be uniquely represented in terms of events.

58
Q

Early event time

A

The earliest time of arrival at the event allowing for the completion of all preceding activities

59
Q

Forward Pass

A

Calculates the early event times

60
Q

Late event time

A

The latest time that the event can be left without extending the time needed for the project.

61
Q

Backwards pass

A

Calculates the late event times

62
Q

Critical activity

A

Has 0 float, i.e. any delay in its duration or start will delay the project’s completion by the same amount of time.

63
Q

Critical Path

A

A path from the source node to the sink node which is formed entirely of critical activities.

64
Q

Resource Levelling

A

The process of adjusting start and finish times of activities in order to take into account the constraints of the resources.

Decision (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions