Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
Tour
A walk that visits every vertex and returns to the start vertex
26
Trail
A walk where no edge is visited more than once
27
Loop
An edge that starts and finishes at the same vertex
28
Connected
Vertices are connected if there is a path between them. A graph is connected if every vertex is connected
29
Tree
A graph with no cycles
30
Spanning tree
A spanning tree of G is a subgraph of G that contains all of the vertices of G and is a tree
31
Complete graph
Every vertex is connected to every other vertex exactly once. A simple graph
32
Eulerian graph
Every vertex has even degree
33
Semi-eulerian graph
Exactly 2 vertices have odd degree
34
Eulerian cycle
Cycle that contains every edge of a graph exactly once
35
Planar graph
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
Isomorphic
Two graph that have the same number of edges and the degrees of the corresponding edges are the same.
37
How to check that graphs are isomorphic
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
Adjacency Matrix
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
Distance matrix
Every entry corresponds to the weight of each arc. If no loops, dashes down leading diagonal. Dash = no edge
40
Decision Variables
Numbers of each of the things that can be varied
41
Objective
Aim of the problem
42
Objective function
The objective of a problem written as an equation using the decision variables
43
Constraints
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
Feasible solution
Satisfies all the constraints
45
Feasible region
Contains all possible feasible solutions
46
Optimal solution
A feasible solution that meets the objective. There can be multiple
47
Slack variable
Represents the difference between the amount of the resources available and the amount used
48
Basic variable
Variables that don't have a value of 0
49
Non-basic variables
Variables that have a value of 0
50
Basic solution
Feasible solution with no profit. i.e. all variables in objective function are non-basic variables
51
Surplus variable
Represent the difference between the minimum amount of resource available and the amount used
52
Artificial variable
Used to ensure that surplus variables are greater than or equal to 0.
53
Source node
Represents the start of a project
54
Sink node
Represents the end of a project
55
Event
Completion of 1 or more activities
56
Dummy Activity
Has 0 duration
57
When to use dummies
1) To represent dependency | 2) Each activity must be uniquely represented in terms of events.
58
Early event time
The earliest time of arrival at the event allowing for the completion of all preceding activities
59
Forward Pass
Calculates the early event times
60
Late event time
The latest time that the event can be left without extending the time needed for the project.
61
Backwards pass
Calculates the late event times
62
Critical activity
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
Critical Path
A path from the source node to the sink node which is formed entirely of critical activities.
64
Resource Levelling
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.
© 2025 Bold Learning Solutions. Terms and Conditions