Winter Semester 2010/11
Winter Semester 2011/12
Winter Semester 2012/13
Winter Semester 2013/14
Winter Semester 2014/15
Algorithms and Data Structures MAT2305
Course content:
Sorting:
Bucket sort,
Heapsort,
Inserion Sort,
Merge-Sort,
Quicksort,
Elementary Data Structures:
Stacks and Quees,
Linked Lists,
Trees:
- Binary Search Trees,
- 2-3 Trees,
Hash Tables,
Algebra algorithms:
Knuth-Morris-Pratt Algorithm,
Matrix Chain Multiplication,
Strassen Algorithm,
Multiplication of Polynomials (Fast Fourier Transform),
Graph Algorithms:
Representation of Graphs,
Breadth-First Search,
Depth-First Search,
Minimum Spanning Trees,
Shortest Paths:
Bellman-Ford Algorithm,
Dijkstra's Algorithm,
Floyd-Warshall Algorithm,
Flow Networks:
- maximal flow Ford-Fulkerson method,
- maximum bipartite matching,
- maximal selectors,
NP Problems,
Problems of greater to polynomial complexity,
Learning outcomes:
Students should be acquainted with basic methods of the analysis of algorithms and basic strategies of projecting effective algorithms (operating on suitable data structures).
Course coordinators
Term 2014Z: | Term 2013Z: | Term 2010Z: | Term 2011Z: |
Bibliography
a) basic references:
Aho A.V., Hopcroft J.E. UllmanJ.D.: Design and Analysis
of Computer Algorithms, Addison-Wesley, New York 1974
(Polish translation)
Cormen T.H., Leiserson C.E., Rivest R.I., Stein C.:
Introduction to Algorithms, WNT, MIT Press
& McGraw-Hill Book Comp., New York 2003
(Polish translation)
Lipski W.: Combinatorics for programmers, (in Polish)
WNT, Warszawa 1988
b) supplementary references: