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 |