Logo ČVUT
Loading...
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2011/2012

Data Structures and Algorithms

Login to KOS for course enrollment Display time-table
Code Completion Credits Range
XD36DSA Z,ZK 5 14+6s
Lecturer:
Michal Píše (gar.), Petr Matyáš
Tutor:
Michal Píše (gar.), Petr Matyáš
Supervisor:
Department of Computer Science and Engineering
Synopsis:
Requirements:
Syllabus of lectures:

1. Space and time complexity of algorithms

2. Classification of sorting methods. Sorting algorithms with complexity O(n2)

3. Sorting algorithms with complexity O(n.logn)

4. Searching problem. Address searching methods

5. Associative searching methods

6. Multidimensional searching, Multidimensional searching trees

7. Geometrical searching, geometrical algorithms

8. Specification and implementation of data types

9. Implementation of the string, stack, queue, array, table, list, and graph data types

10. File data type, logical and physical structure of files, file sorting

11. Recursive programming, implementation of recursive algorithms

12. Back tracking searching algorithms

13. Dynamic programming

14. Program design paradigms

Syllabus of tutorials:

1. Calculation of minimal, maximal and average complexity of algorithms

2. Select-Sort and Buble-Sort, their space and time complexities

3. Insert-Sort implemented in array and linked structures

4. 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, proximity problem

8. Construction of convex hull of a set of points in 2D

9. Specification of data types

10. Implementation of data types

11. Updating and sorting sequential files

12. Backtracking algorithms

13. Complexity of recursive algorithms

14. Assessment

Study Objective:
Study materials:

1. Cormen,T.H., et al.: Introduction to ALGORITHMS, New York, McGraw-Hill 1990.

2. Manoocher, A.:Abstract Data Types and Algorithms, London, Macmillan Education Ltd.

Note:
Time-table for winter semester 2011/2012:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri
Thu
Fri
roomKN:E-126
Matyáš P.
11:00–12:30
ODD WEEK

(lecture parallel1)
Karlovo nám.
Trnkova posluchárna K5
Time-table for summer semester 2011/2012:
Time-table is not available yet
The course is a part of the following study plans:
Generated on 2012-7-9
For updated information see http://bilakniha.cvut.cz/en/predmet11664304.html