BITP 1123 Data Structures: Templates and Overloading

BITP 1123 Struktur Data & Algoritma

• The course covers templates, introduction to data structure and algorithm analysis
• Students should be able to apply class and function templates in programming
• Students should be able to understand abstract data types, data structures, algorithm analysis, and algorithm efficiency

Templates

• Templates are models for functions or classes used to generate functions or classes
• Templates provide a major implementation for code reusability
• Different functions and classes can be easily created from one template
• Functions created from a function template must have the same interface, including the number of arguments
• Argument types and return values are usually different
• Classes created with a class template have the same design
• Data members and function arguments may be different

Types of Templates

• Function Templates
• Class Templates

Overloading

• Overloading allows a programmer to have several functions that do the same task but receive or return different types of arguments
• Overloading can lead to longer programs

Basic Template Concepts

• Function templates generate functions
• Class templates generate classes

Function Templates

• A function applies actions to one or more objects and may create and return one object
• Function Templates can create multiple functions each with potentially different arguments and return types
• The template prototype is also known as template prefix
• Syntax Declaration: template
• T, data and dataType must be a valid identifier

Declaration for Standard Data Types:

• int x; double y;

Declaration for Class Generic Data Types:

• template <class T> T x;
• template <class dataType> dataType x;
• T and dataType are the class generic type that can represent any type of standard data type

Function templates

• Only one function template is needed to allow any method call with different data types being sent to its parameters
• The class generic data type changes according to the type of data being sent
• The function adds two numbers and prints the result according to the data type

Function Template With More Than One Parameter

• A function template can have more than one parameter
• Syntax declaration: template <class T1, class T2>
• T1 and T2 can be two different data types
• T1 can represent an integer while T2 can represent a char
• Templates are separated by commas during definition
• Generic data types can be used to represent two different data types at the same time

Function Template With Multiple Type Of Parameters

• The parameter in the function can also be other standard data types such as integer, float, double, boolean, and char, along with the generic data type
• At least one of the parameters must be the class generic data type
• Syntax Declaration: template <class T> void Maximum (T x, int y);

Class Templates

• Sometimes there is a situation that needs a generic class being declared
• Class Template is designed to have the data member with the generic type
• The declaration of class templates is the same as function templates: template <class T>
• Generic parameters must be used in at least one of the class data members
• The template prefix must be defined before the declaration of each class and each functions implementation
• The class interface and implementation must be included into one header file
• Templates will be compiled only when requested

Intro to Data Structures & Algorithm

• One of the most common tools used to define algorithms is pseudocode
• Pseudocode is an English-like representation of the code required for an algorithm
• It has an English part and a structured code part
• The English part provides a relaxed syntax that is easy to read
• The structured code consists of an extended version of the basic algorithmic constructs such as sequence, selection, and iteration

Algorithm Header

• Each algorithm begins with a header that names it, describes its parameters, and lists any pre- and postconditions
• The header information must be complete enough to communicate everything that programmers need to know to use the algorithm

Abstract Data Type (ADT)

• A data type consists of two parts: a set of data and the operations that can be performed on the data
• Integer types consist of values and operations like add, subtract, multiply, and divide

Atomic Data

• Atomic data are data that are considered a single, non-decomposable entity
• An example is the integer 4562
• Atomic data types are sets of atomic data with identical properties

Composite Data

• Composite data can be broken out into subfields that have meaning
• An example of this is a phone number
• It can be broken down into the state code, the district code, and the phone number

Data Structure

• A data structure is an aggregation of atomic and composite data types into a set with defined relationships
• Structure means a set of rules that hold the data together
• Data structures can be nested
• Arrays are homogeneous sequences of data or data types known as elements
• Records are heterogeneous combinations of data into a single structure with an identified key

Abstract Data Type (ADT)

• An abstract data type is a data declaration packaged together with the operations that are meaningful for the data type
• The ADT consists of a set of definitions that allow programmers to use the functions while hiding the implementation
• With ADTs users are not concerned with how the task is done but rather with what it can do
• Users are not aware of the structure used

Algorithm Analysis

• An algorithm is a set of instructions that must be followed by the computer to solve problems
• Algorithm Analysis is a technique to analyze an algorithm, its efficiency, and the usage of memory to find the best algorithm
• Algorithms should solve the problem successfully, use memory efficiently, and have a fast runtime
• Run time depends on input size, code quality, computer speed, and algorithm complexity

Types of Algorithms

• Algorithm 1 is easier to understand, encode and debug
• Algorithm 2 uses computer resources like CPU memory and speed efficiently
• Algorithm 1 can be used if a function/method is only used a few times to minimize cost and input size
• Algorithm 2 can be used in functions/methods used a lot with bigger input sizes to minimize the cost of program development

Efficiency Scenarios

• There are three scenarios to estimate efficiency with computer resources during runtime
  • Worst Case Scenario
  • Best Case Scenario
  • Average Case Scenario / Theta Notation

Type of Software Application

• Analyzing efficiency depends on the type of software application being developed
• Critical applications like air traffic control and medical systems need to have the worst-case scenario analyzed

Algorithm Efficiency

• Brassard and Bratley used the term algorithmics to define the systematic study of the fundamental techniques used to design and analyze efficient algorithms
• If a function is linear (contains no loops) then its efficiency is a function of the number of instructions it contains

Linear Loops

• Assuming i is an integer, the loop is repeated for 1000 times: f(n) = n
• Linear loops with the number of iterations is half the loop factor. The higher the factor the lower the number of loops
• Assuming i is an integer, the loop is repeated for 500 times: f(n) = n/2

Logarithmic Loops:

• Multiply Loops
• Divide Loops
• Iterations in loops that multiply or divide are determined by the following formula: f(n) = [log2 n]

Linear Loops Summary

• For + and – operations the f(n) = n
• If i (+ or – ) any constant number the efficiency is n/(constant number)

Logarithmic Loops Summary

• For * and / operations the f(n) is log [constant number] n

Nested Loops

• Nested Loops are determined by how many iterations each loop completes
• The total is the product of the number of iterations in the inner and outer loops
• Iterations = outer loop iterations x inner loop iterations
• Types of nested loops: linear logarithmic, dependent quadratic, and quadratic

Linear Logarithmic

• Number of iterations in the inner loop: [log2 10]
• Because the inner loop is controlled by an outer loop, the above formula must be multiplied by the number of times the outer loop executes which is 10
• Generalized as f(n) = [nlog2 n]

Dependent Quadratic

• Multiplying the inner loop by the number of times the outer loop is executed gives the formula: f(n) = (n(n+1)) / 2

Quadratic

• Each loop executes the same number of times
• The formula generalizes to: f(n) = n2