Mathematics BSc
Course description
2013.
Course description
2013.
Design and analysis of algorithms 1
Hours lect+pc |
Credits lect+pc |
Assessment | Specialization | Course code lect/pc |
Semester | Status |
---|---|---|---|---|---|---|
2 + 2 | 2 + 3 | exam + term grade |
applied math. | mm1c1at4a mm1c2at4a |
4 | compulsory |
Course coordinator
- László Hunyadvári
- István Fekete
Strong | Weak | Prerequisites | |
---|---|---|---|
Practice class | |||
Strong:
Programming fundamentalsL
(im1c1pn2)
| |||
Lecture | |||
Weak:
practice class
|
Remarks
Syllabus designed by:
- László Hunyadvári, Department of Algorithms and their Applications, Faculty of Informatics.
- István Fekete, Department of Algorithms and their Applications, Faculty of Informatics.
Literature
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. The MIT Press, 2009.
Recommended:
- D. E. Knuth: The Art of Computer Programming, I. and III. Addison-Wesley Professional, 1998.
- S. Lipschutz: Data Structures. McGraw-Hill, 2005.
- N. Wirth: Algorithms + Data Structures = Programs. Prentice Hall, 1976.
- A. Aho, J. Hopcroft, J. Ullman: Data Structures and Algorithms. Addison-Wesley, 1983.
Syllabus
- Abstract concepts of programming: state space, problem specification, solution, abstract program. Constructing correct programs, program correctness proof. Simple widely used small programs.
- Algorithmic solvability of problems, time and space complexity, asymptotic estimation of resources, order of growth.
- Abstraction levels of data types: „abstract data type” (ADT), „abstract data structure” (ADS), representation (by arrays or pointers).
- Basic data structures: arrays, stacks, queues, priority queues, lists, trees.
- Selections: maximum, parallel minimum and maximum, kth largest element and median. Lower bound analysis.
- Sorting algorithms using comparisons. Principles of the sorting methods. Bubble sort, insertion sort and sorting with maximum search. Tournament sort, heapsort, quicksort, merge sort, Shell-sort, Batcher’s bitonic sort. Lower bounds of efficiency: worst case and average case analysis.
- Search methods on associative data structures (1). Sequential search, binary search, search trees, AVL-trees, B-trees.