ISTD 50.004 INTRODUCTION TO ALGORITHMS

Fall 2017


Course Description

This course deals with the design and analysis of efficient algorithms, looking at a variety of practical problems. Topics covered include: asymptotic notation,
divide-and-conquer, sorting, search trees, heaps, hashing, graph algorithms like graph searches and shortest paths, dynamic programming, introduction to complexity and NP-complete problems. It emphasises the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems. The lectures and the content of the course follows closely the MIT CS course 6.006 "Introduction to Algorithms".

Prerequisite

  1. 10.009 The Digital World

Learning Objectives

  1. Apply important algorithmic design paradigms and methods of analysis.
  2. Demonstrate a familiarity with major algorithms and data structures.
  3. Understand major issues in the implementation of algorithms.
  4. Appreciate the impact of algorithmic issues in the design of information systems.

Measurable Outcomes

  1. Describe an algorithmic paradigm
  2. Explain when an algorithmic design situation calls for one
  3. Recite algorithms that employ each paradigm
  4. Synthesise algorithms in the paradigm

Class Time

Two Sessions per week (S1, S2a or S2b).
  • S1 (Lecture): Tuesday 12:00pm-3:00pm. LT4 (2.404)
  • S2a (Recitation A) : Wednesday 11:00am-1:00pm (2.507, cohort classroom 14)
  • S2b (Recitation B) : Thursday 9:00am-10:50am (2.507, cohort classroom 14)
  • S2c (Recitation C): Thursday 1:00pm-3:00pm (2.507, cohort classroom 14)

Please bring your laptop to the class. The class is entirely cohort-based: mini-lectures, problem solving, activities, discussion, in-class quizzes. You are required to solve a set of weekly home exercises each week, and also do a number of problem sets, each requiring some theoretical analysis and some programming.