CSC265H Standard Course Description

CSC265H Standard Course Description

Enriched Algorithm Design Techniques

Owner

Faith Fich

fich@cs.toronto.edu

Course Description

Standard graph-theoretic algorithms (traversals, minimum spanning trees, shortest paths, backtracking). Standard algorithm design techniques: divide-and-conquer, greedy strategies, dynamic programming, linear programming. Recurrence equations and their solutions. Emphasis is placed on conceptual understanding of techniques, proofs of correctness, and problem-solving. This course goes at a faster pace than CSC263H and will have more challenging assignments.

Background

This course evolved from the first part of the "old" CSC364H and two parts of CSC270H ("graph theory" and "dynamic programming"), expanded to contain more design techniques. Students will be expected to design new algorithms based on these techniques and write careful proofs of correctness. They will also be expected to do careful worst case analyses of iterative and recursive algorithms.

Prerequisistes

CSC207H/270H
- good programming skills
CSC240H/(236H/238H with permission of the instructor)/(148H with permission of the instructor and strong mathematical background, such as with a specialist in Mathematics)
- "enriched" skills for reasoning about the correctness and complexity of algorithms. CSC148H is accepted so that mathematics specialists may take the course.
CGPA 3.00
- enriched course

Exclusions

CSC263H
- "regular" version of this course
CSC364H
- covers much of the same material

Follow-On Courses

CSC324H
- recurrence relations
CSC340H
- recurrence relations and standard algorithms
CSC343H
- graph theory, standard algorithms
CSC363H/365H
- familiarity with standard algorithms, recurrence relations
CSC377H/379H
- familiarity with standard algorithms, recurrence relations
CSC411H
- recurrence relations and standard algorithms
CSC418H
- recurrence relations and standard algorithms
CSC458H
- recurrence relations and standard algorithms
CSC488H
- recurrence relations and standard algorithms

Learning Objectives

Understand standard graph-theoretic algorithms (traversals, minimum spanning trees, shortest paths), why they are correct and their complexities,
- learn various data structures for representing graphs
Understand standard algorithm design techniques (divide-and-conquer, greedy strategies, dynamic programming, linear programming)
- know the definitions of the various techniques and why they are correct
- be able to recognize algorithms that employ these techniques
- be able to write algorithms using these techniques
- prove algorithms written using these techniques to be correct
- be able to choose among these techniques to solve problems
Understand how to analyze the efficiency of algorithms
- be able to analyze the efficiency of algorithms written using the techniques mentionned above
- understand the difference between upper and lower bounds
- be able to setup recurrence relations
- be able to solve general recurrence relations, using various common techniques

Topics (not necessarily in this order)

Graphs and basic graph algorithms (4 hr.)
- review of graphs and data structures for graphs
  - basic definitions
  - adjacency matrices and adjacency lists
- traversal algorithms (BFS, DFS)
- backtracking algorithms
Divide-and-Conquer Algorithms (4 hr.)
- definitions and examples (including matrix multiplication)
- expressing correctness
- more examples
Complexity Analysis of Recursive Algorithms (4 hr.)
- Review of basic analysis techniques for nonrecursive algorithms (1 hr.)
  - upper and lower bounds on running times
- Recurrences (3 hr.)
  - setting up recurrence relations for the running time of recursive algorithms
  - solving general recurrence equations
Greedy Algorithms (4 hr.)
- definitions and examples (including minimum spanning trees)
- expressing correctness (stating loop invariants)
- more examples
Dynamic Programming (6 hr.)
- definitions and examples (including shortest paths)
- expressing correctness (justifying recurrences)
- more examples
Linear Programming (4 hr.)
- setting up problems as linear programs
- network flow algorithms as a special case

Suggested Texts

REQUIRED

Introduction to Algorithms (2nd edition)
Cormen, Leiserson, Rivest, and Stein, McGraw-Hill, 2001
ISBN 0-07-013151-1

Sample Evaluation

type	weight	description
assignments	40%	5 assignments (pencil-and-paper)
midterm tests	15-20%	1-2 tests
final exam	40-45%