Decision 1&2 definitions Flashcards
What is an algorithm?
A finite sequence of step by step instructions carried our to solve a problem
What do the different boxes in flow charts represent?
Oval : Start/ end
Rectangle: Instruction
Diamond: Decision
What is a trace table?
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
What is a bubble sort?
A type of sorting algorithm where adjecent items in alist are swapped if they are not in order until the list is sorted.
What is a working list?
A list where all comparisons are made
Whats is a sorted list?
A list containg all items that are in their final position
What is a quick sort?
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
What are the three bin-packing algorithms?
First-fit
First-fit decreasing
Full-bin
How does the first-fit algorithm work?
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
What is the lower bound for the number of bins needed?
An optimal solution (uses the least amount of bins) that cannot be improved upon.
How does the first-fit decreasing algorithm work?
Requires the item to be in descending order before applying the algorithm.
* Sort items in descending order
* Apply firt-fit algorithm to reordered list
How does the full-bin packing algoritm work?
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.
Advatages and disadvatages of first-fit
Adv: Quick to implement
Dis: It is not likely to lead to a good solution
Advatages and disadvatages of first-fit decreasing
Adv: You usually get a fairly good solution. Easy to implement.
Dis: You may not get optimal solution
Advatages and disadvatages of full-bin
Adv: Usually get good solution
Dis: Difficult to do, especially when the numbers are plentiful and awkward
What is the order of an algorithm?
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
What is a graph?
Consists of points(vertices or nodes) which are connected by lines (edges or arcs)
What is a weighted graph/network?
A graph that has a number associated with each edge
What is the vertex set of a graph?
List of all nodes
What is an edge set of a graph?
List of all edges
What is a subgraph?
Part of the original graph. A graph each of whose vertices and edges belong to the original graph
What is meant by the degree ( or valency or order) of a vertex?
Number of edges incident to it
What is a walk?
A route through a graph along edges from one vertex to the next
What is a path?
A walk in which no vertex is visited more than once.
What is a trail?
A walk in which no edge is visited more than once.
What is a cycle?
A walk where the start vertex is the same as the end vertex and no other vertex is visited more than once.
What is a Hamiltonian cycle?
A cycle that includes every vertex
What is a connected graph?
Two vertices are conncted if there is a path between them. A graph is connected if all vertices are connected
What is a loop?
An edge that starts and finishes at the same vertex
What is a simple graph?
Graph with no loops and at most one edge connecting any pair of vertices
What is a digraph?
A graph where the edges have directions associated with them
What is Euler’s Handhshaking lemma?
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.
What is a tree?
A connected graph with no cycles
What is a spanning tree?
Subgraph that includes all vertices of original graph and is also a tree
What is a complete graph?
A graph in which every vertex is directly connected by a single edge to each of the other vertices
What is an isomorphic graph?
Show the same information but are drawn differently
What is an adjecency matrix?
A matrix where each entry describes the number of edges joining corresponding vertices
What is a distance matrix?
A matrix where each entry represents the weight of the edges joining corresponding values.
What is a planar graph?
A graph that can be drawn in a plane such as that no two edges meet except at a vertex.
