Transcript Wk #01-02

MIS 215 Module 0
Intro to Data Structures
MIS215 Module 0 - Intro
1
Where are we?
MIS215
Basic Algorithms
Introduction List Structures
Search
Techniques
Intro to
Java, Course
Java lang.
basics
Linked
Lists
Arrays
Sorting Techniques
Hashtables
Binary Search
Stacks,
Queues
Advanced structures
Graphs,
Trees
Bubblesort
Fast Sorting algos
(quicksort, mergesort)
Newbie
Programmers
Designers
MIS215 Module 0 - Intro
Developers
Professionals
2
Today’s Buzzwords

Data Structures
Algorithms
Efficiency of algorithms
Analysis of algorithms
Programming = Data Structures + Algorithms
Programming as a problem-solving method

Elluminate





MIS215 Module 0 - Intro
3
Nuts and Bolts of this Class

Elluminate

A tool for Synchronous Online Collaboration
 This course will be all about collaboration
 Start by clicking the link in the Course Calendar in
WebCT
 Allow Elluminate to install
 Do not click on the microphone while in class!
(believe me – bad things will happen if you do)

Dr. Java and JDK 1.5
MIS215 Module 0 - Intro
4
Elluminate features we will use

Definitely:
 Private
and moderator chats
 Drawing board
 Polling and quizzing

Possibly:
 Project
presentations
 Out-of-class meetings
 Online office hours
MIS215 Module 0 - Intro
5
Introduction to Data Structures







What are data structures/ruptures & algorithms
good for?
Overview of data structures.
Overview of algorithms
Some definitions
OO programming
S/W engineering
Java Library Data Structures
MIS215 Module 0 - Intro
6
What’s a program?
So, far, if you’ve only done CS
208/209/equivalent, what has a program
been?
 Probably, just doing some simple data
manipulation..

 store
some grades in an array
 average the grades, find min/max
 anything else??
MIS215 Module 0 - Intro
7
Overview of Data Structures
Arrays (unordered and ordered)
 Stacks, Queues, Lists

 why
did I lump these all together?
Trees (binary, red-black [?], 2-3-4 [?])
 Hash table
 Heap

MIS215 Module 0 - Intro
8
Our approach to Problem Solving
this quarter
Dr. Java
 Integrated Development Environment
 Edit – Compile – Test – Debug
 Unfortunately CaTS won’t install in labs
 Fortunately it doesn’t take much to install
 Lets use Dr. Java to write our first program

MIS215 Module 0 - Intro
9
HelloWorld.java
public class HelloWorld {
public void run() {
System.out.println("Hello Java World!");
}
public static void main (String [] args) {
HelloWorld tpo = new HelloWorld();
tpo.run();
}
}
MIS215 Module 0 - Intro
10
Dissecting HelloWorld





Every program in Java is (at least) one class
Each class has one or more methods.
The class that runs the program is the main
class, and has a main(…) method
Typically, you should create an instance of a
class in your main method, and call methods of
that instance
That’s exactly what HelloWorld Does!
MIS215 Module 0 - Intro
11
Lets do a little more…
public class GradeCalculator {
private int score = 843; // Score of the student
public void run() {
char letgrade = ''; //single quotes for characters
// Do what is needed here to find the letter grade
System.out.println("The student's letter grade is" +
letgrade);
}
public static void main (String [] args) {
GradeCalculator gc = new GradeCalculator();
gc.run();
}
}
MIS215 Module 0 - Intro
12
Dissecting GradeCalculator
First finish it ..
 What is the logic for finding the letter
grade from the numeric score?
 What is that “private int score;” business?
 What are our alternatives?

MIS215 Module 0 - Intro
13
The Input Class



A stable class for easily receiving input from the
users
Documentation of this class is available at
http://www.wright.edu/~arijit.sengupta/mis215/sa
mples/complexity/Input.html
How do you use it?
 Create
an instance of the Input class
 Call the appropriate method (with or without an
argument)

Why should you use the Input class?
 Stable
– includes some built-in error checks!
MIS215 Module 0 - Intro
14
Lets try it!
Change GradeCalculator to ask the user
for the numeric score
 Where should you create the Input class?
 What happens if you call the run() method
multiple times?
 What is a better way?

MIS215 Module 0 - Intro
15
Going ahead – practising loops
Write a program that asks the user to
guess a number between 1 and 100.
 In a loop, let the computer make a guess,
and the user says G/L/M
(greater/less/match)
 Continue until you get a match
 Report the number of tries

MIS215 Module 0 - Intro
16
CFC – Comment-First Coding


What is it?
Why comments?
 Descriptive
 Think
in English instead of the cryptic code
 Will always compile!!!
 Self-documenting



Why comment-first?
How do you fill out the comments?
Lets try it!
MIS215 Module 0 - Intro
17
Only the run() method now..
public void run() {
// Step 1. Initialization
// Step 2.
// Step 3.
// Step 4.
// Step 5.
}
MIS215 Module 0 - Intro
18
Lets describe the steps
public void run() {
// Step 1. Initialization
// set up the needed variables
// Step 2.
// Step 3.
// Step 4.
// Step 5.
}
MIS215 Module 0 - Intro
19
Finally, fill in the code
public void run() {
// Step 1. Initialization
// set up the needed variables
int steps = 0, guess = 0; // any other variables?
// Step 2.
// Step 3.
// Step 4.
// Step 5.
}
MIS215 Module 0 - Intro
20
Now what?
Practice CFC – we will try to use this
diligently this quarter.
 Every assignment you submit must have
your names as comments at the top of the
file, and all code must be extensively
commented, preferably CFC-ed
 Did I just make up a verb there? 

MIS215 Module 0 - Intro
21
Finally…




Lets try to have fun as you write code
Remember, programs do what we tell them to do
– so we are the boss!
There is nothing like “IT is not working” – IT
always works – just like you tell it to – maybe
you didn’t tell it to do the right thing!
Practice, practice, practice… makes it perfect
MIS215 Module 0 - Intro
22
Part 2 – Analysis of Algorithms
There are many different ways to solve the
same problem
 How do you tell if one way would be better
than another?
 Analysis of algorithms is a method for
identifying the efficiency of an algorithm

MIS215 Module 0 - Intro
23
Order Notation (big-Oh/little-oh)
For this course, we are only going to use
the big Oh notation
 An algorithm is described to have the
complexity of O(some function over n)
 For example, Mergesort has the
complexity O(n lg n)
 No – that wasn’t a typo – lg(n) is log2(n)

MIS215 Module 0 - Intro
24
So what does it mean?

Lets first see how these functions behave:
n2
n
lg(n)
2n
n lg(n)
n!
10
100
4
34
100
10000
7
665
1000
1000000
10
9966
5000
25000000
13
61439
#NUM!
#NUM!
10000
100000000
14
132878
#NUM!
#NUM!
50000
2500000000
16
780483
#NUM!
#NUM!
100000 10000000000
17
1660965
#NUM!
#NUM!
MIS215 Module 0 - Intro
1024
3628800
1.26765E+30 9.3326E+157
1.0715E+301
#NUM!
25
So.. Can you compare now?

Complexity of Bubblesort is O(n2), and
complexity of Mergesort is O(n lg n).
Which one is more efficient?
Bubblesort
B. Mergesort
C. Both are the same
A.
MIS215 Module 0 - Intro
26
How do you determine
complexity of an algorithm?
Typically involves mathematical induction
 For the purpose of this class, try to find the
main loop of the algorithm, and determine
the number of comparisons (or whichever
is the most important operation is)
 Try to find an association between the
input and the number of operations

MIS215 Module 0 - Intro
27
The ComplexityDemo.java
program
Compile and run it – don’t worry too much
about the source code at the moment
 See how the time behaves as you run the
different algorithms
 If you feel adventurous, change the code a
bit and try different input numbers
 (careful – some will not run for large
inputs)

MIS215 Module 0 - Intro
28