TORONTO METROPOLITAN UNIVERSITY

Course Outline (W2024)

COE428: Engineering Algorithms and Data Structures

Instructor(s)Dr. Reza Samavi [Coordinator]
Office: ENG457
Phone: (416) 979-5000 x 554903
Email: samavi@torontomu.ca
Office Hours: Mon 14:00-16:00 / please email to make an appointment

Dr. Reza Sedaghat
Office: ENG431
Phone: (416) 979-5000 x 556083
Email: rsedagha@torontomu.ca
Office Hours: TBA

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, Clifford Stein. Introduction to Algorithms, Fourth Edition, MIT Press, 2022, ISBN: 978-0-262-04630-5
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 AssistantsTBA
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 during the scheduled class hours.
 2. Notes/slides from the class lectures will be posted on D2L.
 3. 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. 20: 20.1, 20.2, 20.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. 21, Ch. 21 and 22 and 23.1

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


13

3

Ch. 24 and 34 (pp 1042-1048)

Flow Networks, 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

Lab1-2 review

Lab 1 and 2 review

5-6

Lab 3

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

7-8

Lab 4

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

9-10

Lab 5

Use of Stacks and XML-based HEAP
 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. Design a heap data structure and print it as an XML expression.
 ( 4 hours )

11

Lab5 review

Lab 5 review

University Policies & Important Information

Students are reminded that they are required to adhere to all relevant university policies found in their online course shell in D2L and/or on the Senate website

Refer to the Departmental FAQ page for furhter information on common questions.

Important Resources Available at Toronto Metropolitan University

Accessibility

Academic Accommodation Support

Academic Accommodation Support (AAS) is the university's disability services office. AAS works directly with incoming and returning students looking for help with their academic accommodations. AAS works with any student who requires academic accommodation regardless of program or course load.

Academic Accommodations (for students with disabilities) and Academic Consideration (for students faced with extenuating circumstances that can include short-term health issues) are governed by two different university policies. Learn more about Academic Accommodations versus Academic Consideration and how to access each.

Wellbeing Support

At Toronto Metropolitan University, 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.

If you are experiencing a mental health crisis, please call 911 and go to the nearest hospital emergency room. You can also access these outside resources at anytime:

If non-crisis support is needed, you can access these campus resources:

We encourage all Toronto Metropolitan University community members to access available resources to ensure support is reachable. You can find more resources available through the Toronto Metropolitan University Mental Health and Wellbeing website.