COMP6230

Introduction to Algorithmics

10 Units

This course introduces students to the notion of efficiency and computational complexity. The basic data structures encountered in first year, such as lists, trees and graphs, are reviewed in light of their efficiency and common usage scenario. Asymptotic measures of complexity are covered, and recurrence relations are introduced as an analytical tool. Problem-solving techniques such as the greedy strategy, divide-and-conquer, dynamic programming, and graph searching are covered. These techniques are illustrated upon optimization problems chosen for their practical relevance.

Faculty Faculty of Engineering and Built Environment
School School of Electrical Engineering and Computer Science
Availability Semester 2 - 2015 (Callaghan)
Learning Outcomes

On successful completion of this course, students will be able to:

  1. apply basic techniques to analyse the performance of algorithms;
  2. explain the most important algorithms used in various common computer science applications;
  3. apply efficient algorithm design techniques and understand the limitations of algorithms.
Content
  1. Preliminaries (review of basic mathematical notions, data structures, induction, basic combinatorics).
  2. Elementary algorithmics (worst-case vs. average case, basic examples, elementary operations).
  3. Asymptotic Notation (big O, Omega and Theta).
  4. Analysis of Algorithms (loops, recurrence relations).
  5. Data structures (graphs, trees, heaps, disjoint sets).
  6. Searching and Sorting.
  7. Greedy algorithms.
  8. Divide-and-Conquer.
  9. Dynamic programming.
  10. Text-search Algorithm.
  11. Introduction to the topics of computational complexity, heuristics, metaheuristics and approximation algorithms.
     
Multi-Term Sequence
Requisites
Assumed Knowledge SENG6120 Knowledge of discrete mathematics
Assessment Items
  • Written Assignment: Essays / Written Assignments
  • In Term Test: Examination: Class
  • Formal Examination: Examination: Formal *
  • Project: Assessment tailored towards MIT students needs
  • Project: Projects
Contact Hours
  • Lecture: for 3 hour(s) per Week for Full Term
  • Tutorial: for 2 hour(s) per Week for Full Term
Timetable 2015 Course Timetables for COMP6230

Sound like the course for you?

  Apply Now