(5) SortingMidterm 1 Exam Study GuideThe Midterm Exam will be given Wednesday, 12 February 2003. Theexam counts for 10% of your final grade. The exam is closed book and closed notes The midterm 1 will consist of the following kinds of problems:(1) You will be asked to write an induction proof.(2) You will be asked to write a recurrence and initial cases for the complexity (in terms of a specifiedoperation) of some algorithm.(3) you will be given a pair of functions and asked to indicate which relationships between them areapplicable (little-o, big-O, big-theta, big-omega, little-omega).(4) Algorithm design and analysis- Be able to define or explain the terms order, big oh, big omega, big theta, L'Hopital's Rule,recurrence, optimal algorithm, lower bound, divide and conquer, and recursion. - Be able to solve recurrences using summation, recursion trees, or the master method. - Be able to prove one function is big Oh, big Theta, or big Omega of another(5) Sorting- Be able to trace and give the order and space requirements for all of the sorting algorithms wehave covered (e.g., Insertion Sort, Selection Sort)(6) Game of Life(7)Some basic of Graph theoryoDefinition and terminology e.g. degree of a node, leaf, child, parent, sibling, path, length of a path, levelor depth of a node, height of a node, height of a tree, ancestor vs. properancestor, descendent vs. proper descendent oPreorder, postorder, inorder of binary tree.oEuler trails,Eulerian graphs, Hamiltonian cycles and Hamiltonian graphs odefinitions oEuler’s Theorems on necessary and sufficient conditions for Euler trail Euler pathsSome sample Problems:1.2.3.4. When considering growth rates involving a logarithm, why the base of the logarithm is usually ignored?5. Decide whether the following graph is Eulerian or Hamiltonian?6. Give examples of graphs that contain: 1. neither an Eulerian tour (circuit) nor a Hamiltonian cycle; 2. an Eulerian tour but no Hamiltonian cycle; 3. a Hamiltonian cycle but no Eulerian tour; 4. both an Eulerian tour and a Hamiltonian cycle. 7. Fill in the following table, showing the worst, best, and average case running times for various sorting algorithms. sorting algorithm worst case best case average casebubble sort O(n2) insertion sort selection
View Full Document
![23FL20heap[1]](https://media.gradebuddy.com/documents/68167/f5ba0121-bfeb-4bce-8c70-9325cd50ffaf.png)
Unlocking...