Transcript Document

CIS 2420 Data Structures
Introduction
2
Course Objectives and Methods:
Students will acquire the skill of designing and
implementing abstract data structures in a high-level
programming language.
CIS*242 will convey the concept of layered software
by separating the application from the
implementation using abstraction.
When building data structures students will review
methods of performance and complexity analysis of
algorithms used for implementation.
Introduction
3
Data structures will include lists, vectors, queues,
stacks, trees, dictionaries, hash-tables, and graphs.
Algorithms used include searching, sorting, text
processing using the above data structures.
On assignments, students are asked to program data
structures using a high-level programming language.
On exams and quizes, students are asked to solve
problems using analytical methods and programming
skills acquired from lectures and assignments to
demonstrate knowledge and comprehension of
course material.
Introduction
4
 Prerequisite(s):
CIS*2650,
(CIS*1900 or MATH*2000).
 Text Book:
M.T.Goodrich and R.Tamassia
Data Structures & Algorithms in Java
(2nd Edition),WILEY,1997.
Introduction
5
Course Format and Schedule:
Course webpage can be found at:
http://snowhite.cis.uoguelph.ca/~welazmeh/teaching/cis242/fall02
Students will attend lectures presented by the
professor and lab-tutorials presented by a
teaching assistant. The lectures schedule is:
S1) X. Li Tuesdays/Thursdays 08:30-09:50
MACK 120 Office hour: Email for an appointment
S2) W. Elazmeh Tuesdays/Thursdays 08:30-09:50
C&M 160 Office hour: Email for an appointment
Introduction
6
Labs Schedule:
Lab
Lab
Lab
Lab
Lab
A) Tuesday 13:00-14:50 THRN 1313
B) Tuesday 17:30-19:20 THRN 1313
C) Wednesday 15:00-16:50 THRN 1313
D) Thursday 15:00-16:50 THRN 1313
E) Thursday 17:00-18:50 THRN 1313
The labs are limited to 30 students per lab section.
To register in a lab section, pick a suitable time and write your
ID in the registration list posted outside Reyn 321.
The spaces are reserved for the first 30 students registered on that
list. (please do not change groups unless approved by your
instructor).
Introduction
7
Course Evaluation:
4 Assignments: equally weighted 6%
24%
3 Quizzes: weighted 6%, 10%, 10%
26%
1 Final Exam: 50%
*** in order to pass the course (minimum passing
grade), students MUST obtain at least 50% on the
final exam.
Total:
100%
Introduction
8
Course Topics:
1. Intro algorithm complexity analysis
2. Stacks,queues,vectors,and lists
3. Trees
4. Priority queues
5. Dictionaries and hashing
6. Search trees
7. Sorting
8. Text Processing
9. Graphs
Introduction
9
Instructor Information:
Prof. Xining Li
[email protected]
Reynolds 327 Ext: 6548
Prof. William Elazmeh
[email protected]
Reynolds 321 Ext: 8762
Introduction
10
Teaching Assistants Information:
Lab A: Eric Junjiang Chen
Lab B: Amol Shukla
Lab C: Stephen Pearce
Lab D: Lei Song
Lab E: Yang Yu
Marker: Ryan VanAcker
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
Introduction
11
Important Dates:
Monday 09/09/2002:
Tuesday 01/10/2002:
Thursday 03/10/2002:
Tuesday 15/10/2002:
The week of 15/10/2002:
Thursday 24/10/2002:
Monday 04/11/2002:
Tuesday 05/11/2002:
Tuesday 19/11/2002:
Thursday 21/11/2002:
Friday 29/11/2002:
Monday 02 - Friday 13/12/02:
Classes begin
Assignment #1 Due
Quiz #1
Assignment #2 Due
No Labs
Quiz #2
Course Drop Deadline
Assignment #3 Due
Assignment #4 Due
Quiz #3
Last Day of Class
Final Exam Period
Introduction
12
Important Notes:





Late assignments or labs are NOT ACCEPTED.
Missed quizes result in a mark of zero, unless (see next
item).
Illness and severe circumstances may be accommodated,
email your instructor at least 48 hours before the due time
and provide certification whenever possible.
An excused absence from quizzes or labs is not
provided to accommodate personal inconveniences and other
minor problems.
Marks Posting: When ready, you may be able to examine your
marks by clicking here (the marks will be posted during the
term).
Introduction
13
Important Notes:
 Your final grade will be based on the grading system published
in the university calendar.
 To appeal a mark on an assignment, a lab or a quiz, you must
do so within two weeks after they are handed back.
 Each assignment will indicate its due time and date.
 Academic misconduct includes the submission of program code
or assignment answers that appear so similar to another
student's work as to be semantically indistinguishable.
Misconduct cases will be handles swiftly, discreetly,and
summarily by the Department in accordance with University
principles.
Introduction
14
Java = C++ - Java is a general purpose object-oriented
programming with extensions to support
GUI and network (client/sever) applications.
 Java is architecturally neutral. It is an
interpreted language. It is supported by a
variety of hardware platforms and operating
systems.
Introduction
15
Source-level and executable-level
portability:
 Programs written by a high-level programming language are
source-level portable (some special cases).
 Source-code programs are not directly executable, they must
be compiled.
 A compiler could be designed to generate two types of
executable code:
bytecode or binarycode.
 Bytecode programs are executable-level portable, they are
executed by an interpreter (virtual machine, emulator ...).
 Binarycode programs are not portable, they are executed by
hardware.
Introduction
16
Three alternatives for running
Java programs:
 Java interpreter. It translates Java bytecode on-the
-fly. It is usually slow, sometimes at only 3-10 percent
the speed of compiled C code.
 JIT (Just-In-Time) compiler. It converts Java
bytecode into native (binary) code. This can result in
significant performance improvements, but sometimes a
JIT compiler takes an unacceptable amount of time and
memory to do the compilation.
 Java chip. It is a dedicated Java processor, natively
understand Java bytecode without the overhead of an
interpreter or JIT compiler.
Introduction
17
Types of Java programs:
 Standalone application: main()
 Applet - code executed by a web
browser: no main()
Introduction
18
Object-Oriented Programming:
type: defines value domain
name: symbolic identifier
Data: value: a specific value
location: memory reference
operations: predefined on
basic types.
class: define state domain
name: symbolic identifier
Object:
state: current state
location: memory reference
methods: pre/user defined
Object-Oriented programming: glues data and their
related operations into one piece - object.
Introduction
19
Object-Oriented concepts:
 Class: The fundamental structure in Java.
Class = Structured_type + Associated_operations.
 Inheritance: A relation between classes that allows for the
definition and implementation of one class to be based on that
of other existing classes. The inheritance relation is often called
the “is a" relation.
 Encapsulation: A language construct that enables programmers
to limit access to parts of an object.
 Overloading: The ability to use the same name for multiple
methods.
 Polymorphism: In general, polymorphism means the ability to
take more than one form. In OO, it indicates the ability to deal
with multiple types based on a common feature.
Introduction
20
Class Modifiers:
Modifier
(default)
Meaning
class is visible in this
package
public
class is visible in other
packages
abstract
class must be extended
final
class must not be
extended
Introduction
21
Method Usage Modifiers:
Usage Modifier
Meaning
final
cannot be overridden
static
attached to a class not an
object
abstract
must be overridden
native
not written in Java
synchronized
entry to the method is
mutual-exclusive
Introduction
22
Method Scope Modifiers:
Scope Modifier
Meaning
public
visible everywhere
protected
visible in this package and
visible in subclasses in other
packages
(default) friendly
visible in this package
private protected
only visible in this class and its
subclasses
private
only visible in this class so can
never be declared abstract
Introduction
23
Variable Modifiers, Their
Scopes and Extents:
There are three kinds of variables in Java:
instance variables, class variables and
local variables. Characteristics related
with variables are types, modifiers,
scopes, extents, and initial values.
Introduction
24
Variable usage modifiers:
Usage Modifier
Meaning
final
the variable's value
cannot be changed
a class variable
static
transient
volatile
reserved for future
use
the variable can be
changed
asynchronously
Introduction
25
Variable scope modifiers:
Scope Modifier
Meaning
public
visible everywhere
protected
visible in this package
and in subclasses in
other packages
default (friendly)
visible in this package
private protected
in this class and its
subclasses
private
only visible in this class
Introduction
26
Extent of a variable:
Variable Kind
Extent
instance variable
T(creation) - T(no_more_references)
class variable
T(loaded) - T(no_more_references)
local variable
T(enter_code_block) - T(exit_code_block)
Introduction
27
Declarations:
 The general form of data declaration:
<Modifiers> <type_name><variable_name> [= <initial_value>];
 The general form of object declaration:
<Modifiers> <type_name><variable_name> [= new <costructor>];
 Object declarations (without an initialization) do
not create objects. For example:
Bicycle blackice; // no blackice object yet
Bicycle blackice = new Bicycle(...); // create an object blackice
Introduction
28
Operators and Expressions:
There are factors that influence the final value
of an expression:
 Precedence: it says that some operations bind more
tightly than others.
 Associativity: it defines the tie breaker for deciding
the binding when we have several operators of equal
precedence strung together.
 Evaluation_order: it tells the sequence (for each
operator) in which the operands are evaluated.
Introduction
29
The Basic Statements:
 selection: if and switch statements
 iteration: for, while, and do statements
 control transfer: return, throw,
continue, break, and goto statements
 guarding: synchronized statement
 method call: object.method(arg_list);
Introduction
30
The Object Class:
 In Java, nearly everything is an object. Every
class is ultimately inherited from the ultimate
superclass Object, i.e., any object obj in a
Java program can be converted to an object
of Object by casting (Object) obj.
 Most Java utility classes require the use of
instances of Object. However, variables of
basic types are not instances of Object yet.
 Thus Java provides a simple way to promote
them when needed.
Introduction
31
The class version of basic types:
Basic Type
Corresponding Class
boolean
Boolean
char
Char
integer
Integer
Long
Long
float
Float
double
Double
Introduction
32
An example of moving an int to an
Integer object and an Integer to an int,
using methods from the Integer class:
Integer iobj;
int i = 42;
iobj = new Integer(i);
// to Object
i = iobj.intValue(); // to int
Introduction
33
Interfaces:
 Interfaces are skeletons of classes. They are used to specify the






form that something must have, but not actually provided the
implementation.
An interface only declares methods and defines constants
(variables).
An interface can be implemented by any class.
A class can implement several interfaces at once. (different from
inheritance, a class can only extend one parent class).
An interface is a static (compile-time) protocol. (An abstract class
implies inheritance, which may select a proper method at
runtime).
Any methods or variables declared in a public interface are
implicitly public.
An interface may extend any number of other interfaces.
Introduction
34
1. A program written in the JavaTM
programming language can run on any
platform because...
A. Java programming is derived from C++.
B. The Java Virtual Machine(JVM) interprets the
program for the native operating system.
C. The compiler is identical to a C++ compiler.
D. The APIs do all the work.
Introduction
35
2. An applet will run in almost any
browser because...
A. The server has a built-in JVM.
B. The browser has a built-in JVM.
C. The source code is interpreted by
the browser.
D. Applets don't need a JVM.
Introduction
36
3.What is the purpose of the main
method?
A.To build a user interface.
B.To hold the APIs of the application.
C.To create buttons and scrollbars.
D.To act as the entry point for the
program.
Introduction
37
4.The Applet class provides...
A. A browser to run the applet.
B. Methods to define the applet's
behavior and appearance.
C. A special HTML page.
D. Permission to communicate with the
server.
Introduction
38
5.Which method will a web browser
call first on a new applet?
A. main method
B. start method.
C. init method.
D. paint method.
Introduction
39
6.What is the advantage of using
import statements?
A.To avoid having to declare variables.
B.To refer to a class without using
prefixes.
C.To avoid calling methods.
D.To import the images you want to
use.
Introduction
40
7.When a program class implements
an interface, it must provide behavior
for...
A. Two methods defined in that
interface.
B. Only certain methods in an interface.
C. Any methods in a class.
D. All methods defined in that interface.
Introduction
41
8.A constructor is used to...
A. Free memory.
B. Initialize a newly created object.
C. Import packages.
D. Create a JVM for applets.
Introduction
42
9.The BorderLayout class provides
static fields for...
A. Introducing new methods.
B. Adding components to specific
areas of a container.
C. Starting an applet.
D. Specifying font size and color.
Introduction
43
10.Servlets are typically used for...
A. Creating graphics.
B. Extending a web server by
providing dynamic web content.
C. Storing information in applets.
D. Loading buttons and menus.
Introduction
44