Data Structures and Algorithms • optimality
Algorithm - a well-defined finite set of rules that Approaches:
specifies a sequential series of elementary operations to
be applied to • theoretical analysis
• empirical analysis
some data called the input, producing after a finite
amount of time some data called the output. Theoretical analysis of time efficiency
Algorithm Principles Time efficiency is analyzed by determining the number
of repetitions of the basic operation as a function of
Sequence input size.
• One command at a time Basic operation: the operation that contributes most
• Parallel and distributed computing towards the running time of the algorithm.
Condition C++ - a high-level language: when you write a program
in it, the shorthands are sufficiently expressive that you
• CASE
don’t need to worry about the details of processor
Loops instructions.
• FOR The Compilation Process
• WHILE A program goes from text files (or source files) to
• REPEAT processor instructions as follows:
Complexity
Time complexity:
• How much time it takes to compute
• Measured by a function T(N)
Space complexity:
• How much memory it takes to compute
• Measured by a function S(N)
Design and Analysis - An algorithmic solution to a
computational problem will usually involve designing an
algorithm, and then analyzing its performance.
Design - A good algorithm designer must have a
thorough background knowledge of algorithmic Bjarne Stroustrup – creator of c++ (1979)
techniques, but especially substantial creativity and
imagination. Often the most obvious way of doing Programming with the Problem Analysis–Coding–
something is inefficient, and a better solution will Execution Cycle
require thinking “out of the box”. In this respect,
algorithm design is as much an art as a science.
Analysis - A good algorithm analyst must be able to
carefully estimate or calculate the resources (time,
space or other) that the algorithm will use when
running. This requires logic, care and often some
mathematical ability.
In designing and analysing an algorithm we should
consider the following questions:
1. What is the problem we have to solve?
2. Does a solution exist?
3. Can we find a solution (algorithm), and is there
more than one solution?
4. Is the algorithm correct?
5. How efficient is the algorithm?
Analysis of algorithms
Issues:
• correctness Tokens - the minimal chunks of program that have
• time efficiency meaning to the compiler – the smallest meaningful
• space efficiency symbols in the language.
Determine representation of those abstract entities and
to implement the abstract operation on these concrete
representations.
Multiple data structures:
• Arrays
• Maps
• Linked Lists
// - Comment • Stack
• Queues
# - preprocessor commands, which usually change what • Trees
code is actually being compiled. • Graphs
int main() {...} - defines the code that should execute Array - a group of consecutive memory locations with
when the program starts up. same name and data type.
cout << - This is the syntax for outputting some piece of Elements – memory locations
text to the screen.
Length – total number of elements
Namespaces - a context – sort of a directory of names
Index/Subscript – reference to its position in the array
Strings – a sequence of characters.
DECLARATION OF AN ARRAY:
\n – newline
Type – valid type (data type sa madaling sabe)
Name – valid identifier(variable name sa madaling sabe)
Elements – field, specifies how many of these elements
the array has to contain.
Operator types:
Mathematical – alam nyo to
Logical – and(%%), or(||), not(!)
Types of Array:
Bitwise – used to manipulate the binary representations
of numbers • Single dimensional array
Data Type - a formal description of what kind of data its • Two dimensional array
value. • Multi dimensional array
Sorting Arrays:
• Ascending Order
• Descending Order
Data Structures - a collection of data elements whose
organization is characterized by accessing operations
that are used to store and retrieve the individual data
elements. The logical arrangement of data as used by a
system for data management; a representation of a data
model in computer form.
Goals of Data structures
Identify and develop useful mathematical entities and
operations and to determine what classes of problems
can be solved by using these entities and operations.
