Please refer to the resource box on the right to download the "Stacks.pdf, Queues.pdf and Stacks and Queues.pdf".
Please refer to the additional notes to reinforce your understanding of
1) Stacks
2) Queues
For Stacks and Queues, you will need to know
1) how to create a stack using Array or Link List;
2) how to create a linear queue using Array or Link List;
3) how to create a circular queue using Array or Link List;
4) the differences between stack and queue
Sunday, September 6, 2009
Sunday, August 23, 2009
Lesson 5 Summary
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
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
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.
Saturday, July 25, 2009
Lesson 1 Summary
Please refer to the resource box on your right and download the Lesson 1 Concept (Powerpoint), Java class files (Person.java, Student.java, MonashStudent.java) and Java driver class files (StudentApp.java, StudentArrayApp.java, MonashStudentApp.java).
[ Lesson 1 Concept Powerpoint ]
Lesson 1 Concept illustrates the context in example 1 and example 2.
[ Example 1 ]
In example 1, we describe inheritance using Person class, Student class.
Person -> Student
Student class inherits the attributes of Person class using the "extends" keyword.
The StudentApp.java is a driver class that is used to demonstrate object instantiation as well as concept elucidation.
[ Example 2 ]
In example 2, we describe polymorphism in inheritance using Method overriding.
Person -> Student -> MonashStudent
MonashStudent inherits all the methods and attributes from the Student class which inturn inherits from Person class.
MonashStudentApp.java is the driver class that articulate method overriding and polymorphism. The methods that are overridden are getGpa and setGpa.
In method overriding, we preserve the method signature but change the logic (content) in the method body.
[ Others ]
We have also went through a short session on Array of objects. You can recall this in StudentArrayApp.java.
[ Notes ]
In the next lesson, we will be talking about protected and how can protected allow the derived class to access the attributes in the base class.
Super class = Parent class = Base Class
Sub class = Child class = Derived Class
We use the "super" keyword to initialise the base class' attributes via the derived class constructor. The "super" keyword is also used to reference to base class method.
usage: super.getGpa();
For a better and clearer example on polymorphism, please visit http://en.wikipedia.org/wiki/Polymorphism_in_object-oriented_programming#Java
[ Lesson 1 Concept Powerpoint ]
Lesson 1 Concept illustrates the context in example 1 and example 2.
[ Example 1 ]
In example 1, we describe inheritance using Person class, Student class.
Person -> Student
Student class inherits the attributes of Person class using the "extends" keyword.
The StudentApp.java is a driver class that is used to demonstrate object instantiation as well as concept elucidation.
[ Example 2 ]
In example 2, we describe polymorphism in inheritance using Method overriding.
Person -> Student -> MonashStudent
MonashStudent inherits all the methods and attributes from the Student class which inturn inherits from Person class.
MonashStudentApp.java is the driver class that articulate method overriding and polymorphism. The methods that are overridden are getGpa and setGpa.
In method overriding, we preserve the method signature but change the logic (content) in the method body.
[ Others ]
We have also went through a short session on Array of objects. You can recall this in StudentArrayApp.java.
[ Notes ]
In the next lesson, we will be talking about protected and how can protected allow the derived class to access the attributes in the base class.
Super class = Parent class = Base Class
Sub class = Child class = Derived Class
We use the "super" keyword to initialise the base class' attributes via the derived class constructor. The "super" keyword is also used to reference to base class method.
usage: super.getGpa();
For a better and clearer example on polymorphism, please visit http://en.wikipedia.org/wiki/Polymorphism_in_object-oriented_programming#Java
Using JGRASP to edit and compile my Java program
JGRASP is a lightweight integrated development environment software that allows one to edit and compile your Java program at ease. I strongly encourage you to get a copy of this software at http://www.jgrasp.org/.
In order for JGRASP to work properly, you will need to install JDK 5 (1.5) from http://java.sun.com/javase/downloads/index_jdk5.jsp.
Set up the Java development environment in week 1 of this semester and this will help you to pave the way for success in DSAG.
In order for JGRASP to work properly, you will need to install JDK 5 (1.5) from http://java.sun.com/javase/downloads/index_jdk5.jsp.
Set up the Java development environment in week 1 of this semester and this will help you to pave the way for success in DSAG.
Subscribe to:
Comments (Atom)
