Algorithmics And Data Structures Past Paper PDF 2021-2024

Module: Algorithmics and Data Structure – Univ-Sétif – L.DOUIDI University of Setif 1 - Faculty of Sciences Department of Computer Science Major: Academic Bachelor's degree Module: Algorithmics and Data Structure - ASD3 Academic year: 2021-22/23/24 CHAP 5:...

Module: Algorithmics and Data Structure – Univ-Sétif – L.DOUIDI University of Setif 1 - Faculty of Sciences Department of Computer Science Major: Academic Bachelor's degree Module: Algorithmics and Data Structure - ASD3 Academic year: 2021-22/23/24 CHAP 5: COMPLEXITY 1- Objectives of complexity calculations: - Be able to predict the execution time of an algorithm - Be able to compare two algorithms performing the same processing Examples: - If we start calculating the factor of 100, how long will we have to wait for the result? - Which sorting algorithm is best to use to sort an array where an item has just been changed? 2- The assessment of complexity can be done at several levels: at the purely algorithmic level, through analysis and calculation at the level of the implementation of the program experimentally 2-1 Experimental complexity It is possible to evaluate the time it takes to run programs experimentally. This experimental evaluation depends a lot on the programming languages, computers and operating systems used. To be meaningful, the experimental evaluation requires a calibration (Benchmarking) of the computers used.  Module: Algorithmics and Data Structure – Univ-Sétif – L.DOUIDI 2-2 Benchmarking Benchmarking software gives a measurement of a computer's power in flops (floating point operations per second). This power varies according to the processing carried out (raw calculations, on integers or reals, calculations related to the display, etc.) Power of today's consumer computers: a few Gigaflops (106 flops) Power of the best current supercomputers: about 1000 Teraflops (1015 flops) (cf. www.top500.org) 3- Temporal vs. spatial complexity Example: exchange of two integer values: exchange of the values of two integer variables x, y, z;... initializing x and y z