Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT
| MIE0001 | Data Structures and Algorithms |
| Teaching Staff in Charge |
Assoc.Prof. SERBAN Gabriela, Ph.D., gabis cs.ubbcluj.roAssoc.Prof. NICULESCU Virginia, Ph.D., vniculescu cs.ubbcluj.roLect. IONESCU Clara, Ph.D., clara cs.ubbcluj.roLect. CIOBAN Vasile, Ph.D., vcioban cs.ubbcluj.roLect. TRÎMBITAS Gabriela, Ph.D., gabitr cs.ubbcluj.ro |
| Aims |
|
- to study the concept of abstract data types (ADT) and the most used ADTs in application development;
- to study the data structures used to implement these ADTs (arrays, linked lists, binary trees, hashing tables, etc.); - to create the ability to design and build applications starting from abstract data types; - to create the ability to work with data stored different data structures: arrays, linked lists, binary trees, hashing tables, stacks, queues, graphs, trees; - to create the ability to compare the cost of static and dynamic allocation for different data structures; - to create the ability to choose the appropriate structure for a certain application; - to create the ability to design and implement algorithms that use these data structures; - to improve the ability to evaluate the complexity of the algorithms. |
| Content |
|
1. Introduction. Data Structures. Static, semistatic, and dynamic structures. [1, ch. 1, 2] (1 lecture – S1 + 1 seminar – S1 / S2)
- Abstractness and data encapsulation - Dynamic sets - Complexity 2. Data Types: domain, operations and data representation [6, ch. 5] (1 lecture – S2) - Abstract Data Types: domain and operations - Requirements, interface, implementation (implementations) - Abstract Data Types Design Array - Description, properties - Strings, substrings, subsequences, matrix - Dynamic Arrays: operations: insertion / deletion, sequential and binary search - Merging - Sorting: mergesort, ranksort, radixsort, bucketsort etc. 3. ADT Collection [1, ch. 5] (1 lecture – S3) - Related concepts - Related applications - Specifications and design - Representations using arrays, linked lists, hash tables, and binary trees ADT Set - Related concepts - Related applications - Specifications and design - Representations using arrays, linked lists, hash tables, and binary trees 4. ADT Map [4, ch. 6] (1 lecture – S4+ 1 seminar – S3 / S4) - Related concepts - Related applications - Specifications and design - Representations using arrays, linked lists, hash tables, and binary trees - Sorted map 5. ADT List [1, ch. 11] (2 lectures – S5, S6+ 2 seminars – S5, S7 / S6, S8) - Related concepts - Related applications - Specifications and design - Representations using arrays and linked lists - Sorted Lists Linked List - Description, properties - Singly, doubly and circular linked lists – dynamic allocation - Linkage on arrays - Operations: insertion / deletion, searching, traversal 6. ADT Stack [1, ch. 11] (1 lecture – S7) - Related concepts - Related applications - Specifications and design - Representations using arrays and linked lists 7. ADT Queue [1, ch. 11] (1 lecture – S7) - Related concepts - Related applications - Specifications and design - Representations using arrays and linked lists 8. ADT Priority Queue [1, ch. 7] (1 lecture – S8+ 1 seminar – S9 / S10) - Related concepts - Related applications - Specifications and design - Representations using arrays and linked lists 9. Hash-table [1, ch. 12] (1 lecture – S9, S10+ 1 seminar – S11 / S12) - Direct Addressing - Description, properties - Open and Closed Hash-tables - Collisions resolution: chaining, interleaved lists and open addressing - Operations: searching, insertion / deletion 10. ADT Tree [1, ch. 13] (1 lecture – S11 + 1 seminar – S13 / S14) - Related concepts - Related applications - Specifications and design - Linked Representation - ATD Tree with different properties Binary Tree - Description, properties - Search Binary Tree - Operations: searching, insertion / deletion, traversal 11. Heaps [1, ch. 7] (1 lecture – S12) - The structure presentation - Binary Heap - Priority Queue representation using a heap - HeapSort 12. Balanced Search Trees [1, ch. 14; 3, Lecture 9] (1 curs – S13) - AVL Trees - Red-Black Trees 13. ADT Graph [1, ch. 23] (1 curs – S14) - Related concepts - Related applications - Specifications and design |
| References |
|
1. CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.: Introducere în algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000.
2. HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995. 3. MOUNT, DAVID M.: Data Structures. University of Maryland, 1993. 4. AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. 5. WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976. 6. STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995 7. SEDGEWIK: Algorithmen 8. Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, Cluj-Napoca, 2006 |
| Assessment |
|
Each student will receive a list of problems that must be solved during the term. For this homework the student will receive a first grade (A). Each student will receive a grade to a written paper at the middle of the term (B). At the end of the term the student must take an exam for which he will receive a third grade (C). The final grade will be computed as (2*A+2*B+6*C)/10. The access to the written paper is conditioned by the grade (A), which has to be at least 5. In order to promote the final exam, grade (C) and the final grade has to be at least 5.
|
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |