CS341 Lecture Notes - Merge Sort, Binary Search Algorithm, Dont

49 views14 pages

lemoncoyote675

16 Oct 2011

School

University of Waterloo

Department

Computer Science

Course

CS341

Professor

Forbes Burkowski

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

Solving recurrences: method 1: recursion trees, method 2: master theorem. Prove a general theorem covering a wide variety of recurrences. Apply the theorem in cookbook fashion: method 3: guessing and checking method. // base case: 1 element is always sorted if (l = r) then return; m := (l + r)/2; // we need to sort both subsequences lm, m+1r merge_sort(l, m); merge_sort(m + 1, r); // finally: merge the two sorted sequences merge(l, m, r); In the previous code we used a merge function: A[k] := l[i]; i := i + 1; k := k + 1; else. A[k] := r[j]; j := j + 1; k := k + 1; 1 we display the computation in the form of a tree (one node for each time the function is invoked). Label each node in the tree with the combine time cost incurred at that node. Leaves are labeled with base case cost t(0).

Related Questions

Recursion Question 5. In the following question, you will be asked to program the following using recursion. If you have an iterative solution, you may use it, but the most you can get for the question will be half credit. (5) points) Consider the following mathematical function h which operates on integers. (1, if n < 2 h(n) = n(n-1) +n if n > 2 and n is even han -2) +2*n if n > 2 and n is odd In Java, use recursion to write a method h which takes as input an int n and returns h (n). public static int h(int n) {

3. As seen in Assignment #5 of EECS1520, Excel can be used to simulate physiological processes like thyroxine conversion in the liver. In these simulations the value of the time dependent variables, like the amount of thyroxine in the liver, is often defined using the value of the same variable from an earlier time step. This type of relation where each further term of the sequence is defined as a function of the preceding terms is called: a) backward relation b) Forward relation c) Recurrence relation x d) Bidirectional relation e) None of the above

3. Consider the following method, which returns the number of times the parameter String word occurs in the parameter array wordArray: public static int countOccurrences (String[] wordArray, String word) { int result; result = 0; for (int i = 0; i < wordArray.length; i++) { if (wordArray[i] == word) { result = result + 1; return result; Unfortunately, the above method contains a bug. This bug causes the method to return 0 instead of the expected value of 2 when it is called in the following code fragment: String[] animalism = { new String ("four"), new String ("legs"), new String ("good"), new String ("two"), new String ("legs"), new String ("bad") }; int count = count Occurrences (animalism, "legs"); System.out.println("Number of occurrences: " + count); Describe what the problem is, and suggest a simple way to fix it. BE BRIEF; overly long answers will be grounds for mark deductions.

CS341 Lecture Notes - Merge Sort, Binary Search Algorithm, Dont

Document Summary

Get access

Related Documents

CS341 Lecture Notes - Merge Sort, Quicksort, Binary Search Algorithm

ACO 101 Study Guide - Final Guide: Loop Invariant, Metic, Liquid Oxygen

H Lecture Notes - Lecture 3: Sorting Algorithm, Quicksort, Merge Sort

Related Questions