Transcript COEN 352 Data structures and Algorithms

COEN 352
Data structures and Algorithms
R. Dssouli
Abu Abdullah Muhammad ibn Musa al-Khwarizmi
(c. 780 -- 850 AD)
 Persian astronomer and mathematician
 lived in Baghdad, father of algebra
“On calculating with hindu numerals”
a treatise in Arabic, 825
“Agoritmi de numero Indorum”
 translation into Latin, 12th century
 author’s name, mistaken for a plural noun, came to
mean “calculation methods”
Algorithm: Etymology
Al-Khwārizmī (in Arabic: ,)‫خوارزمی‬Persian astronomer and mathematician,
wrote a treatise in the Arabic language in 825 AD, On Calculation with Hindu–
Arabic numeral system. (See algorism). It was translated from Arabic into Latin
in the 12th century as Algoritmi de numero Indorum (al-Daffa 1977), whose title
is supposedly likely intended to mean "Algoritmi on the numbers of the
Indians", where "Algoritmi" was the translator's rendition of the author's name;
but people misunderstanding the title treated Algoritmi as a Latin plural and
this led to the word "algorithm" (Latin algorismus) coming to mean "calculation
method". The intrusive "th" is most likely due to a false cognate with the Greek
ἀριθμός (arithmos) meaning "numbers".
Source Wikipedia
Why Study Data Structures?
• Data structures organize Data
– Good choice  better program (more efficient
program)
– Bad choice  poor program performance
• Changes over time
– More powerful computers
– More complex applications
– More complex tasks
Why Study Data Structures?
• Characteristics of problem’s solution
– Efficiency: a solution is efficient if it solves
problem within resource constraints
• Time
• Space
– Cost: the amount of resources a solution will
consume
Why study Algorithms
• Algorithms solve problems
– Good choice  more efficient program
– Bad choice  poor program performance
• Impact
– Different algorithms perform better on different
inputs
– Input size can affect the performance
Why study algorithms? (2)
• a language for talking about program behavior
• standard set of algorithms and design techniques
• feasibility (what can and cannot be done)
•
halting problem, NP-completeness
• analyzing correctness and resource usage
• successful companies (Google, Mapquest, Akamai)
• computation is fundamental to understanding the world
• cells, brains, social networks, physical systems all can be
• viewed as computational devices
• IT IS FUN!!!
Goal
• Designing “clever" algorithms to
solve problems efficiently.
• Analyzing algorithms. This
means:
– proving that they are correct. It is not part of
this course.
– estimating their running time and/or other
resources needed (e.g., memory space).
•
A
Abstract Data Types
ADT
• Basic definitions
–
–
–
–
–
Type: a set of objects
Data item or element: a piece of information or record
Member: a data item is said to be a member of a data type
Simple data item: a data item containing no subparts
Aggregate data item: a data item that may contain several
pieces of information
– Abstract data type: a type and a collection of operations to
manipulate that type
ADT are mathematical abstractions, an ADT only mentions
what is to be done, not how.
Data Structure
• A data Structure is a physical implementation
of an ADT
– Each ADT operation is implemented by one or
more subroutines
– Data structures are organizations for data in the
main memory
Relations between notions
Problem
Abstract data structure
Algorithms
Concrete data structure
Program
Software library
Specify
Resolves /Implements
Selecting a Data Structure
•
•
•
•
Analyze problem
Determine basic operations
Select a data structure
Questions
– At what times(s) in the program run do inserts
occur
– Are deletes allowed?
– Is there any Order to data processing?
Algorithm/ Data Structure
• Each data structure requires:
– Space to store each item, including overhead
– Time to perform basic operations
– Programming effort
• Algorithms are closely related:
– Poor data structure choice higher complexity
algorithms
– Good data structure choice  algorithm trivial
Performance isn’t everything
Typical goal: Find most space- and time-efficient algorithm for
given problem.
•
What else is important?
– modularity
– user-friendliness
– correctness
– programmer time
– maintainability
– simplicity
– functionality
– extensibility
– robustness
– reliability
Problems, Algorithms and Programs
What is the difference among these?
• Key questions that relate:
– Can the problem be solved efficiently?
– What do we mean by efficient?
– Which algorithms are more efficient?
– How one can answer the above questions?
– How to estimate the time required for a program?
– Hoe to reduce the running time of a program?
– The consequences of careless use of recusion
Problems
• Problem: task to be performed
– Can be seen as: a set of inputs and matching outputs
– Problem definition includes resource constraints
• Problems are analogous to mathematical functions
– Function: mapping inputs (domain) to outputs (range)
– The input to a function can vary:
• Single number
• Multiple numbers
• Set of information
– Parameters: the value making up an input
– A given input must always map to the same output
Algorithms
Definition: Finite set of unambiguous instructions
for solving a problem.
• An algorithm is correct if on all legitimate inputs, it
outputs the right answer in a finite amount of time
• Can be expressed as
–
–
–
–
Pseudocode
flow charts
text in a natural language (e.g. English)
computer code
Algorithms and Programs
• Algorithms: a method or process to solve a
problem
– Algorithm transforms the input of a problem to its
outputs
– Algorithm proprieties
1)
2)
3)
4)
5)
Must be correct
It must be composed of a series of correct steps
There can be no ambiguity about which step is next
It must be finite in length
It must terminate
• Program: an instance of an algorithm, written in
some programming language.