Data Structures - Object Oriented Data Structures

Data Structures - Object Oriented Data Structures is a first year second semester computer science course that gives the students knowledge of the basic concepts of Object Oriented Design and the design and implementation of basic data structures such as queues, stacks, linked-lists, sorted linked-lists, and trees. More advanced data structures are also taught such as priority queues, heaps (both linked list implementations and array implementations) and balanced ("red-black") trees. Students are shown a variety of implementations for each of the above structures. As these data stuctures are taught, various concepts of Object Oriented Design are introduced such as inheritance, encapsulation, polymorphism, and the concept of code re-use. An emphasis is also place on implementing the above data structures using abstract data types. More advanced topics included in the course material are listed: approaches to implementing algorithms, analyzing efficiency of algorithms, advanced recursion, advanced sorting algorithms, and the fundamentals of multi-threading (in years when Java is used). There is an extensive accompanying lab which includes many serious projects and utilizes all subjects covered with practical examples.

Grading Policy

Attendance is required. Failure to attend at least 95% of the classes will mean the loss of Moed Bet privileges, unless the teacher is satisfied that the student had legitimate reasons for his absences.
Data Structures Course
Home work and attendance is worth 10% of the grade. Final exam is worth 90% of the grade.
Data Structures Targil
Home work and attendance is worth 10% of the grade. Final exam is worth 90% of the grade.
Seminar in C++ (Advanced C++)
Home work and attendance is worth 30% of the grade. Final exam is worth 70% of the grade.

Course Outline

Week 1 Dynamic Memory Allocation
Week 2 Classes
Week 3 Classes II
Week 4 Linked Lists
Week 5 Linked Lists II
Week 6 Fifo and Lifo
Week 7 Operator Overloading
Week 8 Bit Manipulation, Logic, Masks
Week 9 Files
Week 10 Binary Trees
Week 11 Binary Trees II
Week 12 Inheritance
Week 13 Generic Data Structures and Virtual Functions
Week 14 Advanced Sorting Algorithms
Week 15 Advanced Sorting Algorithms II

Textbooks

  1. C++ How to Program (5th Edition) (How to Program)
  2. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching (3rd Edition)
  3. Algorithms in C++ Part 5: Graph Algorithms (3rd Edition)

On-Line Help


Assignments:

Future Topics

  1. Josephus example for Circular lists
  2. simulations
  3. virtual destructor
  4. hide vs. overloaded function in base class
  5. RTTI
  6. singing waiter class
  7. stacks : validate parenthesis or nesting
  8. right threaded binary tree
  9. Euclids method for greatest common denominator
  10. prefix, infix, postfix notation, done with stacks
  11. avl trees
  12. B-trees
  13. Hashing
  14. fence register
  15. overlay
  16. DMA
  17. Rotational Ordering
  18. re-entrant code
  19. hybred systems
  20. buddy system
  21. asymptotic

References: