Transcript abstract class Employee

ICS 202: Data Structures
Fall 2008-2009 (081)
Section 01: 10-10:50am, 24:116
Section 02: 9 - 9:50am, 24:174
Instructor: Dr. Wasfi G. Al-Khatib
Office: 22:133-1
Telephone: 1715
E-mail: [email protected]
Office Hours: SMW 11:00AM-1:00PM
or by appointment
Textbooks
1. “Data Structures and Algorithms in Java”,
2nd Edition, Adam Drozdek, Thomson
Learning, ISBN 0-534-49252-5.
2. “Data Structures and Algorithms with
Object Oriented Design Patterns in Java”,
Bruno R. Preiss, John Wiley & Sons, Inc.,
2000.
Course Objectives
• Introduce students to fundamental data
structures; their algorithms,
implementations and applications.
• Teach students how to analyze the
efficiency of the fundamental data
structures in terms of both time and space
so that they are able to decide what data
structure is suitable for a given problem.
Course Learning Outcomes
• After completion of this course, the student shall
be able to:
– Apply object oriented concepts (inheritance,
polymorphism, design patterns, etc.) in software
design.
– Implement various data structures and their
algorithms, and apply them in implementing simple
applications.
– To analyze simple algorithms and determine their
efficiency using big-O notation.
– To apply the knowledge of data structures to other
application domains like data compression and
memory management.
Topics (Tentative)
Topics of Coverage
Lecture Slides &
Text Book References
Review & Introduction to Design Patterns
Lectures 1-3, Preiss Chapter 5
Introduction to Algorithm Analysis
Lectures 4-6, Preiss Chapter 3, Drozdek Chapter 2
Review of Linked Lists
Lectures 7-8, Preiss Chapter 4, Drozdek Chapter 3
Review of Stacks & Queues
Lectures 9-10, Preiss Chapter 6, Drozdek Chapter 4
Recursion and Recursive Algorithms
Lectures 11-14, Slides, Drozdek Chapter 5
Tree Structures and their Applications
Lectures 15-23, Preiss Chapter 9, Drozdek Chapter 6
and 7, Heap Sort (Drozdek pg 484)
Graphs and Graph Algorithms
Lectures 24-31, Preiss Chapter 16, Drozdek Chapter 8
Hashing Techniques
Lectures 32-34, Preiss Chapter 8
Garbage Collection
Lecture 35, Preiss Chapter 13, Drozdek Chapter 12
Advanced Data Structures
Grade Distribution
Activity
Laboratory
Active Participation
Weight
20%
1%-5%
Four Home Works
15%
Five Quizzes
10%
n Pop Quizzes
EXAM 1: November 22, 2008,
Saturday 7:00-9:00pm
EXAM 2: January 10, 2009,
Saturday 7:00-9:00pm
FINAL EXAM: February 5, 2009,
Thursday at 7:30am
5%
15%
15%
20%
Attendance Policies (Lecture Only)
• Attendance will be checked each class.
• Unexcused Absences
–
–
–
–
–
The first four absences are FREE of charge.
The fifth absence is worth -2.5 of your maximum 100 total.
Each subsequent absence, up to the ninth absence, is worth -0.5.
The tenth absence will result in an automatic DN grade.
An unexcused absence can become an excused absence ONLY by an
official letter from the Dean of Student’s office.
• A bonus of 0.5 percentage point will be given for each “additional”
hour attended above the 43 hours. This shall come from the help
sessions conducted for the two major exams and the final exam.
• Bonus percentage points can be earned for active participation in
the course. This includes, but is not limited to, positive involvement
in electronic discussions on the course, and [possibly] attendance of
help sessions beyond regular class hours.
Notes
• Students are expected to be courteous toward the instructor,
the lab instructor and their classmates throughout the duration
of this course.
• All cell phones and pagers must be turned off during class
and exams.
• Hard copies of homework are due at the beginning of the first
class after the electronic submission deadline. No late
homework will be accepted. Discussing questions among
your classmates and on WebCT is highly encouraged.
Copying homework solutions from each other is NOT
permitted and will be considered CHEATING.
• Quizzes: 15-20 minutes. Each covers material given since the
last quiz or major exam.
• Pop Quizzes:  5 minutes. Each covers material given during
the same lecture.
Notes (Cont.)
• 24-Hour Policy: One has 24 hours to object to the
grade of a homework, [pop] quiz or a major from
the end of the class time in which the graded
exam/homework papers have been distributed. If
for some reason you cannot contact me within this
period, send me an email requesting an
appointment. The email should be sent within the
24-hour time period.
• Exams, homework and quizzes are generally
CHALLENGING.
• Check the WebCT course page regularly for
announcements and updates.
Important Dates
Activity
Date and Time
Place
Quiz 1
Wednesday October 22, 2008
In class
Quiz 2
Wednesday November 5, 2008
In class
Major 1
Saturday November 22, 2008 (7 - 9pm)
Eid Ul-Adhaa Break
Quiz 3
TBA
Wednesday December 3,2008 – Saturday December 13, 2008
Monday December 15, 2008
Lecture and Lab
Thursday December 18, 2008
(Saturday Replacement)
Quiz 4
Saturday December 27, 2008
Major 2
Saturday January 10, 2008 (7 - 9pm)
Quiz 5
Saturday January 24, 2008
Final Exam
Thursday February 5, 2008 at 7:30am
In class
In class/lab
In class
TBA
In class
TBA
Review of Object-Oriented Concepts in JAVA
• Object-Oriented Concepts supported by JAVA.
• Advantages of Object-Orientation.
• Inheritance.
• Abstract Classes.
• Interfaces.
• Review Questions.
Object-Oriented Concepts supported by JAVA
• Java provides explicit support for many of the fundamental ObjectOriented Concepts. Some of these are:
– Classification: Grouping related things together. This is
supported through classes, inheritance & packages.
– Encapsulation: Representing data and the set of operations on
the data as a single entity - exactly what classes do.
– Information Hiding: An object should be in full control of its
data, granting specific access only to whom it wishes.
– Inheritance: Java allows related classes to be organized in a
hierarchical manner using the extends keyword.
– Polymorphism: Same code behaves differently at different
times during execution. This is due to dynamic binding.
Advantages of Object-Orientation.
• A number of advantages can be derived as a result of these objectoriented features. Some of these are:
– Reusability: Rather than endlessly rewriting the same piece of
code, we write it once and use it or inherit it as needed.
– Extensibility: A class can be extended without affecting its
users provided that the user-interface remains the same.
– Maintainability: Again, once the user-interface does not change,
the implementation can be changed at will.
– Security: Thanks to information hiding, a user can only access
the information he has been allowed to access.
– Abstraction: Classification and Encapsulation allow portrayal of
real-world problems in a simplified model.
Review of inheritance
• Suppose we have the following Employee class:
class Employee {
protected String name;
protected double payRate;
public Employee(String name, double payRate)
this.name = name;
this.payRate = payRate;
}
public String getName() {return name;}
public void setPayRate(double newRate) {
payRate = newRate;
}
public double pay() {return payRate;}
public void print() {
System.out.println("Name: " + name);
System.out.println("Pay Rate: "+payRate);
}
}
{
Review of inheritance (contd.)
• Now, suppose we wish to define another class to
represent a part-time employee whose salary is paid per
hour. We inherit from the Employee class as follows:
class HourlyEmployee extends Employee {
private int hours;
public HourlyEmployee(String hName, double hRate) {
super(hName, hRate);
hours = 0;
}
public void addHours(int moreHours) {hours += moreHours;}
public double pay() {return payRate * hours;}
public void print() {
super.print();
System.out.println("Current hours: " + hours);
}
}
Notes about Inheritance
•
We observe the following from the examples on inheritance:
• Methods and instance variables of the super class are inherited by
subclasses, thus allowing for code reuse.
• A subclass can define additional instance variables (e.g. hours) and
additional methods (e.g. addHours).
• A subclass can override some of the methods of the super class to
make them behave differently (e.g. the pay & print)
• Constructors are not inherited, but can be called using the super
keyword. such a call must be the first statement.
• If the constructor of the super class is not called, then the complier inserts a
call to the default constructor -watch out!
• super may also be used to call a method of the super class.
Review of Abstract Classes
• Inheritance enforces hierarchical organization, the benefits of which
are: reusability, type sharing and polymorphism.
• Java uses Abstract classes & Interfaces to further strengthen the
idea of inheritance.
• To see the role of abstract of classes, suppose that the pay method
is not implemented in the HourlyEmployee subclass.
– Obviously, the pay method in the Employee class will be assumed, which will
lead to wrong result.
– One solution is to remove the pay method out and put it in another extension of
the Employee class, MonthlyEmployee.
– The problem with this solution is that it does not force subclasses of Employee
class to implement the pay method.
Review of Abstract Classes (Cont'd)
• The solution is to declare the pay method of the Employee class as
abstract, thus, making the class abstract.
abstract class Employee {
protected String name;
protected double payRate;
public Employee(String empName, double empRate) {
name = empName;
payRate = empRate;
}
public String getName() {return name;}
public void setPayRate(double newRate) {payRate = newRate;}
abstract public double pay();
public void print() {
System.out.println("Name: " + name);
System.out.println("Pay Rate: "+payRate);
}
}
Review of Abstract Classes (Cont'd)
• The following extends the Employee abstract class to get
MonthlyEmployee class.
class MonthlyEmployee extends Employee {
public MonthlyEmployee(String empName, double empRate) {
super(empName, empRate);
}
public double pay() {
return payRate;
}
}
• The next example extends the MonthlyEmployee class to get the
Executive class.
Review of Abstract Classes (Cont'd)
class Executive extends MonthlyEmployee {
private double bonus;
public Executive(String exName, double exRate) {
super(exName, exRate);
bonus = 0;
}
public void awardBonus(double amount) {
bonus = amount;
}
public double pay() {
double paycheck = super.pay() + bonus;
bonus = 0;
return paycheck;
}
public void print() {
super.print();
System.out.println("Current bonus: " + bonus);
}
}
HourlyEmployee
Employee
MonthlyEmployee
Executive
Review of Abstract Classes (Cont'd)
• The following further illustrates the advantages of organizing classes
using inheritance - same type, polymorphism, etc.
public class TestAbstractClass {
public static void main(String[] args) {
Employee[] list = new Employee[3];
list[0] = new Executive("Jarallah Al-Ghamdi", 50000);
list[1] = new HourlyEmployee("Azmat Ansari", 120);
list[2] = new MonthlyEmployee("Sahalu Junaidu", 9000);
((Executive)list[0]).awardBonus(11000);
for(int i = 0; i < list.length; i++)
if(list[i] instanceof HourlyEmployee)
((HourlyEmployee)list[i]).addHours(60);
for(int i = 0; i < list.length; i++) {
list[i].print();
System.out.println("Paid: " + list[i].pay());
System.out.println("*************************");
}
}
}
The Program Output
Review of Interfaces
• Interfaces are not classes, they are entirely a separate entity.
• They provide a list of abstract methods which MUST be
implemented by a class that implements the interface.
• Unlike abstract classes which may contain implementation of some
of the methods, interfaces provide NO implementation.
• Like abstract classes, the purpose of interfaces is to provide
organizational structure.
• More importantly, interfaces are here to provide a kind of "multiple
inheritance" which is not supported in Java.
– If both parents of a child implement a method, which one does the child inherits?
- Multiple inheritance confusion.
– Interfaces allow a child to be both of type A and B.
Review of Interfaces (contd.)
• Recall that Java has the Comparable interface defined as:
interface Comparable {
int compareTo(Object o);
}
• Recall also that java has the java.util.Arrays class, which has a sort
method that can sort any array whose contents are either primitive
values or Comparable objects.
• Thus, to sort our list of Employee objects, all we need is to modify
the Employee class to implement the Comparable interface.
• Notice that this will work even if the Employee class is extending
another class or implementing another interface.
• This modification is shown in the next page.
Review of Interfaces (contd.)
abstract class Employee implements Comparable {
protected String name;
protected double payRate;
public Employee(String empName, double empRate)
name = empName;
payRate = empRate;
}
public String getName() {return name;}
public void setPayRate(double newRate) {
payRate = newRate;
}
abstract public double pay();
public int compareTo(Object o) {
Employee e = (Employee) o;
return name.compareTo( e.getName());
}
}
{
HourlyEmployee
Comparable
Employee
MonthlyEmployee
Executive
Review of Interfaces (contd.)
•
Since Employee class implements the Comparable interface, the array of
employees can now be sorted as shown below:
import java.util.Arrays;
public class TestInterface {
public static void main(String[] args) {
Employee[] list = new Employee[3];
list[0] = new Executive("Jarallah Al-Ghamdi", 50000);
list[1] = new HourlyEmployee("Azmat Ansari", 120);
list[2] = new MonthlyEmployee("Sahalu Junaidu", 9000);
((Executive)list[0]).awardBonus(11000);
for(int i = 0; i < list.length; i++)
if(list[i] instanceof HourlyEmployee)
((HourlyEmployee)list[i]).addHours(60);
Arrays.sort(list);
for(int i = 0; i < list.length; i++) {
list[i].print();
System.out.println("Paid: " + list[i].pay());
System.out.println("**********************");
}
}
}
The program output
Review Questions
•
How does an interface differ from an abstract class?
• Why does Java not support multiple inheritance? What feature of
Java helps realize the benefits of multiple inheritance?
•
An Abstract class must contain at least one abstract method, (true
or false)?
•
A subclass typically represents a larger number of objects than its
super class, (true or false)?
• A subclass typically encapsulates less functionality than its super
class does, (true or false)?
•
An instance of a class can be assigned to a variable of type any of
the interfaces the class implements, (true or false)?