RYERSON UNIVERSITY

Course Outline (W2022)

COE428: Engineering Algorithms and Data Structures

Instructor(s)Dr. Reza Samavi [Coordinator]
Office: ENG457
Phone: (416) 979-5000 x 554903
Email: samavi@ryerson.ca
Office Hours: Fri 12:00-14:00 on Zoom - please email to make an appointment
Calendar DescriptionThe main topics covered in this course include basic data structures (arrays, pointers), abstract data structures (trees, lists, heaps), searching, sorting, hashing, recursive algorithms, parsing, space-time complexity, NP-complete problems, software engineering and project management, object-oriented data structures. Case studies and lab exercises will be implemented using a high level programming language. (Formerly ELE 428.)
PrerequisitesCOE 318
Antirequisites

None

CorerequisitesMTH 314
Compulsory Text(s):
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms, Third Edition, MIT Press, 2009, ISBN: 978-81-203-4007-7
Reference Text(s):
  1. Knuth, Donald Ervin, The Art Of Computer Programming (3 volumes) Addison-Texts Wesley,1977. This is the classic book on computer programming, algorithms, and data structures. It is very mathematical and also has extensive problems and solutions.
  2. Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999, ISBN:0-201-61586-X, 267 pages. This excellent book will help you hone your programming skills in any language (although the emphasis is on C).
  3. Standish, Thomas A., Data Structures, Algorithms and Software Principles in C, Addison-Wesley 1995, ISBN: 0-201-59118-9
  4. Brian W. Kernighan, Dennis Ritchie, The C Programming Language, Prentice-Hall, 2nd edition 1988. This is the classic book on C, written by the language developers.
  5. Laboratory Manual: Available through the course web page:http://www.ee.ryerson.ca/~courses/coe428
Learning Objectives (Indicators)  

At the end of this course, the successful student will be able to:

  1. Develop knowledge of designing and analyzing algorithms that can be used to solve various computational problems in the domain of engineering. (1a)
  2. Apply mathematical principles to determine the run-time complexity (best, worst and average cases) of various algorithms. Learn about various asymptotic notations used for bounding the algorithm running times and develop knowledge on how to solve recurrence equations. (1b)
  3. Learn about various data structures (e.g. stacks, queues, linked lists, binary search trees, red black trees, priority queues, heaps, hash tables etc.) that can be applied to construct efficient algorithms for a variety of engineering problems. (1c)
  4. Analyze the efficiency of various Graph algorithms that are used in solving network related problems. The analysis will help to rank/rate alternative algorithms for a given problem. (4b)
  5. Compare different approaches for designing algorithms such as incremental approach versus divide-and-conquer approach. Learn how to select the best design alternative for a given input size of a problem. (4c)
  6. Follow lab and exam instructions and develop required algorithms. (7a)

NOTE:Numbers in parentheses refer to the graduate attributes required by the Canadian Engineering Accreditation Board (CEAB).

Course Organization

3.0 hours of lecture per week for 13 weeks
2.0 hours of lab per week for 12 weeks
0.0 hours of tutorial per week for 12 weeks

Teaching AssistantsSections 01 & 05 & 13: Thong Vo (thong.vo@ryerson.ca)
 Sections 02 & 14 & 17: Behzad Mahasseni (behzad.mahaseni@ryerson.ca)
 Sections 03 & 11 & 16: Meghan Muldoon (meghan.muldoon@ryerson.ca)
 Sections 04 & 08 & 09: Sajjad Sani (srostamisani@ryerson.ca)
 Sections 06 & 15 & 18: Hirad Daneshvar (hirad.daneshvar@ryerson.ca)
 Sections 07 & 10 & 12: Hina Tariq (hina1.tariq@ryerson.ca)
 
Course Evaluation
Theory
Mid-term Examination 35 %
Final Examination 40 %
Laboratory
Labs 25 %
TOTAL:100 %

Note: In order for a student to pass a course, a minimum overall course mark of 50% must be obtained. In addition, for courses that have both "Theory and Laboratory" components, the student must pass the Laboratory and Theory portions separately by achieving a minimum of 50% in the combined Laboratory components and 50% in the combined Theory components. Please refer to the "Course Evaluation" section above for details on the Theory and Laboratory components (if applicable).


ExaminationsMidterm exam in Week 7, two hours, problems, closed book (covers Weeks 1-6).
 Final exam, during exam period, 2-3 hours, closed-book (covers Weeks 1-13).
Other Evaluation InformationIn order to achieve a passing grade in this course, the student must achieve an average of at least 50% in both theoretical and laboratory components.
 
Teaching Methods1. Lectures will be delivered synchronously (i.e. for all students at the same time)during the scheduled class hours.
 2. Notes/slides from the class lectures will be posted on D2L.
 3. Audio/video recordings of the lecture delivery will not be posted on D2L due to department IP ownership policy. Individual students may record the lectures at their own discretion and the professor is not responsible for such recordings.
 4. Laptops/computer systems are mandatory requirement for the course lectures and labs.
 
Other InformationAll the labs have to be performed individually by each student. Each lab
 has its own weight as specified in the lab manuals. In case any two
 students have the same code, it will automatically be considered as
 plagiarized, therefore it is strongly advisable to write your own code and do the submission.
 Any late submission of the lab deliverable will be deducted 10% per day up to 8 days, whereby the lab will not be accepted.

Course Content

Week

Hours

Chapters /
Section

Topic, description

1

3

Ch. 1

Introduction: Course overview. Introduction to algorithms.
 Role of algorithms in solving various computational problems.


2

3

Ch. 2

Analyzing and designing algorithms
 Incremental approach divide-and-conquer approach insertion sort algorithm merge sort algorithm introduction to recursion comparison of the two sorting algorithms.


3

3

Ch. 3 Appendix A (A.1)

Complexity analysis
 Growth rate of functions asymptotic notations.


4

3

Ch.4: 4.3, 4.4, 4.5

Recurrence equations
 The substitution method the recursion tree.


5

3

Ch. 6, Ch. 10: 10.1, 10.2, 10.3 Appendix B: B.5

Elementary Data Structures
 Stacks Queues Priority Queues linked lists max heaps min heaps basic operations on these data structures maintaining the Maxheap property building a max
 heap heapsort algorithm.


6

3

Ch. 11: 11.1, 11.2, 11.3 (11.3.1, 11.3.2) 11.4

Hash Tables
 Direct address table Hash table basic operations on these data structures and the complexity analysis of those operations hash functions collision resolution using chaining.


7-9

9

Ch. 12: 12.1, 12.2, 12.3 Ch. 13

Trees
 Binary Search Trees insertion deletion Red Black Trees rotation insertion deletion Balanced Search Trees


10

3

Ch. 22: 22.1, 22.2, 22.3 Appendix B (B.4)

Graphs
 Undirected graph directed graph weighted graphs representations of graphs adjacency-list representation adjacency-matrix representation breadth-first search (BFS) depth-first search (DFS)


11-12

6

Ch. 23, Ch. 24: 24.1, 24.3 Ch. 25: 25.1

Elementary Graph Algorithms
 Minimum spanning trees Kruskal’s algorithm shortest paths Dijkstra's algorithm Bellman-Ford algorithm.


13

3

Ch. 34 (pp 1048-1053)

Introduction to NP-Completeness
 Course Review


Laboratory(L)/Tutorials(T)/Activity(A) Schedule

Week

L/T/A

Description

2

Lab 1

Introduction
 Reviews C programming
 ( 2 hours )

3

Lab 2

Recursion
 Understanding of recursion using Tower of Hanoi problem.
 ( 2 hours )

4-5

Lab 3

Sorting
 Implement and analyze insertion sort and merge sort algorithms.
 ( 4 hours )

6-7

Lab 4

State machines
 Implement the flow of control from state to state.
 ( 4 hours )

8-9

Lab 5

XML Balancing stacks direct-mapped tables and hash table
 Develop an algorithm to determine whether the start and end-tags balance by using a Stack data structure that keeps track of previously read start-tags.
 ( 4 hours )

10-11

Lab 6

Heaps
 Design a heap data structure and print it as an XML expression.
 ( 4 hours )

Policies & Important Information:

Students must be reminded that they are required to adhere to all relevant university policies found in their online course shell in D2L and/or on the following URL: http://ryerson.ca/senate/course-outline-policies

  1. Students are required to obtain and maintain a Ryerson e-mail account for timely communications between the instructor and the students;
  2. Any changes in the course outline, test dates, marking or evaluation will be discussed in class prior to being implemented;
  3. Assignments, projects, reports and other deadline-bound course assessment components handed in past the due date will receive a mark of ZERO, unless otherwise stated. Marking information will be made available at the time when such course assessment components are announced.
  4. Ryerson senate policy 157 requires that any electronic communication by students to Ryerson faculty or staff be sent from their official Ryerson email account.
  5. Familiarize yourself with the tools you will need to use for remote learning. The Continuity of Learning Guide for students includes guides to completing quizzes or exams in D2L or Respondus, using D2L Brightspace, joining online meetings or lectures, and collaborating with the Google Suite.
  6. The University has issued a minimum technology requirement for remote learning. Details can be found at: https://www.ryerson.ca/covid-19/students/minimum-technology-requirements-remote-learning. Please ensure you meet the minimum technology requirements as specified in the above link.
  7. Ryerson COVID-19 Information and Updates (available https://www.ryerson.ca/covid-19/students) for Students summarizes the variety of resources available to students during the pandemic.
  8. Refer to our Departmental FAQ page for information on common questions and issues at the following link: https://www.ee.ryerson.ca/guides/Student.Academic.FAQ.html.

Missed Classes and/or Evaluations

When possible, students are required to inform their instructors of any situation which arises during the semester which may have an adverse effect upon their academic performance, and must request any consideration and accommodation according to the relevant policies as far in advance as possible. Failure to do so may jeopardize any academic appeals.

  1. Academic Consideration Requests for missed work (e.g. missing tests, labs, etc) - According to Ryerson Senate Policy 134, sections 1.2.3, if you miss any exams, quizzes, tests, labs, and/or assignments for helth or compassionate reasons you need to inform your instructor(s) (via email whenever possible) in advance when you will be missing an exam, test or assignment deadline. When circumstances do not permit this, you must inform the instructor(s) as soon as reasonably possible "In the case of illness, a Ryerson Student Health Certificate, or a letter on letterhead from an appropriate regulated health professional with the student declaration portion of the Student Health Certificate attached. For reasons other than illness, proper documentation is also required (e.g. death certificate, police report, TTC report). ALL supporting documentation for illness or compassionate grounds MUST be submitted within three (3) working days of the missed work." NOTE: You are required to submit all of your pertinent documentation through Ryerson's online Academic Consideration Request system at the following link: prod.apps.ccs.ryerson.ca/senateapps/acadconsform.
  2. Religious, Aboriginal and Spiritual observance - If a student needs accommodation because of religious, Aboriginal or spiritual observance, they must submit a Request for Accommodation of Student Religious, Aboriginal and Spiritual Observance AND an Academic Consideration Request form within the first 2 weeks of the class or, for a final examination, within 2 weeks of the posting of the examination schedule. If the requested absence occurs within the first 2 weeks of classes, or the dates are not known well in advance as they are linked to other conditions, these forms should be submitted with as much lead time as possible in advance of the absence. Both documents are available at www.ryerson.ca/senate/forms/relobservforminstr.pdf. If you are a full-time or part-time degree student, then you submit the forms to your own program department or school;
  3. Academic Accommodation Support - Before the first graded work is due, students registered with the Academic Accommodation Support office (AAS - www.ryerson.ca/studentlearningsupport/academic-accommodation-support) should provide their instructors with an Academic Accommodation letter that describes their academic accommodation plan.

Virtual Proctoring Information (if used in this course)

Online exam(s) within this course may use a virtual proctoring system. Please note that your completion of any such virtually proctored exam may be recorded via the virtual platform and subsequently reviewed by your instructor. The virtual proctoring system provides recording of flags where possible indications of suspicious behaviour are identified only. Recordings will be held for a limited period of time in order to ensure academic integrity is maintained and then will be deleted.

Access to a computer that can support remote recording is your responsibility as a student. The computer should have the latest operating system, at a minimum Windows (10, 8, 7) or Mac (OS X 10.10 or higher) and web browser Google Chrome or Mozilla Firefox. You will need to ensure that you can complete the exam using a reliable computer with a webcam and microphone available, as well as a typical high-speed internet connection. Please note that you will be required to show your Ryerson OneCard prior to beginning to write the exam. In cases where you do not have a Ryerson OneCard, government issued ID is permitted.

Information will be provided prior to the exam date by your instructor who may provide an opportunity to test your set-up or provide additional information about online proctoring. Since videos of you and your environment will be recorded while writing the exam, please consider preparing the background (room / walls) so that personal details are not visible, or move to a room that you are comfortable showing on camera.

Turnitin (if used in this course)

Turnitin.com is a plagiarism prevention and detection service to which Ryerson subscribes. It is a tool to assist instructors in determining the similarity between students' work and the work of other students who have submitted papers to the site (at any university), internet sources, and a wide range of books, journals and other publications. While it does not contain all possible sources, it gives instructors some assurance that students' work is their own. No decisions are made by the service; it generates an "originality report," which instructors must evaluate to judge if something is plagiarized.

Students agree by taking this course that their written work will be subject to submission for textual similarity review to Turnitin.com. Instructors can opt to have student's papers included in the Turnitin.com database or not. Use of the Turnitin.com service is subject to the terms-of-use agreement posted on the Turnitin.com website. Students who do not want their work submitted to this plagiarism detection service must, by the end of the second week of class, consult with their instructor to make alternate arrangements.

Even when an instructor has not indicated that a plagiarism detection service will be used, or when a student has opted out of the plagiarism detection service, if the instructor has reason to suspect that an individual piece of work has been plagiarized, the instructor is permitted to submit that work in a non-identifying way to any plagiarism detection service.

Academic Integrity

Ryerson's Policy 60 (the Academic Integrity policy) applies to all students at the University. Forms of academic misconduct include plagiarism, cheating, supplying false information to the University, and other acts. The most common form of academic misconduct is plagiarism - a serious academic offence, with potentially severe penalties and other consequences. It is expected, therefore, that all examinations and work submitted for evaluation and course credit will be the product of each student's individual effort (or an authorized group of students). Submitting the same work for credit to more than one course, without instructor approval, can also be considered a form of plagiarism.

Suspicions of academic misconduct may be referred to the Academic Integrity Office (AIO). Students who are found to have committed academic misconduct will have a Disciplinary Notation (DN) placed on their academic record (not on their transcript) and will normally be assigned one or more of the following penalties:

  1. A grade reduction for the work, ranging up to an including a zero on the work (minimum penalty for graduate work is a zero on the work);
  2. A grade reduction in the course greater than a zero on the work. (Note that this penalty can only be applied to course components worth 10% or less, and any additional penalty cannot exceed 10% of the final course grade. Students must be given prior notice that such a penalty will be assigned (e.g. in the course outline or on the assignment handout);
  3. An F in the course;
  4. More serious penalties up to and including expulsion from the University.

The unauthorized use of intellectual property of others, including your professor, for distribution, sale, or profit is expressly prohibited, in accordance with Policy 60 (Sections 2.8 and 2.10). Intellectual property includes, but is not limited to:

  1. Slides
  2. Lecture notes
  3. Presentation materials used in and outside of class
  4. Lab manuals
  5. Course packs
  6. Exams

For more detailed information on these issues, please refer to the Academic Integrity policy(https://www.ryerson.ca/senate/policies/pol60.pdf) and to the Academic Integrity Office website (https://www.ryerson.ca/academicintegrity/).

Academic Accommodation Support

Ryerson University acknowledges that students have diverse learning styles and a variety of academic needs. If you have a diagnosed disability that impacts your academic experience, connect with Academic Accommodation Support (AAS). Visit the AAS website or contact aasadmin@ryerson.ca for more information.

Note: All communication with AAS is voluntary and confidential, and will not appear on your transcript.

Important Resources Available at Ryerson

  1. The Library (https://library.ryerson.ca/) provides research workshops and individual assistance. If the University is open, there is a Research Help desk on the second floor of the library, or go to https://library.ryerson.ca/workshops

  2. Student Learning Support (https://www.ryerson.ca/student-life-and-learning/learning-support/) offers group-based and individual help with writing, math, study skills and transition support, as well as resources and checklists to support students as online learners (https://www.ryerson.ca/student-life-and-learning/learning-support/).

  3. You can submit an Academic Consideration Request (https://prod.apps.ccs.ryerson.ca/senateapps/acadconsform) when an extenuating circumstance has occurred that has significantly impacted your ability to fulfill and academic requirement. You may always visit the Senate website (https://www.ryerson.ca/senate/) and select the blue radial button on the top right hand side entitled: Academic Consideration Request (ACR) to submit the request.

    Policy 167: Academic Concideration due to COVID-19: Students that miss an assessment due to cold or flu-like symptoms, or due to self isolation, are currently not required to provide a health certificate. Other absences must follow Policy 167: Academic Consideration.

    Also NOTE: Outside of COVID-19 symptoms, the new Policy 167: Academic Consideration does allow for a once per term academic consideration request without supporting documentation if the absence is less than 3 days in duration and is not for a final exam/final assessment. In the absence is more than 3 days in duration and/or is for a final exam/final assessment, documentation is required. For more information please see Senate Policy 167: Academic Consideration.

  4. Ryerson COVID-19 Information and Updates for Students (https://www.ryerson.ca/covid-19/students/) summarizes the variety of resources available to students during the pandemic.

  5. Familiarize yourself with the tools you will need to use for remote learning. The Continuity of Learning Guide (https://www.ryerson.ca/centre-for-excellence-in-learning-and-teaching/learning-guide/) for students includes guides to completing quizzes or exams in D2L Brightspace, with or without Respondus LockDown Browser and Monitor, using D2L Brightspace, joining online meetings or lectures, and collaborating with the Google Suite.

  6. Information on Copyright for Faculty (https://library.ryerson.ca/copyright/faculty/copyright-faqs/my-teaching-materials-have-been-posted-online/ and students (https://library.ryerson.ca/copyright/home/copyright-for-students-2/students-course-sharing-websites-and-file-sharing/).

  7. At Ryerson, we recognize that things can come up throughout the term that may interfere with a student's ability to succeed in their coursework. These circumstances are outside of one's control and can have a serious impact on physical and mental well-being. Seeking help can be a challenge, especially in those times of crisis. Below are resources we encourage all Ryerson community members to access to ensure support is reachable. https://www.ryerson.ca/mental-health-wellbeing.

    If support is needed immediately, you can access these outside resources at anytime: