61126 Algorithms Analysis & Design

Course Description

The design and analysis of algorithms is the core subject matter of Computer Science. Given a problem, we want to (a) find an algorithm to solve the problem, (b) prove that the algorithm solves the problem correctly, (c) if possible, show that the problem can not be solved any faster, and (d) implement the algorithm. Designing an algorithm for a computational problem involves knowledge of the problem domain, a thorough knowledge of the data structures that are available and suitable and a good measure of creativity. This course concentrates on the above issues. The course will also cover useful algorithmic design techniques, and methods for analyzing algorithms.

This course provides introduction to the analysis, design and implementation of algorithms. Topics to be covered include mathematical foundations of algorithms such as sequences, series, asymptotic notations, recurrences, Homogeneous & Non-Homogeneous Recurrences, Graphs, Greedy algorithms, analysis of time and space of algorithms, formal methods for establishing the correctness of algorithms through the use of comparative techniques.

Learning Objective

  • 1. Explain the use of big O, Omega, and Theta notations to describe the amount of work done by an algorithm.
  • 2. Compare, evaluate and determine the time and space complexity needed for efficient algorithms.
  • 3. Deduce recurrence relations that describe the time complexity of recursively defined algorithms.
  • 4. Solve homogeneous and non-homogeneous recurrence relations.

Credits

    3

Books for this Course

  • Fundamentals of Algorithmics, Gilles Brassard and Paul Bratley, Prentice Hall, 2008

Times Offered

  • September 2014
  • January 2015

Course Prerequisite

TOP