# CO522 Algorithms, Data Structures and Complexity

 If a list is unordered, then our algorithm will be... Quadratic If a list is ordered, then our algorithm will be... Linear List the Disadvantages of a Binary Search Tree Slower to insert nodes than other algorithmsIt can be very slow to search through if the tree has a large height. List the Advantages of a Binary Search Tree Very fast search (If the height of the tree is small).Orders nodes when they are added to the tree. List the disadvantages of a Hash Table A hash code may be inaccurate in grouping nodes dependant on the hashing algorithm used.Entities in the table are unorderedCan become inefficient when there are many hash collisions List the advantages of a Hash Table Very fast when working with large amounts of data!Groups similar hash codes together which immediately eliminates large portions of the data to search through. Explain the specification that makes a tour an Euler Tour? Every edge must be used once and only once.The graph is connected (All nodes are connected)You must finish at the same node as you started.Each node must have an even number of edges connected to it. Describe Hierholzers algorithm for finding a Euler Tour If G is not connected, or if G has any node with odd degree then FAILChoose a node and construct any closed trail around that nodeRepeat until the trail is a Euler Tour:Choose a node in the visited set that has unvisited edges and construct a closed trail using unvisited edgesAdd that trail to the larger trail, by inserting it into the correct placeFinaltrail is our Euler Tour What are the three types of connections for graphs? ConnectedBi-ConnectedUnconnected Explain the difference between a connected graph and a bi-connected graph Connected graph - A graph where every node can be reached by travelling along the edges of the graph consistently.Bi-Connected Graph - A graph where every node can be reached and has at least two connections to other nodes. Explain the difference between an unconnected graph and a connected graph Connected graph - A graph where every node can be reached by travelling along the edges of a graph consistently.Unconnected graph - A graph where only some nodes can be reached by travelling along the edges of a graph consistently. Describe the Union-Find data structure Union - adding a new edge to the graph, and the data structure        –If the nodes share the same root do nothing        –Otherwise, attach the root of one as a child of the root of the otherFind - test if two nodes are connected        –Two nodes are connected if they share the same root        –If they share different roots they are unconnected Which out of Quicksort and Mergesort are best at sorting Arrays? Quicksort Which out of Quicksort and Mergesort are best at sorting Linked Lists? Mergesort Describe the process of a quicksort algorithm. Partition the array, placing higher figures at the end and lower figures at the front (based on a pivot)Recursively call this on the two new divisions and their divisions after etc... How can you improve the quicksort algorithm? Sort shorter partitions (< 5 say) Remove recursionUse the median of the first last and middle elements as the pivot. Name the three fields needed for a single Linked List object (Node). ID (Value or String)Data (user-defined)Next (Pointing to next Node object in list) Explain the process of a mergesort algorithm. Recursively halve the list into sub-lists until we are left with many pairs of Nodes. Swap the values of these lists into the correct order.Merge the lists back together again. What is the answer to the equation... a & b where a = 000111 b = 000101 000101 = 5 (denary) What is the answer to the equation... a & b where a = 00000110 b = 01111010 00000010 = 2 (denary) What does left-shifting in a binary number represent? B) Multiplication What is the answer to this equation... a | b where a = 00100100 b = 01101010 01101110 = 110 (denary) What is the answer to this equation... a | b where a = 00000101 b = 00001001 00001101 = 13 (denary) What do these bit operators represent... &     |     !     ^ & = AND|  = OR!  = NOT^ = XOR What is graph isomorphism? Isomorphism is graph equality.For them to be equal, they must have the same number of nodes and edges, and they must be connected in the same way. Describe how an Edge list looks when comapring a graph and compare your imagined image to the answer ACCBBA Describe how an Adjacency Matrix looks when displaying a graph and compare your imagined image to the answer ||| 1 2 3 4------------1 | 0 1 1 02 | 1 0 0 03 | 0 0 1 04 | 1 0 0 0 Describe how an Object Model looks when displaying a graph and compare your imagined image to the answer Nodes       Edgesn1:A         e1:n1 n2 label Xn2:B         e2:n2 n3 label Yn3:C         e3:n3 n4 label Xn4:D         e4:n4 n1 label Q Describe how a set based schema looks when displaying a graph and compare you imagined image to the answer G = (N,E)N = {1,2,3,4}E = {(1,2),(1,3),(2,3),(3,4),(4,1)}w: E --> Integersw(1,2) = 3w(1,3) = 4w(2,3) = 1w(3,4) = 4w(4,1) = 1 In O-notation, what does O(1) time scale represent? Constant time i.e, the time never changes. No matter how large or small the program, no matter how complex or simple the architecture, the time is always the same. In O-notation, what does O(n) time scale represent? Linear In O-notation, what does O(n2) time scale represent? Quadratic In O-notation, what does O(n3) time scale represent? Cubic In O-notation, what does O(log(n)) time scale represent? Logarithmic (no base!) In O-notation, when do we use multiplication to represent the time for a program or group of statements to run? When a loop is present (iterative function) What is the difference between a fixed point number and a floating point number? A fixed point number looks like this: 765.34A Floating point number looks like:  7.6534e2A fixed point number has a general mantissa (sequence of numbers) and then arbitrary information as to where that decimal point belongs.A floating point number has a mantissa and an exponent. The exponent dictates where exactly the decimal point belongs. What is the formula to work out the actual number in a floating point number? m*b(e-k) Where m = MantissaWhere b = Base (Denary, Binary, Hex)Where e = ExponentWhere k = Length of mantissa How do you go about performing an add or subtract statement on two floating point numbers Line up points by shiftingPerform the operation (Add or Subtract)Round the answer to the required number of digitsShift, if necessary (normalise) How is breadth-first search implemented? a) FIFO b) LIFO a) FIFO How is depth-first search implemented? a) FIFO b) LIFO b) LIFO What does a spanning tree do? A spanning tree connects all the nodes in an undirected graph with the smallest number of edges What is a minimum spanning tree? A MST is a spanning tree of a weighted graph with the smallest sum of edge weights of all the possible spanning trees. How would we go about finding a minimum spanning tree using Kruskal's algorithm? Sort all the edges from smallest weight to largest. Work down the list adding edges that do not form a cycle!End when you have (N - 1) edges where 'N' is the number of nodes. Authorianholden ID212620 Card SetCO522 Algorithms, Data Structures and Complexity DescriptionCards for CO527 - Algorithms, Data Structures and Complexity Updated2013-05-16T13:53:09Z Show Answers