Programming Methods (imperative approach) 1000-212aMPRI
1.Recursion: applications and implementation. Visibility of variables - local and global variables. Proving correctness of recursive procedures.
2.Divide-and-conquer method. Incrementation and binary split.
3.Pointer types. Application to the implementation of the list data model. Basic operations on lists. Two-way lists and cyclic lists.
4.Linear data types: stacks and queues. Array and list implementation of stacks and queues. Implementation of graph data type by lists of neighbours. Breadth-First-Search and Depth-First-Search.
5.Trees. Implementation of trees of any order. Binary trees. Tree traversals. Conversion of infix notation of expressions into Polish and Reverse-Polish notation.
6.Greedy programming. Huffman algorithm.
7.Dynamic programming. Knapsack problem. Optimal order of multiplication of many matrices.
Prerequisites: Introduction to Programming
Type of course
Prerequisites
Bibliography
1.Algorithms+Data Structures=Programs, N.Wirth, Prentice Hall 1976.
2.Introduction to ALgorithms, T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, MIT 1990.
3.Algorithms in C++, R.Sedgewick, Addison-Wesley, 1992
4.The Art of Computer Programming, vol. 1,3, Addison-Wesley, 1968, 1973
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: