CSCI 422: Advanced Algorithms and Data Structures
Fall 2019

Course Announcements

Anything new and of sufficient consequence (such as cancellations, updates to assignments, etc.) will be emailed to the class. Such emails will arrive at the email address that is indicated at your Student Record. Announcements with lasting significance will also be posted here.
If I change an announcement, I will put the change in bold

Date Announcement
Sept 6,7,8: There will NOT be a tutorial today. We start the tutorials next week.

You are invited (but are not required) to read Chapter 0 of Jeff Erickson's text. It gives some history of the study of algorithms. In particular I was interested in the history of alternative algorithms for multiplication.

Required reading (and covering in class): Erickson 1.4 - 1.9 The earlier part of the chapter (1.0-1.3) should be review for you from 260, and you can read it if you like. Chapter 1.4 will also be a review - we will "warm up" with an analysis of mergesort and then use that as a model for selection and median algorithms.

Note that the textbook's complexity analysis of divide-and-conquer algorithms acts as if we don't have the Master Theorem at our disposal; this is good, as we will see a Master Theorem proof sketch emerge - i.e., we will see why the Master Theorem works.
Sept 14, 15,16 Tutorial: Recursion trees for running time analysis; ADT Array in constant time per operation implementation.
Lecture: Sept 14: Sections 1.5 - 1.8. Sept 16 Sections 1.9, 2. (skip 1.10). Skimmed 2.1 and 2.2, covered 2.3 Subset Sum, and 2.4 General Backtracking, and covered 2.6 Longest Increasing Subsequence.
Sept 21, 22, 23 Tutorial:

Useful Links:

Course Outline
Jeff Erickson's Algorithms (page with multiple links)
Gara Pruesse's Homepage
Computer Science Homepage
Vancouver Island University Homepage