Data Structures and Algorithm Analysis

Објавено: June 28, 2022
1. Course Title Data Structures and Algorithm Analysis
2. Code 4ФЕИТ07З017
3. Study program КТИ
4. Organizer of the study program (unit, institute, department) Faculty of Electrical Engineering and Information Technologies
5. Degree (first, second, third cycle) First cycle
6. Academic year/semester III/5 7. Number of ECTS credits 6
8. Lecturer D-r Daniel Denkovski
9. Course Prerequisites Passed: Programming and Аlgorithms, Data Structures and Programming
10. Course Goals (acquired competencies): Knowledge in data structures and algorithm design strategies. Ability to work with complex data structures in the Java programming language. Design of appropriate algorithms for the respective data structures. Ability to analyze algorithm complexity. After finishing this course the student will be able to solve problems using complex data structures and complex algorithms in Java.
11. Course Syllabus: Introduction to algorithm theory and basic concepts of data structures. Logical and physical structures. Implementation of a Java ADT. Algorithm analysis and algorithm complexity. Linear data structures – arrays and lists. Static and dynamic arrays and lists in Java. Application of arrays and lists for logical data structures: stack, queue, priority queue (in Java). Algorithmic strategies. Algorithm design. Algorithms classification. Brute force strategy. Greedy algorithms. Divide and conquer algorithms. Non-linear structures. Trees. Binary trees. Binary search trees. Balanced binary search trees. AVL trees. Red Black trees. Hash structures. Hash functions and their properties. Collisions and handling. Representation of graphs using data structures. Application of graphs (directed and nondirected, weighted graphs). Graph traversal algorithms: depth-first and breadth-first. Shortest path algorithms in weighted graphs. Bellman-Ford algorithm. Djikstra’s algorithm. Kruskal’s algorithm. Prim’s algorithm.
12. Learning methods: Theoretical and practical classes, laboratory exercises
13. Total number of course hours 2 + 2 + 1 + 0
14. Distribution of course hours 180
15. Forms of teaching 15.1. Lectures-theoretical teaching 30
15.2. Exercises (laboratory, practice classes), seminars, teamwork 45
16. Other course activities 16.1. Projects, seminar papers 0
16.2. Individual tasks 25
16.3. Homework and self-learning 80
17. Grading 17.1. Exams 0
17.2. Seminar work/project (presentation: written and oral) 0
17.3. Activity and participation 10
17.4. Final exam 90
18. Grading criteria (points) up to 50 points 5 (five) (F)
from 51to 60 points 6 (six) (E)
from 61to 70 points 7 (seven) (D)
from 71to 80 points 8 (eight) (C)
from 81to 90 points 9 (nine) (B)
from 91to 100 points 10 (ten) (A)
19. Conditions for acquiring teacher’s signature and for taking final exam Regular following of lectures and tutorial classes and complete fulfillment of all lab exercises
20. Forms of assessment Two partial written exams during the semester (in the middle and in the end of the semester) with a duration of 120 minutes each or one final written exam in a corresponding exam session with a duration of 120 minutes. The laboratory exercises are also graded. The final grade includes points from the exam and the lab exercises. Usage of books, hand-written materials or any kind of supplementary text book during the exam is not allowed.
21. Language Macedonian and English
22. Method of monitoring of teaching quality Internal evaluation and questionnaires
23. Literature
23.1. Required Literature
No. Author Title Publisher Year
1 T. H. Cormen, et al. Introduction to Algorithms, 3rd Ed. MIT Press 2009
2 R. Lafore Data Structures and Algorithms in JAVA, 2nd Ed. SAMS 2003
3 M. Goodrich and R. Tamassia Data Structures and Algorithms in Java, 6th Ed. John Willey 2014