Welcome to Week 6 of Analysis of Algorithms. The lectures for this
week complete our survey of important combinatorial classes and
applications in the analysis of algorithms.
----------
Lecture 8: Strings and Tries. From DNA sequences to web indices,
strings (sequences of characters) are ubiquitous in modern computing
applications, so we use analytic combinatorics to study their basic
properties and then introduce the trie, an essential and fundamental
structure not found in classical combinatorics.
Lecture 9: Words and Mappings. We view strings as sets of characters
or as functions from [1..N] to [1..M] to study classical occupancy
problems and their application to fundamental hashing
algorithms. Functions from [1..N] to [1..N] are mappings, which have
an interesting and intricate structure that we can study with analytic
combinatorics.
----------
Your assignment for this week, due at 11:59PM on
Thursday, March 16, 2017
is to write up and submit solutions to
Exercises 8.3, 8.14, 8.57, and 9.58
in "Analysis of Algorithms" (second edition).
Submit files named “A6-Q1.pdf” “A6-Q2.pdf” “A6-Q3.pdf” “A6-Q4.pdf" here:
http://dropbox.cs.princeton.edu/COS488_S2017/Assignment_6
RS