comp 410 final exam study questions and answers UPDATED 2024

load lambda - how full the table currently is foo(N-1) time complexity - O(N) foo(N-1) - foo(N-2) - O(2^N) foo(foo(N-1)) - O(2N) or O(N) stable sort that is O(NlogN) worst case - merge sort unstable sort that is O(NlogN) worst case - heap sort sort algorithm that is O(N) worst case - bucket sort traveling salesman problem - no efficient solution is known find a Hamiltonian path in a graph - no efficient solution is known complete graph with 12 vertices - dense graph find a minimum spanning tree for a graph - is efficiently solvable halting problem - no solution is possible graph isomorphism problem - no efficient solution is known graph formed from the circuits in a VLSI design (millions of transistors as nodes, edges as wire connections between them) - sparse graph Euler path # of odd vertices - 2 Euler path begins - with one odd node and ends at other odd node Euler path passes - through every edge once Euler circuit # of odd vertices - 0 Euler circuit begins - and ends at same vertex A graph that is already a tree has no minimum spanning tree - false A complete graph is always planar - false if the number of nodes in a tree is an exact power of 2, then that tree is a bi-partite graph - true if the number of nodes in a tree is odd then that tree is a bi-partite graph - true every graph that is a tree has no euler path - false careful programming can produce a hash function that will work well for all data types - false carefully programmed, quicksort is a stable sort algorithm - false carefully programmed, insertion sort is a stable sort algorithm - true the splay function in a splay tree always shortens the longest path by at least 1 - false in a balanced avl tree, the shortest path an the longest path differ by at most 1 - false hamiltonian path - contains each vertex once