Algoritmi "Podijeli pa vladaj"

Penzer, Petra (2016) Algoritmi "Podijeli pa vladaj". Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (661kB) | Preview

Abstract

This master thesis describes the “divide and conquer” method which is used in the design of algorithms. The thesis is divided into three chapters. The first chapter describes the basic principles of ”divide and conquer”, and general steps of the algorithms designed by this method. Also, in this chapter, there is a brief review of main results from the theory of recursive relations that are used in the analysis of time complexity of the algorithms mentioned in the second chapter. The second chapter contains several algorithms which are designed by the ”divide and conquer” method: the binary search algorithm, mergesort, quicksort, multiplication of large integers, and multiplication of matrices. For these algorithms, there is an analysis of their time complexity and their pseudocode. In the third chapter of this thesis, we give implementations of some of the before mentioned algorithms in the C++ programming language. The algorithms are tested by measuring the execution time for various sizes of the input data. The results of each test are presented in table and graphic forms. This master thesis on the ”divide and conquer” method concludes that this is a very important method for the design of algorithms. This method is widely used in practice because it can produce efficient algorithms for solving some of the problems. The method is also very simple and interesting

Item Type: Thesis (Diploma thesis)
Supervisor: Singer, Saša
Date: 2016
Number of Pages: 43
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 09 Nov 2016 12:24
Last Modified: 09 Nov 2016 12:24
URI: http://digre.pmf.unizg.hr/id/eprint/5274

Actions (login required)

View Item View Item