Course Description

 IT 212 Data Structure

Text book:

  • Frank M. Carrano, Data Structures and Abstractions with java, 3rdEd., Pearson.

Course Description:

This course emphasized the importance of information hiding and how to use abstraction in good program design. Students will be able to estimate algorithms growth rates and describe it using big O notation. Various Sorting and searching techniques including Hashing will be studied and their performances compared. Similarly, various data structures their representations, traversal, and application will be studied and compared. These data structures include at least: lists, stacks, queues, trees, and graphs. For trees: binary trees, search trees, height-balanced trees, and Heaps will be discussed; For graphs: Depth-First Traversal, Breadth-First Traversal, and Shortest/Cheapest path algorithms will be covered.

Course Learning Outcomes:

  1. Recognize the concepts of different ADTs such as: lists, stacks, queues, trees and graphs. And be able to describe them
  2. Differentiate between alternative ADT’s and choose most suitable for a specific application.
  3. Design fundamental data abstractions and apply object oriented design principles such as encapsulation, information hiding, and implementation independence.
  4. Implement suitable ADT’s for a given problem
  5. Demonstrate algorithms applied to different ADT’s, in addition to various sorting, and searching techniques
  6. Estimate the efficiency of various algorithms.

Topics to be covered:

  • Bags
  • Efficiency: Time & Space Complexity, Big-O notation.
  • Stacks
  • Queues, Deques and priority queues
  • Lists
  • Iterators
  • Sorted lists
  • Searching
  • Hashing
  • Trees: terminology, BT, BST
  • Heaps and Heap Sort
  • Trees continued: AVL – B-Trees
  • Hashing
  • Graphs
  • Sorting

Grades distribution:

  • Course Work (60%)
    • Quizzes (3) – 12%
    • Exams (2) – 24%
    • Activities – 4%
    • Tutorial –  5 %
    • Programming Assignments- 8%
    • Final Lab  – 7%
  • Final (40%)
    • Final Exam – 40%

 

Regulations and guidelines:

  • All homework assignments are due one week after the assignment date.
  • Students are encouraged to discuss homework problems but not copy.
  • All exams are closed book (ADTs specification is allowed during the exam). Except for the practical exam which is an open book exam.
  • The final exam will be comprehensive.
  • The students are required to solve the sheets and programming assignments as groups of two or three members. They should not share their solutions nor seek any. If we detect that a solution match or resemble any other groups, both groups members will get a – 10 out of 10 marks. The students involved will be cross-examined by a departmental committee to determine the cheater’s penalty.
  • Handing the sheet should be at the same date it is due in the tutorial or lecture time, unless stated otherwise. If the student do not hand the sheet within the due time, it will be ignored. But for programming assignments, 0.25 grade will be subtracted for each late day.
  • Applications handed in the CD should have no compilation errors. If an application has any errors, it will be ignored. However, incomplete applications are more tolerated.  A student may earn a good mark even if your application is not 100% complete.

Leave a comment