Brainscape's Knowledge GenomeTM

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


See full index

D1 > D1 > Flashcards

D1 Flashcards

1
Q

How do you find the lower bounds of a bin-pack?

A

Total of all number divided by bin size

- must round up

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

What are the advantages of First- fit bin packing?

A

quick to do

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

What are the disadvantages of First-fit bin packing?

A

not likely to lead to a good solution

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

What are the advantages of First-fit decreasing bin packing?

A
  • Usually a good solution

- Easy to do

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

What are the disadvantages of First-fit decreasing bin packing?

A
  • May not get get an optimal solution
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the advantages of Full bin packing?

A

Usually a good solution

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

What are the disadvantages of Full bin packing?

A

Difficult to do, especially when lots of numbers or awkward numbers are involved

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

What is the Hand-shaking lemma?

A

sum of all degrees = 2 x number of edges

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

How is Graph defined?

A

A graph consists of vertices [nodes] which are connected by edges [arcs].

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

How is Sub Graph defined?

A

A sub graph is a part of a graph.

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

How is Weighted Graph defined?

A

A graph in which there is a number associated with each edge [its weight].

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

How Degree of Valency/Order defined?

A

The number of edges incident to a vertex.

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

How is Path defined?

A

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

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

How is Walk defined?

A

A path in which you are permitted to return to vertices more than once.

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

How is Cycle/Circuit defined?

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
16
Q

How is Connected defined?

A

Two vertices are ‘connected’ if there is a path between them. A graph is connected if all its vertices are connected.

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

How is Loop defined?

A

An edge that starts and finishes at the same vertex.

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

How is Simple Graph defined?

A

A graph in which there are no loops and not more than one edge connecting any pair of vertices.

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

How is Digraph/Directed edges defined?

A

A graph in which the edges have a direction associated with them – the edges are known as directed edges.

20
Q

How is Tree defined?

A

A connected graph with no cycles.

21
Q

How is Spanning Tree defined?

A

A subgraph of a graph which includes all the vertices of the graph and is also a tree.

22
Q

How is Bipartite graph defined?

A

A graph consisting of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.

23
Q

How is Complete graph defined?

A

A graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, the connected graph is denoted kn.

24
Q

How is Complete bipartite graph defined?

A

A graph in which there are r vertices in set X and s vertices in set Y [denoted kr,s].

25
Q

How is Isomorphic graphs defined?

A

A graph showing the same information as another but which is drawn differently.

26
Q

How is Adjacency Matrix defined?

A

A matrix which records the number of direct links between vertices.

27
Q

How is Distance Matrix defined?

A

A matrix which records the weights on the edges. Where there is no weight, this indicated by ‘-.’

28
Q

How is Minimum Spanning Tree defined?

A

A spanning tree such that the total length of its arcs is as small as possible.

29
Q

What are the Differences between Kruskal’s and Prim’s Algorithm?

A
  1. Kruskal’s algorithm always starts with the arc of lowest weight while Prim’s can start at any node.
  2. Kruskal’s algorithm produces a MST in a ‘chaotic’ manner while Prim’s MST grows with linked arcs.
  3. Unlike Kruskal’s algorithm, you do not have to check for cycles with Prim’s algorithm.
  4. Prim’s algorithm can be applied to a distance matrix while Kruskal’s algorithm cannot.
30
Q

What is a Eularian graph?

A

All the valencies are even –> The graph is traversable

31
Q

What is a Semi-Eularian graph?

A

If precisely two valencies are odd and the rest are even –> it is semi-traversable

32
Q

How is Traversable defined?

A

it is possible to traverse (travel along) every arc just once without taking your pen from the paper

33
Q

Why must there always be an even (or zero) number of vertices with odd valency in every graph?

A
  • Each arc has two ends and so will contribute to two to the total sum of the valencies of the whole graph.
  • Therefore, the sum of the valencies is always even.
  • Therefore, vertices with an odd number of valencies must exist in pairs.
  • Therefore, there is always an even number of odd valencies
34
Q

How is Early Event time defined?

A

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

35
Q

How is Late Event Time defined?

A

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

36
Q

How is Critical Activity defined?

A

An activity where any increase in its duration results in a corresponding increase in the duration of the whole project i.e. it has a total float of zero.

37
Q

How is Critical Path defined?

A

A path from the source node to the sink node which entirely follows critical activities. It is the longest path contained in the network.

38
Q

How is Total Float defined?

A

The amount of time an activity may be delayed without affecting the duration of the project.

39
Q

What is the purpose of Dummy Activity?

A
  1. E.g. If activity D depends only on activity B but activity E depends on activities B and C.
    - To show dependency ( where subsequent activities do not depend on the same preceding activities)
  2. To enable the unique representation of activities in terms of their end events
40
Q

How do you find the lower bound of workers you need?

A

sum of all activity times/critical time of the project

41
Q

What are the two methods you can use to find the Optimal Solution?

A
  • Objective line method (ruler method)

- Vertex testing method

42
Q

How is Matching defined?

A

A matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y, in a bipartite graph.

43
Q

How is Maximal Matching defined?

A

A matching in which the number of arcs is as large as possible.

44
Q

How is Alternating Path defined?

A

A path starting at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately ‘not in’ or ‘in’ the initial matching.

45
Q

What is capacity utilisation of an arc?

A

is the ratio of the flow on the arc to its maximum capacity

D1 (1 decks)

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