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
-
C++ How to Program (5th Edition) (How to Program)
- Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching (3rd Edition)
-
Algorithms in C++ Part 5: Graph Algorithms (3rd Edition)
On-Line Help
Assignments:
Future Topics
- Josephus example for Circular lists
- simulations
- virtual destructor
- hide vs. overloaded function in base class
- RTTI
- singing waiter class
- stacks : validate parenthesis or nesting
- right threaded binary tree
- Euclids method for greatest common denominator
- prefix, infix, postfix notation, done with stacks
- avl trees
- B-trees
- Hashing
- fence register
- overlay
- DMA
- Rotational Ordering
- re-entrant code
- hybred systems
- buddy system
- asymptotic
References: