Transcript Analysis of Algorithms

CIS 2420 Data Structures
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
2
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 quizzes, 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
3
 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
4
Course Format and Schedule:
Course webpage can be found at:
http://www.cis.uoguelph.ca/~welazmeh/cis242/fall03
Students will attend lectures presented by the
professor and lab-tutorials presented by a
teaching assistant. The lectures schedule is:
Tuesdays/Thursdays 08:30-09:50
MACN 105
Office hour: Email for an appointment
Introduction
5
Labs Schedule:
Starting Monday, Sept. 8, 2003, students must sign up
for a lab section. Labs start on Sept. 15, 2003.
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
6
Course Evaluation:
(1) 4 Assignments: equally weighted 5%
20%
(2) 2 Quizzes: weighted 15%, 15%
30%
(3) Final Exam: 50%
*** in order to pass the course (minimum passing
grade), students MUST obtain at least 50% on the
weighted average of the quizzes and final exam.
Total:
100%
Introduction
7
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
8
Instructor Information:
Prof. Xining Li
[email protected]
Thornbrough Bkdg 1389 Ext: 56548
Prof. William Elazmeh
[email protected]
Reynolds 321 Ext: 58762
Introduction
9
Important Dates:
Tuesday 09/09/2003:
Monday 29/9/2003:
Monday 13/10/2003:
Thursday 16/10/2003:
Monday 03/11/2003:
Monday 03/11/2003:
Thursday 20/11/2003:
Monday 24/11/2003:
Friday 28/11/2003:
Wednesday 03/12/2003:
Classes begin
Assignment #1 Due
Assignment #2 Due
Quiz #1 (in class)
Course Drop Deadline
Assignment #3 Due
Quiz #2 (in class)
Assignment #4 Due
Last Day of Class
Final Exam
Introduction
10
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 through the course webpage (the marks will be posted
during the term).
Introduction
11
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
12
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
13
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
14
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
15
Types of Java programs:
 Standalone application: main()
 Applet - code executed by a web
browser: no main()
Introduction
16
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
17
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
18
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
19
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
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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
29
The class version of basic types:
Basic Type
Corresponding Class
boolean
Boolean
char
Char
integer
Integer
Long
Long
float
Float
double
Double
Introduction
30
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
31
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
32
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
33
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
34
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
35
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
36
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
37
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
38
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
39
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
40
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
41
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
42