CS5006: Algorithms Course Charter

Introduction

This course is intended to provide Align students with a common base of knowledge in Algorithms. Faculty use the C programming language to introduce algorithmic concepts.

CS5006 is part of the second semester of the Align bridge. Before taking this course, students should have completed CS5001 and CS5002.

CS5006 and 5007 are each half-semester courses that can, in theory, be taught in either order. Because C is taught in one and used in both, the courses should ideally be taught by the same instructor, and students taking one should register for both.

The current preferred order is CS5007 followed by 5006.

Example Course Page (PDF)

Goals

The goals of this class are to:

  • Build a solid understanding of how to analyze algorithms.
  • Build a solid understanding of how to compare algorithms.
  • Provide students with additional practice in C.

High-Level Learning Objectives

At the end of CS5006, a student should be able to:

  1. Analyze the computation and storage complexity of a given algorithm
    1. utilize the following approaches for analyzing algorithms:
      1. substitution method
      2. The Master method
      3. Recursion trees
    2. have a firm grasp of the mathematics used when discussing algorithms, including
      1. logarithms
      2. exponents
      3. algebra
  2. Prove the correctness of an algorithm via loop invariants
  3. Explain the designs of, and tradeoffs between, common sorting algorithms
  4. Write small C programs

Implementation Details

The course evaluates students through

  1. Weekly programming assignments.
  2. Final exam. Because this is a half-semester course, there is typically just one exam.

An example of a per-week course schedule is as follows:

  • Week 1: Math review, pseudo-code, big-O notation, searches and sorts
  • Week 2: Sorting and analysis, divide and conquer, trees
  • Week 3: Graph algorithms
  • Week 4: More algorithmic strategies, greedy algorithms, randomized algorithms
  • Week 5: Dynamic programming
  • Week 6: Tries and string matching
  • Week 7: Review and final exam

CS5006 introduces several data structures in the context of presenting specific algorithms and general algorithmic techniques. They appear in other courses as well; various presentations reinforce/complement each other.

 Abstract data types: Usage and Implementation

  • Stacks [Use, Implement] Also in 5001, 04, 07
  • Queues [Use, Implement] Also in 5001, 04, 07
  • Heaps [Discuss]
  • Trees [Implement BST] Some in 5002, 04
  • Graphs [Implement] Some in 5002
  • Maps [Implement] Some in 5001, 04, 07

Data Structures: Use and Implementation

  • Arrays [Use] Also in 5004, 07