Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
EECS 3101 E: Design and Analysis of Algorithms

Lecture Schedule ( Fall 2019):

  • Lectures: 4:00 - 5:30 pm, Mondays and Wednesdays at LSB 103
  • Tutorials: 4:00 - 5:30 pm, Thursdays at LSB 103
  • Instructor: Andy Mirzaian

Course Description:

This course is intended to teach students the fundamental techniques in the design of algorithms and the analysis of their computational complexity. Each of these techniques is applied to a number of widely used and practical problems. At the end of this course a student will be able to: choose algorithms appropriate for many common computational problems; to exploit constraints and structure to design efficient algorithms; and to select appropriate tradeoffs for speed and space. Topics covered may include the following:

  • Review: Mathematical Induction, asymptotic notation.
  • Analysis techniques: summations and recurrence relations.
  • Lower Bound Techniques: (Algebraic) Decision Trees, Adversary Arguments, Problem Reduction (or Transformation).
  • Correctness proofs via assertions, pre and post conditions, loop invariants, (weak & strong) induction on these assertions.
  • Sorting and order statistics: Heapsort and Priority Queues, Randomised QuickSort and its expected case analysis, Special Purpose Sorting Algorithms, Linear-Time Selection.
  • Prune-&-Search: Binary Search, Linear Time Selection Algorithm.
  • Incremental methods: VLSI Cheap Testing, In-Place Tri-Partition, Maximum Sum Subarray, Longest Smooth Subarray.
  • Divide-and-conquer: MergeSort, Recursive Doubling, Euclid's (extended) GCD algorithm (and its applications in number theory and encryption techniques), arithmetic with large numbers and matrices, Closest Pair of Points in 2D.
  • Greedy methods: Coin Change Making, Activity Selection (or Event Scheduling), Point-Interval Cover Problems, some graph algorithms.
  • Dynamic Programming: Matrix Chain Product, Optimal Static Binary Search Trees, Scheduling, Knapsack Problems, Longest Common Subsequence, some graph algorithms.
  • Graph algorithms: Depth First Search, Breadth First Search, Biconnectivity and Strong Connectivity, Topological Sort, Minimum Spanning Trees, Shortest Paths, Network Flow, Matching.
  • Theory of NP-completeness.

Copyright Law Notice:

Course materials are subject to Canadian copyright law and are the intellectual property of the associated author(s). Lectures, lecture slides, lecture notes, assignments, tests, and their solutions posted on this course website are the intellectual property of Professor Andy Mirzaian. Course materials may not be distributed without explicit written permission from the professor or author. Course material posted online on this course website may not be sold, passed on to others, or posted online elsewhere.

Photographs and audio recordings of lectures are permitted, provided they are used only as a personal study aid. Lectures can only be recorded from your seat. Exceptions may be made for students who are registered with Counselling & Disability Services and have presented relevant documentation from their counsellor to the professor.

Last modified:
2019/06/12 12:12