### Course Description

# Programming, Data Structures and Algorithms

## Program

Information and Communication Technologies, second-level study programme## Lecturers:

doc. dr. Anton Biasizzoprof. dr. Janez Demšar

## Goals:

The goal of the course is to familiarize the student with the programming languages, programming techiques, common data structures an algorithms, and the analysis of the algorithm complexity.

The competencies of the students completing this course successfully would include the basic programming knowledge in selected programming language, the knowledge of common data structures and algorithms, the ability to reuse the existing algorithms in problem solving.

## Content:

Introduction: mathematical fundamentals, models of computation, and programming techniques, overview of the programming languages and basics of selected programming language.

Lists and stacks: linked list, double linked list, circular list, basic operations on lists, stack model, stack implementation, applications, reverse polish notation.

Trees: definition of tree, implementation of trees, binary trees, operations on trees, search tree, balanced trees, balanced tree operations, B-trees, applications of trees.

Queues and priority queues: queue model, queue implementations, queue applications, priority queues, simple priority queue implementation, binary heaps, applications of priority queues.

Sorting: insertion sort, shellsort, bubblesort, heapsort, mergesort, quicksort, analysis of sort methods.

Graphs: graph definition, directed and undirected graph, graph representation of graphs, shortest-path problem, minimum spanning tree, depth-first search, NP-completeness.

Algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, backtracking algorithms.

Practical examples: computer communications, embedded applications, massive data storages.

## Course literature:

Selected chapters from the following books:

• M. A. Weiss, Data Structures and Algorithm Analysis in C++. Addison-Wesley, 2013. ISBN 978-0-132-84737-7

• R. Sedgewick, and K. Wayne, Algorithms. Addison-Wesley, 2011. ISBN 978-0-321-57351-3

• D. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, 1997. ISBN 0-201-89683-4

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press and McGraw-Hill, 2009. ISBN 0-262-03384-4

## Significant publications and references:

• A. Biasizzo and F. Novak, “Hardware accelerated compression of LIDAR data using FPGA devices”, Sensors, vol. 13, no. 5, pp. 6405-6422, 2013.

• U. Legat, A. Biasizzo, and F. Novak, “SEU recovery mechanism for SRAM-based FPGAs”, IEEE trans. on nuclear science, vol. 59, no 5, pp. 2562-2571, 2012.

• U. Legat, A. Biasizzo, and F. Novak, “A compact AES core with on-line error-detection for FPGA applications with modest hardware resources”, Microprocessors and microsystems, vol. 34, no. 4, pp. 405-416, 2011.

• F. Novak and A. Biasizzo, “Academic network for microelectronic test education”, International Journal of Engineering Education, vol. 23, no. 6, pp. 1245-1253, 2007.

• F. Novak and A. Biasizzo, “Security extension for IEEE Std 1149.1”, Journal of electronic testing, vol. 22, no. 3, pp. 301-303, 2006.

## Examination:

Seminar work

Oral defense of seminar work

## Students obligations:

Seminar work and oral defense of seminar work.