Tutorial 5, CSE2304, Monash, Semester 1, 2006

Week 12, begins 22 May

Class: The tutorials are the primary vehicle for practising the more formal material of the unit. Prepare your answers to the questions before the tutorial! It will probably not be possible to cover all questions unless you have prepared them in advance. Note that the online versions of the tutorials, as available at the unit's home page, are the reference documents and may contain extra information and links.
Tutors: (i) The purpose of the tutorials is not to solve the practical exercises! (ii) The purpose is to check answers, and to discuss particular sticking points, not to simply make answers available.

Objectives: The tutorials give practice in problem solving, the specification and analysis of algorithms and data-structures, and mathematics and logic useful in the above.

1. Prepare your answer before the tute and bring it to the tute. The tutors will collect your answer to this tute question. It is optional to put your name or student-id on your answer.

   The unit organisation is described in the general pages

   [G1] (click) overall unit home page - who, what, when, books, past years, past exams, FAQ, etc.,

   [G2] 2006-specific page,

   [G3] plan, "learning objectives".

   The unit lectures are contained in

   [L1] abstraction, problem solving, abstract data types (ADTs) such as list, tree,

   [L2] list & tree ADTs, doing algebra on algorithms,

   [L3] algorithm verification, termination, correctness,

   [L4] examples of algorithm verification on familiar sorting algs., relation of alg. & its design to its proof,

   [L5] priority-Q & heap sort, relation to selection sort,

   [L6] verification, merge- & quick-sort, divide & conquer (D+C) paradigm,

   [L7] a new problem - edit-distance (ED) - solution is an instance of the dynamic programming (DP) paradigm,

   [L8] Hirschberg's D+C ED alg. trades-off time-complexity(×2) for space-complexity,

   [L9] lookup table (dictionary), various,

   [L10] height-balance AVL-tree,

   [L11] trie & PATRICIA for strings,

   [L12] 2-3- & 2-3-4-trees lead up to B-trees,

   [L13] string searching algs.,

   [L14] graphs, various kinds of,

   [L15] path problems in graphs, another DP alg., greedy alg.,

   [L16] minimum spanning tree (MST) of a graph by Prim's alg. is a DP alg., relation to Dijkstra's alg.,

   [L17] MST of a graph by Kruskal's alg.,

   [L18] directed acyclic graphs (DAGs), topological sort, critical paths,

   [L19] suffix tree for string search (fast alg. to build is not examinable),

   [L20] basic numerical algorithms, numerical (in)accuracy,

   [L22] overview of linear-, binary- & n-ary-recursion,

   [L24] overview of design principles & paradigms, divide & conquer, dynamic programming, greedy, complexity hints.

   University  administration will have asked you to complete a web-based "unit evaluation" survey. The survey contains approximately 18 questions, Q1, Q2, ..., e.g.,

   Q1 "The learning objectives of this unit were made clear to me",

   Q2 "The unit enabled me to achieve the learning objectives", . . . , etc.,

   . . . , Q18.

   The pracs and tutes for the unit are in

   [T1], [T2] [T3] [T4] [T5], and [P1], [P2], [P3], [P4], [P5].

   Other supplementary online material is at

   [S1] algorithms web,

   [S2] bibliography.

   (i) Draw a graph which has the following vertices:

   {G1, G2, G3, L1, ..., L24, Q1, ..., Q18, T1, ..., T5, P1, ..., P5, S1, S2}.

   The graph has an edge from vertex u to vertex v just if v "depends on" u.

   For example,

   (a) L17 (Kruskal's MST algorithm) uses a priority-Q which is discussed in L5, so there should be an edge from the latter to the former;

   (b) there should be an edge from G3 to Q1 because the latter asks about (depends on) learning objectives which are in G3;

   (c) there should be an edge from Q1 to Q2 because they both refer to learning objectives and the former is more general;

   and so on.

   (ii) Is there a topological sort (TS) of your graph? If not, how few edges must be removed before there is a TS?

   (iii) Should there necessarily be a TS of such a graph for every unit?

   ---

   
   

2. In numerical integration of a function, f(), one does not always know in advance what size the interval should be for a fast and accurate result. One simple algorithmic solution to this problem is to start with some initial interval size and to keep halving it, thus doubling the number of intervals, nIntervals, until the result (integral) changes by no more than some small value epsilon.

   Write efficient C-code

   float adaptive(float f(float), float lo, float hi, int nIntervals, float epsilon)

   to use this strategy with the trapezoidal rule.

   
   

3. Given the following algorithm, how many times are (i) "base" and (ii) "body" executed for r(10)?

   void r(int n)
    { if( n > 0 )
       { r(n-1);
         body();
         r(n-1);
       }
      else
         base();
    }
   

   Why?

   (iii) and (iv) as above for r(n).

   
   

4. Here is a rough idea for a sorting algorithm:

   Move all the even elements, if any, to one end of the array and move all the odd elements, if any, to the other end of the array.

   Somehow[*], sort all the even elements and sort all the odd elements.

   Do whatever else is necessary, if anything, to ensure that the entire array is sorted.

   Design an algorithm from this rough idea and state its time and space complexity.

   [*] Note that even/odd involves testing the least significant bit. What about the next bit?