Please refer to the resource box on the right to download the "Linked List.pdf".
Please refer to the additional notes to reinforce your understanding of
1) Link List
2) Doubly Link List
3) Circular Link List
For link list, you need to know
1) How to develop a link list application in Java
2) Using diagrams/models to articulate link list
3) How to write psuedocodes or partial codes of link list operations
Sunday, August 23, 2009
Lesson 4 Summary
Please refer to the resource box on the right to download the "Sorting-1.pdf", "Sorting-2.pdf" and lastly "Sorting.pdf".
The sorting notes are complimentary to the existing notes you have from Monash University.
A sorting family tree has been illustrated and the following sorts have been articulated.
- Bubble Sort
- Selection Sort
- Insertion Sort
- Shell Sort
- Quick Sort
- Merge Sort
- Radix Sort
Please remember for each sorting algorithm, you need to know the following
1) Definition of Sort
2) Description of Sort
3) Algorithm Psuedocode/Java Code
4) Complexity Analysis of Sorting Algorithm
5) Optional (Illustrate the Sort using diagrams)
The sorting notes are complimentary to the existing notes you have from Monash University.
A sorting family tree has been illustrated and the following sorts have been articulated.
- Bubble Sort
- Selection Sort
- Insertion Sort
- Shell Sort
- Quick Sort
- Merge Sort
- Radix Sort
Please remember for each sorting algorithm, you need to know the following
1) Definition of Sort
2) Description of Sort
3) Algorithm Psuedocode/Java Code
4) Complexity Analysis of Sorting Algorithm
5) Optional (Illustrate the Sort using diagrams)
Saturday, August 8, 2009
Lesson 3 Summary
Please refer to the Resource box on the right to download the RecursionApp.java, DP.ppt, GreedyAlgo.ppt and lastly Complexity Analysis.ppt.
[ Recursion ]
Understand what is Recursion by looking at the RecursionApp.java.
Rule 1: Have a base case that can be solved without using recursion (Terminating condition must exist)
Rule 2: Make sure that the recursion work towards the base case (Move towards terminating condition)
Rule 3: Assumes that the recursion call works (Inductive hypothesis)
Rule 4: Do not duplicate effort/work by solving same instance of problem in another recursive function call
In lesson 2, we illustrate a normal binary search algorithm on slide 24(lesson 2).
In lesson 3, we illustrate a recursive binary search algorithm on slide 19(lesson 3).
*** Recursion is not necessarily efficient
*** Recursion will not necessarily produce shorter codes
[ Fibonacci ]
Fibonacci sequence is a classic example of recursion.
Fib(0) = 0 [base case]
Fib(1) = 1 [base case]
For all integers n > 1: Fib(n) = (Fib(n-1) + Fib(n-2)) [recursive definition]
Please visit wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number for better elucidation.
[ Divide and Conquer ]
Divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.
Use Fibonacci to explain divide and conquer.
public static long fibonacci( int n ){
if( n <= 1 )
return n;
else
return fibonacci( n-1 ) + fibonacci( n-2 );
}
The above code snipplet illustrates the use of disjoint recursive calls to divide and conquer a number problem.
[ Solution to Week 2 homework :: Maximum Contiguous Subsequence Sum Problem ]
- For the Recursive solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 280 of the textbook. See page 278 and 279 for background description.
- For the Cubic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 171 of the textbook.
- For the Quadratic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 174 of the textbook.
- For the Linear complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 176 of the textbook.
*** Remember that the simpler the complexity, the shorter the number of iterations and the more efficient the algorithm
[ Dynamic Programming ]
Will elaborate more in the next lesson. Meanwhile, please take a look at DP.ppt.
[ Greedy Algorithm ]
Will elaborate more in the next lesson. Meanwhile, please take a look at GreedyAlgo.ppt.
[ Complexity Analysis ]
Please look at Complexity Analysis.ppt to appreciate the following
- Definition of Algorithm
- Example (Linear Search, Binary Search)
- Complexity (Time Complexity)
- Big-Oh Notation
- Complexity Analysis
[ Measure time taken to process your Algorithm ]
To take a closer look at how to measure your algorithm processing time, please visit
http://nadeausoftware.com/articles/2008/03/java_tip_how_get_cpu_and_user_time_benchmarking#Timingataskusingwallclocktime
[ Recursion ]
Understand what is Recursion by looking at the RecursionApp.java.
Rule 1: Have a base case that can be solved without using recursion (Terminating condition must exist)
Rule 2: Make sure that the recursion work towards the base case (Move towards terminating condition)
Rule 3: Assumes that the recursion call works (Inductive hypothesis)
Rule 4: Do not duplicate effort/work by solving same instance of problem in another recursive function call
In lesson 2, we illustrate a normal binary search algorithm on slide 24(lesson 2).
In lesson 3, we illustrate a recursive binary search algorithm on slide 19(lesson 3).
*** Recursion is not necessarily efficient
*** Recursion will not necessarily produce shorter codes
[ Fibonacci ]
Fibonacci sequence is a classic example of recursion.
Fib(0) = 0 [base case]
Fib(1) = 1 [base case]
For all integers n > 1: Fib(n) = (Fib(n-1) + Fib(n-2)) [recursive definition]
Please visit wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number for better elucidation.
[ Divide and Conquer ]
Divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.
Use Fibonacci to explain divide and conquer.
public static long fibonacci( int n ){
if( n <= 1 )
return n;
else
return fibonacci( n-1 ) + fibonacci( n-2 );
}
The above code snipplet illustrates the use of disjoint recursive calls to divide and conquer a number problem.
[ Solution to Week 2 homework :: Maximum Contiguous Subsequence Sum Problem ]
- For the Recursive solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 280 of the textbook. See page 278 and 279 for background description.
- For the Cubic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 171 of the textbook.
- For the Quadratic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 174 of the textbook.
- For the Linear complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 176 of the textbook.
*** Remember that the simpler the complexity, the shorter the number of iterations and the more efficient the algorithm
[ Dynamic Programming ]
Will elaborate more in the next lesson. Meanwhile, please take a look at DP.ppt.
[ Greedy Algorithm ]
Will elaborate more in the next lesson. Meanwhile, please take a look at GreedyAlgo.ppt.
[ Complexity Analysis ]
Please look at Complexity Analysis.ppt to appreciate the following
- Definition of Algorithm
- Example (Linear Search, Binary Search)
- Complexity (Time Complexity)
- Big-Oh Notation
- Complexity Analysis
[ Measure time taken to process your Algorithm ]
To take a closer look at how to measure your algorithm processing time, please visit
http://nadeausoftware.com/articles/2008/03/java_tip_how_get_cpu_and_user_time_benchmarking#Timingataskusingwallclocktime
Saturday, August 1, 2009
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.
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.
Subscribe to:
Comments (Atom)
