COMP 8042
Advanced Algorithms and Data Structures Design and Analysis
School | School of Computing and Academic Studies |
---|---|
Program | Bachelor of Technology - Computer Systems, Games Development Option |
Course Credits | 3 |
Minimum Passing Grade | 60% |
Start Date | April 10, 2019 |
End Date | June 26, 2019 |
Total Hours* | 45 |
Total Weeks | 12 |
Hours/Weeks | 3.75 |
Delivery Type | Lecture/Lab |
Prerequisite(s) | MATH 7908 |
CRN | 66092 |
Acknowledgement of Territories
The British Columbia Institute of Technology acknowledges that our campuses are located on the unceded traditional territories of the Coast Salish Nations of Sḵwx̱wú7mesh (Squamish), səl̓ilwətaɁɬ (Tsleil-Waututh), and xwməθkwəy̓əm (Musqueam).
Instructor Details
Name | Borna Noureddin |
---|---|
Instructor to provide | |
Location | SW2-321 |
Office Hours | Instructor to provide |
Course Description
The objective of this course is to apply concepts and problem-solving techniques that are used in the design and analysis of efficient algorithms. This course will provide students with exposure and practice to more advanced data structures and algorithmic strategies used in software development. Students will identify real world problems and apply a heuristic approach to solve them. After reviewing basic data structures and algorithms, students will apply advanced analysis techniques and algorithms. Particular emphasis will be placed on efficiency and optimization.
Course Learning Outcomes/Competencies
Upon successful completion of this course, the student will be able to:
- Design and analyze data structures (including advanced tree data structures, dictionaries, hash tables, heaps, and priority queues)
- Apply a heuristic approach to problem solving.
- Apply the most appropriate and optimal solution for problem solving using fundamental algorithms (including greedy, divide-and-conquer, and dynamic programming) and advanced algorithms.
- Apply mapping of real-world problems to algorithmic solutions (including graph problems).
- Apply advanced techniques to algorithms (including probabilistic and Big O analysis).
- Design finite state machines for practical problems.
Learning Resources
Required:
Weiss, “Data Structures and Algorithm Analysis in C++, 4/E”, Pearson, 2014, ISBN 9780132847377
Readings provided in class.
Recommended:
Main & Savitch, “Data Structures and Other Objects Using C++, 4/E”, Pearson, 2011, ISBN 9780132129480
Levitin, “Introduction to the Design and Analysis of Algorithms, 3/E”, Pearson, 2010, ISBN 9780132316811
Evaluation Criteria
Criteria | % | Comments |
Quizzes | 15 | |
Assignments | 40 | |
Class participation | 5 | |
Final exam | 40 |
Attendance Requirements
This is a hybrid course.
There are four in-person classes, including the final exam. Attendance in those classes is mandatory. The remainder of the course is delievered online through D2L.
In case of illness or other unavoidable cause of absence, the student must communicate as soon as possible with his/her instructor indicating the reason for the absence.
NOTE: The passing grade for this course is 60%.
Course Schedule and Assignments
There will be at least three assignments in this course, which you will be required to submit individually unless otherwise specified.
Details on the assignments and project will be provided in class.
As well, there will be three quizzes and a final exam. These assessments will be done during the in-person class times.
Course details are subject to change with sufficient prior notification to students.
Course topics
Week | Topic | Due | |
1 MANDATORY CLASS | 10-Apr | Course overview and review of C++ | |
17-Apr | General purpose data structures (Ch 3, 5, 6) | ||
24-Apr | Finite State Machines | ||
01-May | Algorithm Analysis (Ch 2) | Assignment 1 | |
5 MANDATORY CLASS | 08-May | Graphs and graph traversal (Ch 9) | Quiz 1 |
15-May | Binary trees, search trees, quadtrees (Ch 6) | ||
22-May | Sorting and other major algorithm techniques (Ch 7) | Assignment 2 | |
8 MANDATORY CLASS | 29-May | Hashing (Ch 7) | Quiz 2 |
05-Jun | Heaps (Ch 6) | ||
12-Jun | Algorithm design (Ch 6, 10) | ||
19-Jun | DFS and graphs (Ch 9) | Assignment 3 | |
12 MANDATORY CLASS | 26-Jun | Final exam |
BCIT Policy
The following statements are in accordance with the BCIT Policies 5101, 5102, 5104, and 7507, and their accompanying procedures. To review these policies and procedures please click on the links below.
Attendance/Illness:
In case of illness or other unavoidable cause of absence, the student must communicate as soon as possible with his/her instructor or Program Head or Chief Instructor, indicating the reason for the absence. Students who are seeking accommodation for a medical absence must have a BCIT approved medical certificate submitted to the department, substantiating the reason for absence. For other absences, the student should be prepared to provide appropriate supporting documentation. Unapproved absence in excess of the prescribed regulations within this outline may result in failure or forced withdrawal from the course or program. Please see Policy 5101 - Student Regulations, and accompanying procedures.
Academic Integrity:
Violation of academic integrity, including plagiarism, dishonesty in assignments, examinations, or other academic performances are prohibited and will be handled in accordance with Policy 5104 - Academic Integrity and Appeals, and accompanying procedures.
Accommodation:
Any student who may require accommodation from BCIT because of a physical or mental disability should refer to BCIT's Policy on Accommodation for Students with Disabilities (Policy #4501), and contact BCIT's Accessibility Services (SW1 2360, 604-451-6963) at the earliest possible time. Requests for accommodation must be made to Accessibility Services, and should not be made to a course instructor or Program area.
Any student who needs special assistance in the event of a medical emergency or building evacuation (either because of a disability or for any other reason) should promptly inform their course instructor(s) and Accessibility Services of their personal circumstances.
Human Rights, Harassment and Discrimination:
The BCIT community is made up of individuals from every ability, background, experience and identity, each contributing uniquely to the richness and diversity of the BCIT community as a whole. In recognition of this, and the intrinsic value of our diversity, BCIT seeks to foster a climate of collaboration, understanding and mutual respect between all members of the community and ensure an inclusive accessible working and learning environment where everyone can succeed.
Campus Mediation Services is a supportive resource for both students and employees of BCIT, to foster a respectful learning and working environment. Any student who feels that they are experiencing discrimination or harassment (personal or human rights-related) can confidentially access this resource for advice and support. Please see Policy 7507 – Harassment and Discrimination and accompanying procedure.
Students should make themselves aware of additional Education, Administration, Safety and other BCIT policies listed at https://www.bcit.ca/about/administration/policies.shtml
Guidelines for School of Computing and Academic Studies
Attempts:
Students must successfully complete a course within a maximum of three (3) attempts at the course. Students with two attempts in a single course will be allowed to repeat the course only upon special written permission from the Associate Dean. Students who have not successfully completed a course within three attempts will not be eligible to graduate from their respective program.
Approved
I verify that the content of this course outline is current.
Borna Noureddin, Instructor
March 26, 2019
I verify that this course outline has been reviewed.
Mirela Gutica, Program Head
March 28, 2019
I verify that this course outline has been reviewed and complies with BCIT policy.
Aaron Hunter, Acting Assicate Dean
March 29, 2019
Note: Students will be given reasonable notice if changes are required to the content of this course outline.
*Course hours and credits are calculated per Policy 5012 and the associated procedure.
Total hours – Example of 3 credit lecture/lab course:
- Full-time course: 45 hours of scheduled learning
- Flexible Learning course: 36 hours of scheduled learning plus 9 hours of independent (non-scheduled, non-instructional) learning