Skip to main content

Course Outlines

COMP 3761

Algorithm Analysis and Design

School School of Computing and Academic Studies
Program Computing Part-time Studies
Course Credits 4
Minimum Passing Grade 50%
Start Date January 10, 2018
End Date March 28, 2018
Total Hours 48
Total Weeks 12
Hours/Weeks 4
Delivery Type Lecture/Lab
Prerequisite(s) COMP 2121 and ( COMP 2611 or COMP 2613)
CRN 72095

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 Neilson Mackay
E-mail Instructor to provide
Location
Office Hours Instructor to provide

Course Description

In this hands-on course, Java programming students who have also taken Discrete Math will develop their ability to analyze and design computer algorithms. In particular, learners will analyze the time and space complexity of programs, solve nontrivial programming problems using algorithmic techniques, and prove that their solution is correct. The emphasis will be on developing the practical skills of analysis and design. Topics include: evaluating time and space complexity and designing solutions by using appropriate data structures or applying techniques such as recursion, parsing and graph algorithms.

Course Learning Outcomes/Competencies

Upon successful completion of this course, the student will be able to:

  • Understand the basic framework of algorithm analysis.
  • Analyze pseudo-code using asymptotic notations.
  • Compare the order of growth of different algorithms.
  • Understand the differences between nonrecursive and recursive algorithms.
  • Describe some common algorithm design strategies: Divide and Conquer, Transform and Conquer, Greedy Technique, Graph Algorithm, dynamic programming, etc.
  • Recognize different types of computing problems and how to solve them.
  • Apply algorithm design techniques to solve some practical problems.
  • Specify algorithms in pseudocode.
  • Implement solutions by using appropriate data structures.
  • Deduce the complexity of a program by running different experiments.
  • Argue the correctness of the algorithms.
  • Find lower bounds for some simple problems.

Learning Resources

Text: Introduction to the Design & Analysis of Algorithms, 3rd Edition
Author: Anany Levitin
ISBN-10: 0132316811
ISBN-13: 978-0132316811

ONLINE: This course uses the Desire2Learn (D2L) online system. Students must access this system regularly for announcements and learner support.

Evaluation Criteria

Criteria % Comments
Lab Assignments 25

Weekly assignments, 9 lab assignments in total

All lab assignments must be completed in order to pass this course.
Quizzes 20 Biweekly, 4 quizzes in total
Midterm Exam 25 You must average 50% or higher between the Midterm and Final Exam in order to pass this course.
Final Exam 30 You must average 50% or higher between the Midterm and Final Exam in order to pass this course.
Total 100

Assignments are to be completed by each student on an individual basis unless stated otherwise.

Assignments must be submitted to D2L prior to the due date. Late assignments will not be accepted. Emailed and/or in-person submissions will not be accepted.

Any form of plagiarism will result in a grade of ZERO for the first instance.

Note: the passing grade in this course is 50%. Students who earn less than 50% on the midterm exam and less than 50% on the final exam will be assigned a failing grade in the course.

Attendance Requirements

Please play this short video before the second lesson.

Welcome to Computing PTS - https://youtu.be/C0gtCxVO6f0

Please Note: By attending this course you agree to read this Student Guide.

Computing Part-time Studies Student Guide

PTS Attendance Policy

Attendance in lectures is mandatory.

  • 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.
  • Prolonged illness which causes the student to miss 20% or more of the lessons will require a BCIT -approved medical certificate submitted to the department, substantiating the reason for the absence.

Excessive absence of 20% or more may result in failure or forced withdrawal from this course.

Course Specific Requirements

COMP 2121 and COMP 2613

Or prior understanding of both Discrete Mathematics and Java Programming

NOTE:

CST Diploma day school students must have passed COMP 2121 and COMP 2526 before starting this course.

Course Schedule and Assignments

Week of

Material Covered

References / Reading

Assignment

1

Course Introduction

Algorithmic Efficiency

Orders of Growth

1.1, 1.4

2.1, 2.3

2

Brute Force

Exhaustive Search

3.1, 3.2, 3.4

- Assign 1

3

Decrease and Conquer

4.1, 4.3, 4.4

- Assign 2

- Quiz 1

4

Divide and Conquer

5.1, 5.2, 5.4

- Assign 3

5

Transform and Conquer

6.1, 6.4

- Assign 4

- Quiz 2

6

Space/Time Trade-offs

7.1, 7.2, 7.3

- Assign 5

7

Midterm

-

-

NOTE: Course Withdrawal Deadline
Please inform your instructor that you are dropping this course. You must also fill out and submit the 'REQUEST TO WITHDRAW FROM A PART-TIME STUDIES COURSE' before week 8 or else you will receive a failing grade on your academic record.

8

Data Structures and Graph

1.4, 3.5

- Assign 6

- Quiz 3

9

Graph Algorithms

3.5, 4.2, 5.3

- Assign 7

10

The Greedy Technique

9.1, 9.2, 9.3

- Assign 8

- Quiz 4

Course Evaluation: To be conducted online during Lesson 11 prior to the class break.
Students will have previously received a link to the survey via their myBCIT email. Those who do not have the link in their myBCIT email cannot complete this online evaluation.

If you did not receive the link please email: cstpts@bcit.ca at least 48 hours before lesson 11. Your instructor will leave the room for 15 minutes while each student logs in and completes this anonymous course evaluation.

11

Dynamic Programming, Final Review, Course Evaluation

8.1, 8.2, 8.4

- Assign 9

12

Final Exam

-

This schedule is tentative and subject to change; certain topics will take longer/shorter to cover in response to the needs of the students.

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 Disability Resource Centre (SW1 2360, 604-451-6963) at the earliest possible time. Requests for accommodation must be made to the Disability Resource Centre, 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 the Disability Resource Centre 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.
Neilson Mackay, Instructor
December 14, 2017

I verify that this course outline has been reviewed.
Kevin Cudihee, Program Head
December 26, 2017

I verify that this course outline has been reviewed and complies with BCIT policy.
Bethany Edmunds, Associate Dean
January 08, 2018

Note: Should changes be required to the content of this course outline, students will be given reasonable notice.