The individual chapters of the course notes are available from the protected files area. If you want further reading, a list of textbooks that cover the topics of the course well are listed below, and specific relevant areas are listed with each module.

Winter 2024 Lectures

The coverage of each lecture will be posted as the term progresses.

Lecture	Date	Course notes coverage
Lecture 1	January 9	Administrativia, Asymptotic analysis
Lecture 2	January 11	Runtime analysis : Insertion-sort : worst-case/ best-case (section 1.4) Merge-sort : analysis of recursive algorithm (section 1.4.1) Prioriry Queue : definition, basic implementation (section 2.1) Binary Heap : definition (section 2.2) storage (section 2.2.1) operation insert and deleteMax (section 2.2.2)
Lecture 3	January 16	Binary heap : construction : heapify (section 2.3.2) heap-sort (section 2.3.1) Meldable heaps (section 2.4.1) : Randomized algos & analysis (beginning of section 1.5.2) Binomial heaps (section 2.4.2) Sumset (note to be posted)
Lecture 4	January 18	Binomial heaps (section 2.4.2) Sumset (note is on LEARN) Quick-select (section 3.1)
Lecture 5	January 23	QuickSelect analysis (sections 3.1.3/3.1.4) QuickSort (section 3.2) Lower bound sorting by comparison (section 3.3) Integers sort (section 3.4)
Lecture 6	January 25	Integer sort (section 3.4): bucket-sort, MSD and LSD radix-sort Dictionaries: AVL tree (section 4.2), Scapegoat tree (section 4.3)
Lecture 7	January 30	Dictionaries: Scapegoat tree (section 4.3) / amortized analysis (1.5.4) BST with random insertion order Treaps (section 5.1.2)
Lecture 8	February 1	Dictionaries: Skip lists (section 5.1.3)
Lecture 9	February 6	Searching: biased search: static (section 5.2.1) and self-adjusting (section 5.2.2) among sorted numbers: lower bound (section 6.1.1), binary search (section 6.1.2), interpolation search (sections 6.1.3 and 6.1.4)

Winter 2024 readings

Module #	Topic	Readings
Module 0	Administrivia	None
Module 1	Introduction and Asymptotic Analysis	Course notes Chapter 1 Optional: Course notes Appendix A-B if you need a refresher. Optional: Goodrich & Tamassia   1.1, 1.2, 1.3 Optional: Sedgewick    8.2, 8.3
Module 2	Priority Queues	Course notes Chapter 2 Optional: Sedgewick   9.1 - 9.4
Module 3	Sorting, Average-Case and Randomized Algorithms	Course notes Chapter 1.5, 3 Optional: Goodrich & Tamassia   8.3 Optional: Sedgewick   6.10, 7.1, 7.2, 7.8, 10.3, 10.5
Module 4	Dictionaries	Course notes Chapter 4 Optional: Goodrich & Tamassia   3.1, 4.1, 4.2
Module 5	Other Dictionary Implementations	Course notes Chapter 5 Optional: Sedgewick    9.1-9.4
Module 6	Dictionaries for Special Keys	Course notes Chapter 6 Optional: Goodrich & Tamassia   23.5.1-23.5.2 Optional: Sedgewick    12.4, 15.2-15.4
Module 7	Dictionaries via Hashing	Course notes Chapter 7 Optional: Goodrich & Tamassia   6.4 Optional: Sedgewick    12.2, 14.1 - 14.4
Module 8	Range-Searching in Dictionaries of Points	Course notes Chapter 8 Optional: Goodrich & Tamassia   21.1, 21.3
Module 9	String Matching	Course notes Chapter 9 Optional: Goodrich & Tamassia   23
Module 10	Compression	Course notes Chapter 10 Optional: Goodrich & Tamassia   10.3
Module 11	External Memory	Course notes Chapter 11 Optional: Goodrich & Tamassia   20.1-20.3 Optional: Sedgewick    16.4

Textbooks

Course notes:

• CS240: Data Structures and Data Management by Therese Biedl with the help of many fellow CS 240 instructors is available from the protected files area.

  Module X corresponds roughly to Chapter X of the course notes, but occasionally a different order made more sense for the notes---follow the instructions given in the notes. Usually you can skip any part of the course notes that is marked `(cs240e)' or that is in `Historical remarks' or `Appendix' (but see what your instructor actually covers in class).

• For some of its figures, the latex source is available. This may be freely used when writing assignments.

The following books are on reserve in the DC library for reference and additional resources:

• [Goodrich & Tamassia] Algorithm Design and Applications (2015)
  by Michael T. Goodrich, Roberto Tamassia (mountain scene)
  
• [Sedgewick] Algorithms in C++, Third Edition (1998)
  by Robert Sedgewick, Addison-Wesley
  
• [BKOS] Computational Geometry: Algorithms and Applications
  by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars.
  Reference for multi-dimensional data structures.
• [CLRS] Introduction to Algorithms, 2nd edition (2001)
  by T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, McGraw-Hill
  Introduction to Algorithms, 2nd edition is also avaliable online (in campus).