Computing Science Course Outlines

Course Outline - CMPT 307 - Data Structures and Algorithms

Information

Subject

Catalog Number

Section

Semester

Title

Instructor(s)

Campus

CMPT

307

E100

2010 Summer (1104)

Data Structures and Algorithms

Pavol Hell   

Vancouver Campus

Calendar Objective/Description

Analysis and design of data structures for lists, sets, trees, dictionaries, and priority queues. A selection of topics chosen from sorting, memory management, graphs and graph algorithms.

Instructor's Objectives

The objective of this course is to introduce concepts and problem-solving techniques that are used in the design and analysis of efficient algorithms. This is done by studying various algorithms, algorithmic techniques, and data structures.

Prerequisites

CMPT 225, MACM 201, MATH 151 (or MATH 150), and MATH 232 or 240.

Topics

  • Introduction and Mathematical Preliminaries: Asymptotic notation, Models of computation, Basic probability theory.
  • Sorting and Order Statistics: Heapsort, Quicksort, Non-comparison sorts, Lower bounds, Median-finding, Selection.
  • Simple Data Structures: Lists, Stacks, Queues, Mappings, Trees.
  • Dictionaries: Binary search trees, Height-balanced trees, B-trees, Splay trees.
  • Priority Queues: Heaps, Binomial Heaps, Fibonacci Heaps.
  • Randomized algorithms, Average case analysis, Amortized analysis.
  • Dynamic programming, Greedy algorithms, Graph algorithms.
  • Other topics depending on available time.

Grading

The course has a final examination, homework assignments, and quizzes. Grade distribution will be announced during the first week of classes.

Required Books

  • Introduction to Algorithms - Second Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, C, Stein, McGraw Hill, 2001, 9780072970548

Academic Honesty Statement

Academic honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty will be handled in accordance with the SFU Academic Honesty and Student Conduct Policies ( http://www.sfu.ca/policies/Students/index.html ). Students are also encouraged to read the School's policy information page ( http://www.cs.sfu.ca/undergrad/Policies/ ).

Data Last Updated: