Analysis of Algorithms
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
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.
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
(CIS*1900 or MATH*2000).
M.T.Goodrich and R.Tamassia
Data Structures & Algorithms in Java
Course Format and Schedule:
Course webpage can be found at:
Students will attend lectures presented by the
professor and lab-tutorials presented by a
teaching assistant. The lectures schedule is:
Office hour: Email for an appointment
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
(1) 4 Assignments: equally weighted 5%
(2) 2 Quizzes: weighted 15%, 15%
(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.
1. Intro algorithm complexity analysis
2. Stacks,queues,vectors,and lists
4. Priority queues
5. Dictionaries and hashing
6. Search trees
8. Text Processing
Prof. Xining Li
Thornbrough Bkdg 1389 Ext: 56548
Prof. William Elazmeh
Reynolds 321 Ext: 58762
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
Late assignments or labs are NOT ACCEPTED.
Missed quizes result in a mark of zero, unless (see next
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
Marks Posting: When ready, you may be able to examine your
marks through the course webpage (the marks will be posted
during the term).
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
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
Source-level and executable-level
Programs written by a high-level programming language are
source-level portable (some special cases).
Source-code programs are not directly executable, they must
A compiler could be designed to generate two types of
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
Three alternatives for running
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.
Types of Java programs:
Standalone application: main()
Applet - code executed by a web
browser: no main()
type: defines value domain
name: symbolic identifier
Data: value: a specific value
location: memory reference
operations: predefined on
class: define state domain
name: symbolic identifier
state: current state
location: memory reference
methods: pre/user defined
Object-Oriented programming: glues data and their
related operations into one piece - object.
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
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.
class is visible in this
class is visible in other
class must be extended
class must not be
Method Usage Modifiers:
cannot be overridden
attached to a class not an
must be overridden
not written in Java
entry to the method is
Method Scope Modifiers:
visible in this package and
visible in subclasses in other
visible in this package
only visible in this class and its
only visible in this class so can
never be declared abstract
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.
Variable usage modifiers:
the variable's value
cannot be changed
a class variable
reserved for future
the variable can be
Variable scope modifiers:
visible in this package
and in subclasses in
visible in this package
in this class and its
only visible in this class
Extent of a variable:
T(creation) - T(no_more_references)
T(loaded) - T(no_more_references)
T(enter_code_block) - T(exit_code_block)
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
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.
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);
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.
The class version of basic types:
An example of moving an int to an
Integer object and an Integer to an int,
using methods from the Integer class:
int i = 42;
iobj = new Integer(i);
// to Object
i = iobj.intValue(); // to int
Interfaces are skeletons of classes. They are used to specify the
form that something must have, but not actually provided the
An interface only declares methods and defines constants
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
Any methods or variables declared in a public interface are
An interface may extend any number of other interfaces.
1. A program written in the JavaTM
programming language can run on any
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.
2. An applet will run in almost any
A. The server has a built-in JVM.
B. The browser has a built-in JVM.
C. The source code is interpreted by
D. Applets don't need a JVM.
3.What is the purpose of the main
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
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
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.
6.What is the advantage of using
A.To avoid having to declare variables.
B.To refer to a class without using
C.To avoid calling methods.
D.To import the images you want to
7.When a program class implements
an interface, it must provide behavior
A. Two methods defined in that
B. Only certain methods in an interface.
C. Any methods in a class.
D. All methods defined in that interface.
8.A constructor is used to...
A. Free memory.
B. Initialize a newly created object.
C. Import packages.
D. Create a JVM for applets.
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.
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.