COE428 Course Outline
 
 


Introduction
 

 

Engineering Algorithms & Data Structures (COE 428) deals with the fundamental means to approach the design and analysis of algorithms in an effective and methodologically correct manner. The student will acquire knowledge about general techniques for the design and analysis of algorithms as well as a collection of significant examples of solutions to representative problems. Furthermore, the student will have the opportunity to supplement the theory by writing actual programs in the C language  during laboratory sessions.


Course Objectives

At the conclusion of this course the student will have learned the following:
  1. Structured methods for engineering software design
  2. Process of the problem-to-program and an introduction to "big O" and "big Omega" notation.
  3. Principal internal sorting algorithms: quicksort, heapsort, binsort, and the simpler, less efficient methods such as insertion sort. Linear-time algorithms are also covered.
  4. Traditional list, stack and queue structures. Also, mapping an abstract data type based on the mathematical notion of a function.
  5. Introduction to abstract data types based on the mathematical model of a set. Implementations of stacks and queues. Introduction to hash tables and binary search trees.
  6. Graphs, including directed and undirected graphs, for the implementation of graph algorithms. Introduction to data structures for graph representation. Presentation of a number of graph algorithms, including depth-first search, generating minimal spanning trees, shortest paths, etc.
  7. Asymptotic analysis of recursive procedures, including recurrence relations.
 
8. Introduction to designing algorithms, dynamic programming, local search algorithms, and various forms of tree searching.
 
9. Analysis of algorithm complexity.


Course Outline
The following table gives a brief overview of the course topics and assignments.

Note: Labs begin from second week.


Topic

Lab

1

Introduction. Course overview. Introduction to algorithms 

 

2

Analyzing and Designing algorithms, Recursion 
Lab

3

Complexity analysis
Lab

4

Recurrence equations, Data Structure
Lab

5

Stacks and queues
Lab

 

6

Heapsort, Hashing
Lab

    

Study week
Lab

7

 Trees and Priority Queues
 Mid term (tentative)
Lab

8

Binary Search Trees
Lab

9

Balanced BSTs (including Red-Black Trees)
Lab

10

Graphs
Lab

11

Elementary Graph Algorithm
Lab

 12

 Elementary Graph Algorithm
Lab

13

Review
Lab



Marking Scheme:

The following table summarizes the marking scheme for the course.  All the Labs have to be done individually.  Two week labs carry double weight than one week labs.


Labs:

25%

Midterm:

35%

Final exam:

40%


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.


Instructors:
     


  • Prof. R. Sedaghat (rsedagha@ee.ryerson.ca) ENG-431 (Coordinator)
  • Dr. Arghavan Asad  (arghavan.asad@torontomu.ca)




References:

Textbooks

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms, MIT, 2002, ISBN: 0-07-013151-1 (McGraw-Hill)



Other References
2. Knuth, Donald Ervin, The Art Of Computer Programming (3 volumes) Addison-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.

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

4. Standish, Thomas A., Data Structures, Algorithms and Software Principles in C, Addison-Wesley 1995, ISBN: 0-201-59118-9

5.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.


Reza  Sedaghat

2021-Jan-02