1.4: Unit Summary

Last updated
Save as PDF

Page ID: 49344

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

This unit introduced the basic concepts of algorithm design and analysis and associated techniques. The need for analysing the time and space complexity of algorithms was articulated and the notations for describing algorithm complexity were presented. The unit further discussed the fundamental solution design methods as well as demonstrated each method using concrete examples. The problem solving methods included the iteration, recursion, recursive backtracking and dynamic programming.

Unit Assessment

Check your understanding!

Comparing performance of DP, Recursion and Iteration methods

Instructions

Consider the following iterative solution of the Fibonacci problem:

int iterativeFibonacci(int n) {
//iterative solution to the Fibonacci problem
//initialise base cases:
int previous = 1; // initially rabbit(1)‏
int current = 1; //initially rabbit(2)‏
int next = 1; // results when n is 1 or 2
//compute next Fibonacci values when n >= 3
    for (int i = 3; i <= n; i++) {
    //current is rabbit(i-1), previous is rabbit(i-2)‏
    next = current + previous; //rabbit(i)‏
    previous = current;
    current = next;
}// end for
return next;
} //end iterativeFibbonacci

Implement the iterative, recursive, and DP solutions for the Fibonacci problem and compare the time taken by each solution method for n=1000.

Answers

mailto:njulumi@gmail.com

Grading Scheme

As per the offering Institution discretion.

Unit Readings and Other Resources

The readings in this unit are to be found at course level readings and other resources.