Transcript Week1-Introduction-updated18-1-2016

DATA STRUCTURES
(CS212D)
Overview & Review
Instructor Information
2




Instructor Information:
Dr. Radwa El Shawi
Room:2.501.29
Email:[email protected]
Course objectives




Be familiar with problem solving.
Be familiar with basic techniques of
algorithm analysis.
Be familiar with the concept of recursion.
Master the implementation of linked data
structures such as linked lists, stacks, and
queues.
Course objectives Cont.
Be familiar with advanced data structures such as
balanced search trees, graphs and hash tables.
 Master analyzing problems and writing program
solutions to problems using the above techniques
 Be able to select appropriate data structures and
algorithms for given problems

Course Outline








Introduction to data structures
Arrays
Recursion
Linked Lists
Stacks and queues
Trees
Graphs
Hash tables
Course Material



Textbook: Data Structures & Algorithms in JAVA (6th Edition),
by M. Goodrich, R. Tamassia and M. Goldwasser , John Wiley &
Sons, inc., 2014.
Lecture hand-outs
Lab notes and exercises
Grading/Evaluation
Course Assessment Tools
Percent
Mid term 1
15%
Mid term 2
Lab assignments, quizzes and
participation
Final lab
15%
Final
40%
10%
20%
What is data?

Data



A collection of facts from which conclusion may be
drawn
e.g. Data: Temperature 35°C; Conclusion: It is hot.
Types of data





Textual: For example, your name (Nourah)
Numeric: For example, your ID (090254)
Audio: For example, your voice
Video: For example, your voice and picture
(...)
What is data structure?



A particular way of storing and organizing data in
a computer so that it can be used efficiently and
effectively.
Data structure is the logical or mathematical
model of a particular organization of data.
A group of data elements grouped together under
one name.

For example, an array of integers
Types of data structures
Array
Linked List
Tree
Queue
Stack
There are many, but we named a few. We’ll learn these
data structures in details through this term!
The Need for Data Structures

Goal: to organize data

Criteria: to facilitate efficient




storage of data
retrieval of data
manipulation of data
Design Issue:

select and design appropriate data types
(This is the main motivation to learn and understand data
structures)
Data Structure Operations

Traversing


Searching


Accessing each data element exactly once so that
certain items in the data may be processed
Finding the location of the data element (key) in the
structure
Insertion

Adding a new data element to the structure
Data Structure Operations (cont.)

Deletion


Sorting


Removing a data element from the structure
Arrange the data elements in a logical order
(ascending/descending)
Merging

Combining data elements from two or more data
structures into one
What is algorithm?




A finite set of instructions which accomplish a
particular task
A method or process to solve a problem
Transforms input of a problem to output
 Algorithm = Input + Process + Output
Algorithm development is an art – it needs
practice, practice and only practice!
What is a good algorithm?




It must be correct
It must be finite (in terms of time and size)
It must terminate
It must be unambiguous



Which step is next?
It must be space and time efficient
A program is an instance of an algorithm, written in
some specific programming language
A simple algorithm


Problem: Find maximum of a, b, c
Algorithm



Input = a, b, c
Output = max
Process
o
o
Let max = a
If b > max then

o
If c > max then

o
max = b
max = c
Display max

Order is very important!!!
Algorithm development: Basics

Clearly identify:
 what output is required?
 what is the input?
 What steps are required to transform input into
output
o
o
o
o
The most crucial bit
Needs problem solving skills
A problem can be solved in many different ways
Which solution, amongst the different possible
solutions is optimal?
Algorithm Design: Practice

Example 1: Determining even/odd number


A number divisible by 2 is considered an even
number, while a number which is not divisible by 2 is
considered an odd number. Write pseudo-code to
display first N odd/even numbers.
Example 2: Computing Weekly Wages

Gross pay depends on the pay rate and the number of
hours worked per week. However, if you work more
than 40 hours, you get paid time-and-a-half for all
hours worked over 40. Write the pseudo-code to
compute gross pay given pay rate and hours worked
Even/ Odd Numbers
Input range
 for num←0; num<=range; num←num+1 do

if num % 2 = 0 then

print num is even

else

print num is odd

endif
 endfor

Computing weekly wages
Input hours_worked, pay_rate
if hours_worked <= 40 then
gross_pay ← pay_rate x hours_worked
else
basic_pay ← pay_rate x 40
over_time ← hours_worked – 40
over_time_pay ← 1.5 x pay_rate x over_time
gross_pay ← basic_pay + over_time_pay
endfor
print gross_pay
What is algorithm analysis?


A methodology to predict the resources that the
algorithm requires

Computer memory

Computational time
We’ll focus on computational time


It does not mean memory is not important
Generally, there is a trade-off between the two
factors
o
Space-time trade-off is a common term
How to analyse algorithms?

Experimental Approach
Implement algorithms as programs and run them on
computers

Not a good approach, though!

o
o
o

Results only for a limited set of test inputs
Difficult comparisons due to the experiment environments
(need the same computers, same operating systems, etc.)
Full implementation and execution of an algorithm
We need an approach which allows us to avoid
experimental study
How to analyse algorithms?

Theoretical Approach

General methodology for analysing the running time
o
o
o


Considers all possible inputs
Evaluates algorithms in a way that is independent from the
hardware and software environments
Analyses an algorithm without implementing it
Count only primitive operations used in an algorithm
Associate each algorithm with a function f(n) that
characterises the running time of the algorithm as a function
of the input size n
o
A good approximation of the total number of primitive
operations
Primitive Operations




Basic computations performed by an algorithm
Each operation corresponding to a low-level
instruction with a constant execution time
Largely independent from the programming language
Examples






Evaluating an expression (x + y)
Assigning a value to a variable (x ←5)
Comparing two numbers (x < y)
Indexing into an array (A[i])
Calling a method (mycalculator.sum())
Returning from a method (return result)
Counting Primitive Operations

Total number of primitive operations executed












is the running time of an algorithms
is a function of the input size
Example
Algorithm ArrayMax(A, n)
# operations
currentMax ←A[0]
2: (1 +1)
for i←1;i<n; i←i+1 do
3n-1: (1 + n+2(n- 1))
if A[i]>currentMax then
2(n − 1)
currentMax ←A[i] 2(n − 1)
endif
endfor
return currentMax
1
Total: 7n − 2
Algorithm efficiency: growth rate
 An algorithm’s time requirements can be
expressed as a function of (problem) input size
 Problem size depends on the particular problem:


For a search problem, the problem size is the
number of elements in the search space
For a sorting problem, the problem size is the
number of elements in the given list
 How quickly the time of an algorithm grows as a
function of problem size -- this is often called an
algorithm’s growth rate
Algorithm growth rate
Which algorithm is the most efficient? [The one with
the growth rate Log N.]
Homework
1. Write an algorithm to find the
largest of a set of numbers. You do
not know the number of numbers.
2. Write an algorithm that finds the
average of (n) numbers.
For example numbers are [4,5,14,20,3,6]s