ID: 7012
Course type: scientific and vocational
Course coordinator: Jandrlić R. Davorka
Lecturers: Jandrlić R. Davorka
Contact: Jandrlić R. Davorka
Level of studies: B.Sc. (undergraduate) Academic Studies – Information Technologies in Mechanical Engineering
ECTS: 5
Final exam type: written+oral
Department: Department of Mathematics
Enhancing and application of basic knowledge about data structures, fundamental algorithms, analysis, and algorithm construction strategies.
Upon completion of the course, the student has a basic knowledge of construction and algorithm analysis. He is able to apply the acquired knowledge to solve new problems, and make the optimal choice of the appropriate algorithm and data structure for a specific problem.
1) Analysis of algorithms: asymptotic analysis of the worst and average case; asymptotic notation О, о, Ω, Θ; time and space complexity; 2) Graphs: basics, traversing algorithms - depth first search, breadth first search 3) Graphs: finding shortest paths between nodes 4) Graphs: topological sorting 5) Strings, string-matching, naive algorithm 6) Knuth–Morris–Pratt string-matching algorithm 7) Other string-matching algorithms (Boyer–Moore, Rabin–Karp, ...) 8) Recursion and recursive algorithms 9) Big numbers and operations 10) Backtracking 11) Dynamic programming
Examples, implementation and application of: 1) Graphs: representation, depth first search, breadth first search 2) Graphs: finding shortest paths between nodes 3) Graphs: topological sorting 4) Strings, string-matching, naive algorithm 5) Knuth–Morris–Pratt string-matching algorithm 6) Other string-matching algorithms (Boyer–Moore, Rabin–Karp, ...) 7) Recursion and recursive algorithms 8) Big numbers and operations 9) Backtracking 10) Dynamic programming
-
-
Total assigned hours: 60
New material: 16
Elaboration and examples (recapitulation): 4
Auditory exercises: 20
Laboratory exercises: 6
Calculation tasks: 0
Seminar paper: 0
Project: 4
Consultations: 0
Discussion/workshop: 0
Research study work: 0
Review and grading of calculation tasks: 0
Review and grading of lab reports: 0
Review and grading of seminar papers: 0
Review and grading of the project: 0
Test: 8
Test: 0
Final exam: 2
Activity during lectures: 0
Test/test: 60
Laboratory practice: 0
Calculation tasks: 0
Seminar paper: 0
Project: 0
Final exam: 40
Requirement for taking the exam (required number of points): 0
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, Cambridge, 2009. ; Robert Sedgewick, Algorithms in C. 3rd Edition, 1997.; М. Живковић, Algorithms, Математички факултет, Београд, 2000 (in Serbian)