Electronics and Computer Engineering
School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet -Hanoi -Vietnam
Data structure and Algorithms
Thanh-Hai Tran
2020 2
Outline
nObjectives and contents of the course
nBasic concepts of DS & algorithms
nLanguages for expressing algorithms
nDesign and Analysis of algorithms
2020 3
Analysis of algorithms
nDetermine the correctness of algorithms:
uProof by induction (Chứng minh bằng quy nạp)
uProof by counter-example (Chứng minh bằng phản ví dụ)
nAnalyzing an algorithm:determining the amount of
resources (time and memory) needed to execute it.
uEstimation of runtime
«Manual measures: using clocks (usually in programs)
«By theory: estimation of algorithm complexity (xác định độ phức
tạp của giải thuật)
uEstimation of used memory space
nRunning time requirements are more critical than
memory requirements
2020 4
Analysis of algorithms
nAn algorithm may run faster/slower and use more/less
on certain data sets than on others
nMany indicators for assessing the efficiency:
uAverage case
uBest case (lower bound)
uWorst case (upper bound)
uMost common case
nHow to measure complexity?
uExperimental studies
uTheoretical analysis with pseudo-code, flowcharts
2020 5
Analyses of computational times
nExperimental method
uSetting algorithm in programming language
uRun the program with different input data
uMeasure program execution time and evaluate the increase
uSize relative to the size of the input data
nLimitations:
uLimitation in the quantity and quality of test samples
uRequires testing environment (hardware and software) should
be uniform, stable