Lesson 2 Summary

Please refer to the Lesson 2 Resource box on the right to download the Binary Search, Big-Oh Notation and FindSmallestItemApp.java.

In this lesson, we focus on algorithm development and algorithm analysis.

[ Algorithm Development ]

We devise a simple algorithm to find the smallest item in a item list array. You can refer to the codes in FindSmallestItemApp.java.

We have done a brief walkthrough on the Maximum Contiguous Subsequence Sum Problem.
Please refer to lecture slide 12 for the detailed description of the problem. Your homework is to devise an algorithm and share it with the class in the next lesson. Looking forward to see your first algorithm for this module. =)

[ Algorithm Analysis ]

The different loop used defines different computation cost (overhead). Actual Algorithm computation cost is number of iterations multiply by loop overhead and algorithm overhead (logic + arithmetic operations).

Algorithm computation cost = No of iterations * Loop Overhead * Algorithm Overhead

In Lesson 2, we used algorithm analysis to estimate the amount of resource(time, space) required by an algorithm. The gist of algorithm analysis is to estimate the efficiency level and effectiveness level of the algorithm.

We used Big-Oh notation to describe the complexity and measure the computation cost of an algorithm. Please bear in mind that the computation cost as derived from Big-Oh is an estimated one and is often over-estimated.

Efficiency of Algorithm

Reducing the complexity (no of iterations) in an algorithm will greatly improve the efficiency of the algorithm.

Effectiveness of Algorithm

Improving the algorithm and accuracy/precision will help to improve the effectiveness of the algorithm.


[ Binary Search ]

Binary search is one type of algorithm that is commonly used in the computer science and engineering space. Please refer to the BinarySearch.ppt for better concept elucidation. Please also refer to the psuedocode and read Slide no 24 on the lecture slide for the Java code.