Decision 1&2 definitions

Question 1

What is an algorithm?

Answer 1

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

Question 2

What do the different boxes in flow charts represent?

Answer 2

Oval : Start/ end
Rectangle: Instruction
Diamond: Decision

Question 3

What is a trace table?

Answer 3

A table the keeps track of the step at which you are at and the value of all variables at that step as the algorithm is run

Question 4

What is a bubble sort?

Answer 4

A type of sorting algorithm where adjecent items in alist are swapped if they are not in order until the list is sorted.

Question 5

What is a working list?

Answer 5

A list where all comparisons are made

Question 6

Whats is a sorted list?

Answer 6

A list containg all items that are in their final position

Question 7

What is a quick sort?

Answer 7

A sorting algorithm where:
* You select a pivot then split the items into two sublists
* One sublist contains items less than the pivot
* The other sublist contains items greater than the pivot
* You then select further pivots from within each sublist and repeat the process

Question 8

What are the three bin-packing algorithms?

Answer 8

First-fit
First-fit decreasing
Full-bin

Question 9

How does the first-fit algorithm work?

Answer 9

Works by considering items in the order they are given.
* Take the items in the given order
* Place each item in the first available bin that can take it.Start from bin 1 each time

Question 10

What is the lower bound for the number of bins needed?

Answer 10

An optimal solution (uses the least amount of bins) that cannot be improved upon.

Question 11

How does the first-fit decreasing algorithm work?

Answer 11

Requires the item to be in descending order before applying the algorithm.
* Sort items in descending order
* Apply firt-fit algorithm to reordered list

Question 12

How does the full-bin packing algoritm work?

Answer 12

Uses inspection to select items that will combine to fill bins.Remaining items are packed using first-fit algorithm.
* Uses observation to find combinations of items that will fill a bin.Pack these items firts.
* Any remaining items are packed using the first-fit algorithm.

Question 13

Advatages and disadvatages of first-fit

Answer 13

Adv: Quick to implement
Dis: It is not likely to lead to a good solution

Question 14

Advatages and disadvatages of first-fit decreasing

Answer 14

Adv: You usually get a fairly good solution. Easy to implement.
Dis: You may not get optimal solution

Question 15

Advatages and disadvatages of full-bin

Answer 15

Adv: Usually get good solution
Dis: Difficult to do, especially when the numbers are plentiful and awkward

Question 16

What is the order of an algorithm?

Answer 16

Tells you how the changes in the size of a problem affect the approximate time taken for its completion. Can be described as a function of its size

Question 17

What is a graph?

Answer 17

Consists of points(vertices or nodes) which are connected by lines (edges or arcs)

Question 18

What is a weighted graph/network?

Answer 18

A graph that has a number associated with each edge

Question 19

What is the vertex set of a graph?

Answer 19

List of all nodes

Question 20

What is an edge set of a graph?

Answer 20

List of all edges

Question 21

What is a subgraph?

Answer 21

Part of the original graph. A graph each of whose vertices and edges belong to the original graph

Question 22

What is meant by the degree ( or valency or order) of a vertex?

Answer 22

Number of edges incident to it

Question 23

What is a walk?

Answer 23

A route through a graph along edges from one vertex to the next

Question 24

What is a path?

Answer 24

A walk in which no vertex is visited more than once.

Question 25

What is a trail?

Answer 25

A walk in which no edge is visited more than once.

Question 26

What is a cycle?

Answer 26

A walk where the start vertex is the same as the end vertex and no other vertex is visited more than once.

Question 27

What is a Hamiltonian cycle?

Answer 27

A cycle that includes every vertex

Question 28

What is a connected graph?

Answer 28

Two vertices are conncted if there is a path between them. A graph is connected if all vertices are connected

Question 29

What is a loop?

Answer 29

An edge that starts and finishes at the same vertex

Question 30

What is a simple graph?

Answer 30

Graph with no loops and at most one edge connecting any pair of vertices

Question 31

What is a digraph?

Answer 31

A graph where the edges have directions associated with them

Question 32

What is Euler’s Handhshaking lemma?

Answer 32

In any undirected graph, the sum of dgrees of the vertices is equal to 2x the number of edges. As a consequence, the number of odd nodes must be even.

Question 33

What is a tree?

Answer 33

A connected graph with no cycles

Question 34

What is a spanning tree?

Answer 34

Subgraph that includes all vertices of original graph and is also a tree

Question 35

What is a complete graph?

Answer 35

A graph in which every vertex is directly connected by a single edge to each of the other vertices

Question 36

What is an isomorphic graph?

Answer 36

Show the same information but are drawn differently

Question 37

What is an adjecency matrix?

Answer 37

A matrix where each entry describes the number of edges joining corresponding vertices

Question 38

What is a distance matrix?

Answer 38

A matrix where each entry represents the weight of the edges joining corresponding values.

Question 39

What is a planar graph?

Answer 39

A graph that can be drawn in a plane such as that no two edges meet except at a vertex.