RYERSON UNIVERSITY

Course Outline (W2019)

COE428: Engineering Algorithms and Data Structures

Instructor(s)Reza Sedaghat [Coordinator]
Office: ENG431
Phone: (416) 979-5000 x 6083
Email: rsedagha@ryerson.ca
Office Hours: TBA

Truman Yang
Office: ENG435
Phone: (416) 979-5000 x 4175
Email: cungang@ryerson.ca
Office Hours: TBA

Prathap Siddavaatam
Office: ENG328
Phone: TBA
Email: prathap.siddavaatam@ryerson.ca
Office Hours: Friday 5-8 PM

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, Text MIT, 2002, ISBN: 0-07-013151-1 (McGraw-Hill)

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)

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/tutorial per week for 12 weeks

Teaching AssistantsTBA
Course Evaluation
Labs 30 %
Mid-term Examination 25 %
Final Examination 45 %
TOTAL:100 %

Note: In order for a student to pass a course with "Theory and Laboratory" components, in addition to earning a minimum overall course mark of 50%, 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 for details on the Theory and Laboratory components.


ExaminationsMidterm exam in Week 7, two hours, problems, closed book (covers Weeks 1-6).
 Final exam, during exam period, two hours, closed-book (covers Weeks 8-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.
 All the Labs have to be done in group of 2 students. Two week labs carry double weight than one week labs.
Other InformationNone

Course Content

Week

Hours

Chapters /
Section

Topic, description

1

3

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


2

3

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

Complexity analysis
 Growth rate of functions asymptotic notations.


4

3

Recurrence equations
 The substitution method the recursion tree.


5

3

Elementary Data Structures
 Stacks 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

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

Trees and Priority Queues
 Binary search trees insertion deletion Red Black trees rotation insertion deletion Priority queues.


10

3

Graphs
 Undirected graph directed graph weighted graphs representations of graphs adjacency-list representation adjacency-matrix representation.


11-12

6

Elementary Graph Algorithms
 Breadth-first search depth-first search minimum spanning trees Kruskal’s algorithm shortest paths Dijkstra's algorithm Bellman-Ford algorithm.


13

3

Review


Laboratory/Tutorials/Activity Schedule

Week

Lab

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:

  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. 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. Health certificates - If a student misses the deadline for submitting an assignment, or the date of an exam or other evaluation component for health reasons, they should notify their instructor as soon as possible, and submit a Ryerson Student Health Certificate AND an Academic Consideration Request form within 3 working days of the missed date. Both documents are available at https://www.ryerson.ca/senate/forms/medical.pdf.. If you are a full-time or part-time degree student, then you submit your forms to your own program department or school;
  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.

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/).

Important Resources Available at Ryerson

  1. The Library (https://library.ryerson.ca/) provides research workshops and individual assistance. Inquire at the Reference Desk on the second floor of the library, or go to library.ryerson.ca/guides/workshops
  2. Student Learning Support(https://www.ryerson.ca/studentlearningsupport) offers group-based and individual help with writing, math, study skills and transition support, and other issues.