MIE0001  Data Structures and Algorithms 
Teaching Staff in Charge 
Assoc.Prof. SERBAN Gabriela, Ph.D., gabiscs.ubbcluj.ro Assoc.Prof. NICULESCU Virginia, Ph.D., vniculescucs.ubbcluj.ro Lect. IONESCU Clara, Ph.D., claracs.ubbcluj.ro Lect. CIOBAN Vasile, Ph.D., vciobancs.ubbcluj.ro Lect. TRÎMBITAS Gabriela, Ph.D., gabitrcs.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. Hashtable [1, ch. 12] (1 lecture – S9, S10+ 1 seminar – S11 / S12)  Direct Addressing  Description, properties  Open and Closed Hashtables  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  RedBlack 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. ClujNapoca: 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, AddisonWesley, 1995 7. SEDGEWIK: Algorithmen 8. Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, ClujNapoca, 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 