Programming Techniques

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

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.

Requirements:

Syllabus of lectures:

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

Syllabus of tutorials:

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

Study Objective:

Study materials:

[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

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: