Programming Techniques

Semestr: Summer

Range: 3+2s

Completion:

Credits: 5

Programme type: Undefined

Study form:

Course language:

Summary:

Program design paradigms, complexity of algorithms, sorting - taxonomy of methods, Shellsort, Heapsort, Quicksort, Radixsort, searching, hashing, binary search, binary trees, multidimensional trees, abstract data type specification and implementation (vector, linked list, dynamic free memory, array, table, list, relation, graph), logical and physical structure of files, sorting sequential files.

Keywords:

Course syllabus:

1. Storage and time complexity of algorithms
2. Sorting methods (Selection-, Bubble-, Insertion-, Shell-, Quick-, Heap-, Radix-Sort)
3. Address search methods
4. Associative search methods
5. Multidimensional search
6. Data structures for multidimensional search
7. Data types specification
8. Implementation of data types Stack, Queue, Strig, Array, Table
9. Implementation of data tapes List, Relation, Graph
10. File data type, logical and physical structure of files, file sorting
11. Recursive programming, implementation of recursion
12. Backtracking algorithms, dynamics programming
13. Design of algorithms: sweep line, prune and search, devide and control

Seminar syllabus:

1. Summations of series, solution of simple recurrences
2. Storage and time complexity of algorithms written in Pascal language
3. Insert-Sort implemented in array and linked structures
4. Algorithms Quick-Sort, Heap-Sort, Merge-Sort, and Radix-Sort
5. Address search methods, hashing
6. Binary search, binary search trees
7. K-dimensional search trees, interval and segment trees
8. Proximity problem, Voronoi diagram
9. Abstract data specification
10. Implementation of arrays and tables
11. Implementation of graphs and relations
12. Update of sequential files, sorting of sequential files
13. Complexity of recursive algorithms, backtracking algorithms
14. Assessment

Literature:

[1] Cormen,T.H., et al.: Introduction to ALGORITHMS. McGraw-Hill, New York 1990
[2] Manoocher, A.: Abstract Data Types and Algorithms. Macmillan Education Ltd., London

Examiners:

Lecturers:

Instructors: