Course unit description



Pobieranie 19.47 Kb.
Data02.05.2016
Rozmiar19.47 Kb.
Rzeszów University of Technology


The Faculty of:

Electrical and Computer Engineering

Field of study:


Computer Science

Speciality:




Study degree (BSc, MSc):

BSc


COURSE UNIT DESCRIPTION


Course title:

Algorithms and Data Structures

Lecturer responsible for course: dr inż. Krzysztof Świder
Contacts: phone: +17 865 1548 e-mail: kswider@prz-rzeszow.pl


Department: Computer Science and Automatic Control




Semester

Weekly load

Type of classes

Number of ECTS credits

L

Lectures

C

Theoretical Classes

Lb

Laboratory

P

Project

2


4

30

15

15




5


Course description


Lecture:

Basic notions concerning algorithms. Asymptotic notations and their mathematical interpretation. Model of RAM-machine and RAM commands. Use of pseudo-code. Computational complexity of programs. The notions of time and memory complexities and complexity estimation. Memory representations and basic operations on selected dynamic structures (lists, stacks, queues and graphs). Tree-like structures and their features. Binary trees. Recursion. Binary search trees (BST) and their characteristics. Operations on BST. Definition, essential qualities and basic algorithms relating to heap. Priority queues. Searching on trees (breath-first, depth-first and best-first strategies). Generating of solution paths. Sorting - definitions and problem statement. Explanation and complexity estimation of selected sorting algorithms. Mathematical proof of correctness for a selected sorting method. Advanced strategies – dynamic programming and greedy algorithms.




Classes and laboratory:

Practical use of asymptotic notations. Simple algorithms and their representation in pseudo-code. Example RAM-programs. Time and memory complexity estimation. Examples using lists, stacks and queues. Solving problems with recursion. Programming operations on BST. Solving problems by searching the trees. Construction and practical verification of selected sorting algorithms.






Objectives of the course

Obtain knowledge and skills necessary to: (a) construct algorithms with use of most popular techniques, (b) operate with common data structures.




Examination method

Written solution of problems and oral discussion.






Bibliography





  1. Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych. Helion 2003.

  2. Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych. PWN 1983 (ew. wyd. późniejsze).

  3. Cormen T.H., Leiserson C.E,, Rivest R.L.: Algorytmy i struktury danych. WNT 1996 (ew. wyd. późniejsze).




    1. Banachowski L., Diks K., Rytter W.: Wprowadzenie do algorytmów. WNT 1997.

    2. Banachowski L., Kreczmar A.: Elementy analizy algorytmów. WNT 1982.

    3. Drozdek A., Simon D.L..: Struktury danych w języku C. WNT, 1996.

    4. Knuth D.E.: Sztuka programowania. Tom 1. Algorytmy podstawowe. WNT 2002.

    5. 5. Wróblewski P.: Algorytmy, struktury danych i techniki programowania. Helion 1996.






Lecturer signature




Head of Department signature




Dean signature




: files -> 1011




©absta.pl 2019
wyślij wiadomość

    Strona główna