DSA555 - Data Structures and Algorithms in C++

Outline info
Semester
School
Last revision date May 30, 2022 12:44:11 AM
Last review date Aug 1, 2022 12:15:07 AM


Subject Title
Data Structures and Algorithms in C++

Subject Description
This is a survey course on algorithms and data structures commonly used in computer programs. Students taking this course will learn how these classical data structures and algorithms function. They will learn how to implement these data structures and apply them to real programming problems. Students will also learn how these data structures are used to implement parts of the standard language libraries. Furthermore, the course will also introduce students to computational theory. This course is meant to provide students with a fundamental background to computer science concepts.

Credit Status
1 credit (3 units)
Professional Option for CPA - Computer Programming and Analysis (Ontario College Advanced Diploma)
Professional Option for CPD - Computer Programmer (Ontario College Diploma)

Learning Outcomes
Upon successful completion of this subject the student will be able to:

  1. Analyze algorithms and data structures for resource usage to design optimal programs
  2. Explain the relationship between resource use growth rates and observed algorithmic behavior to forecast performance
  3. Use pseudo code and diagrams to explain how data structures and algorithms are implemented
  4. Implement custom linked-list structures to extend the behavior of language specific libraries 
  5. Explain the P vs NP problem to recognize the limitations of computation
  6. Implement key-based container classes to retrieve data quickly and efficiently 
  7. Use graph data structures to store information about relationships between objects

Essential Employability Skills
    •  Execute mathematical operations accurately.

    •  Apply a systematic approach to solve problems.

    •  Manage the use of time and other resources to complete projects.

Academic Integrity
Seneca upholds a learning community that values academic integrity, honesty, fairness, trust, respect, responsibility and courage. These values enhance Seneca's commitment to deliver high-quality education and teaching excellence, while supporting a positive learning environment. Ensure that you are aware of Seneca's Academic Integrity Policy which can be found at: http://www.senecapolytechnic.ca/about/policies/academic-integrity-policy.html Review section 2 of the policy for details regarding approaches to supporting integrity. Section 2.3 and Appendix B of the policy describe various sanctions that can be applied, if there is suspected academic misconduct (e.g., contract cheating, cheating, falsification, impersonation or plagiarism).

Please visit the Academic Integrity website http://open2.senecac.on.ca/sites/academic-integrity/for-students to understand and learn more about how to prepare and submit work so that it supports academic integrity, and to avoid academic misconduct.

Discrimination/Harassment
All students and employees have the right to study and work in an environment that is free from discrimination and/or harassment. Language or activities that defeat this objective violate the College Policy on Discrimination/Harassment and shall not be tolerated. Information and assistance are available from the Student Conduct Office at student.conduct@senecapolytechnic.ca.

Accommodation for Students with Disabilities
The College will provide reasonable accommodation to students with disabilities in order to promote academic success. If you require accommodation, contact the Counselling and Accessibility Services Office at ext. 22900 to initiate the process for documenting, assessing and implementing your individual accommodation needs.

Camera Use and Recordings - Synchronous (Live) Classes
Synchronous (live) classes may be delivered in person, in a Flexible Learning space, or online through a Seneca web conferencing platform such as MS Teams or Zoom. Flexible Learning spaces are equipped with cameras, microphones, monitors and speakers that capture and stream instructor and student interactions, providing an in-person experience for students choosing to study online.

Students joining a live class online may be required to have a working camera in order to participate, or for certain activities (e.g. group work, assessments), and high-speed broadband access (e.g. Cable, DSL) is highly recommended. In the event students encounter circumstances that impact their ability to join the platform with their camera on, they should reach out to the professor to discuss. Live classes may be recorded and made available to students to support access to course content and promote student learning and success.

By attending live classes, students are consenting to the collection and use of their personal information for the purposes of administering the class and associated coursework. To learn more about Seneca's privacy practices, visit Privacy Notice.

Prerequisite(s)
OOP344 or OOP345

Topic Outline

  •   Introduction - 5%
  •   Analysis - Big-O, Little-o, Theta and Omega  Notation - 20%
    •         Big-O Notation
    •         Little-o Notation
    •         Theta Notation
    •         Omega Notation
  •  Linked Lists - 10%
  • Searching and Sorting 10%
    •         Linear Search
    •         Binary Search
    •         Bubble Sort
    •         Insertion Sort
    •         Selection Sort
    •         Heap Sort
    •         Merge Sort
    •         Quick Sort
  •     Hash Tables - 10%
  •     Recursion - 5%
  •     Trees - 20%
    •         binary heaps
    •         binary search trees
    •         avl trees
    •         red-black trees
    •         two-three trees
  •     Queues and Stacks - 5%
  •     Graphs - 5%
  •     Complexity Theory - 10%

Mode of Instruction
Modes: In-class lecture, in-class exercises, and hands-on activity
Hours per week: 4
Room configurations: Classroom, and computer lab
Typical scheduling pattern: Varies, at least once in Fall or Winter

Prescribed Texts

https://www.gitbook.com/book/cathyatseneca/data-structures-and-algorithms/details

Reference Material
Data Structures and Algorithm Analysis in C++ (4th Edition)
By Mark Allen Weiss
ISBN: 978-0132847377

Required Supplies
None

Student Progression and Promotion Policy
To obtain a credit in this subject, a student must:

  •     Achieve a grade of 50% or better on the final exam
  •     Satisfactorily complete all assignments
  •     Achieve a weighted average of 50% or better for the tests and final exam
  •     Achieve a grade of 50% or better on the overall course

http://www.senecapolytechnic.ca/about/policies/student-progression-and-promotion-policy.html

Grading Policyhttp://www.senecapolytechnic.ca/about/policies/grading-policy.html

A+ 90%  to  100%
A 80%  to  89%
B+ 75%  to  79%
B 70%  to  74%
C+ 65%  to  69%
C 60%  to  64%
D+ 55%  to  59%
D 50%  to  54%
F 0%    to  49% (Not a Pass)
OR
EXC Excellent
SAT Satisfactory
UNSAT Unsatisfactory

For further information, see a copy of the Academic Policy, available online (http://www.senecapolytechnic.ca/about/policies/academics-and-student-services.html) or at Seneca's Registrar's Offices. (https://www.senecapolytechnic.ca/registrar.html).


Modes of Evaluation

Assignments 30%
Test(s) 30%
Labs 10%
Final Exam 30%

Approved by: Mary-Lynn Manton