433-253 Algorithms and Data Structures

433-151 Introduction to Programming (Advanced) or 433-171 Introduction to Programming, and 433-152 Algorithmic Problem Solving (Advanced) or 433-172 Algorithmic Problem Solving, and two subjects (25 points) of first-year mathematics.

Prior or concurrent enrolment in 433-252 Software Engineering Principles and Tools is strongly recommended.

The objective of this subject is for students to understand the fundamentals of algorithm design, including algorithm analysis, abstract data types, and techniques for algorithmic problem solving. Students will be able to apply this understanding to analyse new problems and develop programs that solve them, expressed in an imperative or functional programming language.

Topics covered include complexity classes and asymptotic notations; empirical analysis of algorithms; abstract data types including queues, trees, heaps and graphs; algorithmic techniques including brute force, divide-and-conquer, dynamic programming and greedy approaches; space and time trade-offs; and the theoretical limits of algorithm power.

• ability to apply knowledge of basic science and engineering fundamentals

• ability to communicate effectively, not only with engineers but also with the community at large

• in-depth technical competence in at least one engineering discipline

• ability to undertake problem identification, formulation and solution

• openness to new ideas and unconventional critiques of received wisdom

• profound respect for truth and intellectual integrity, and for the ethics of scholarship

Project work during semester, expected to take about 36 hours (30%); and a 3-hour end-of-semester written examination (70%). To pass the subject, students must obtain at least 50% overall, 15/30 in project work, and 35/70 in the written examination.