The "Notes" section has links to course notes where they are available. A "slides" link will take you to Microsoft PowerPoint slides; a "PDF" link will point you to the same material, but in PDF format: each page will print with a slide in the upper-half leaving the bottom-half blank.
Remember that to make the most of this class, you should always read the recommended material for that day prior to coming to class.
| Date | Topic | Reading | Notes |
|
01/18 01/19 01/20 |
Administrative Issues and Introduction. Recitation 1: Summations, functions, and proof techniques Basic Assumptions and Approach; Insertion Sort |
Ch. 1 App. A, Ch. 3.2 Ch. 2.1-2.2 |
[PDF],
[PPT]
|
|
01/23 01/25 01/26 01/27 |
Analysis of Iterative Code (Insertion Sort) Merge Sort, Divide and Conquer, and Recurrences Recitation 2: Running times for iterative code Asymptotic Bounds |
Ch. 2.1-2.2 Ch. 2.3 Ch. 3.1 |
|
|
01/30 02/01 02/02 02/03 |
Little-o Notation Solving Recurrences Recitation 3: Practice Solving Recurrences Sorting Properties; Elementary Sorting Methods |
Ch. 3.1 Ch. 4.1, 4.3-4.4 |
|
|
02/06 02/08 02/09 02/10 |
Elementary Sorting Methods Priority Queues and Heaps Recitation 4: Stoogesort Building Heaps |
Ch. 6.1-6.2, 6.5 Ch. 6.3 |
|
|
02/13 02/15 02/16 02/17 |
Heapsort; Heapsort vs. Mergesort Quicksort Recitation 5: Review for Exam 1 Quicksort; Median-of-3 Partitioning |
Ch. 6.4 Ch. 7.1-7.2 Ch. 7.3-7.4 |
|
|
02/20 02/22 02/23 02/24 |
**** Exam 1 **** Sorting in Linear Time: Counting Sort Recitation 6: Circular Data Structures Sorting in Linear Time: Radix Sort |
Ch. 8.1-8.2 Ch. 8.3-8.4 |
|
|
02/27 03/01 03/02 03/03 |
Dictionaries Hashing: Hash Functions Recitation 7: Exam 1 post-mortem. Hash Functions cont'd. |
Ch. 11.1-11.2 Ch. 11.3 Ch. 11.3 |
PDF, PPT |
|
03/06 03/08 03/09 03/10 |
Hashing: Open Addressing Dictionaries: Binary Search Trees (BSTs) Recitation 8: Hash Functions and Linear Probing Rotations and Randomized BSTs |
Ch. 11.4 Ch. 12.1-12.3 Ch. 13.2 |
PDF, PPT |
|
03/13 03/15 03/16 03/17 |
Spring Recess
Spring Recess Spring Recess Spring Recess |
|
|
|
03/20 03/22 03/23 03/24 |
Red-Black BSTs Red-Black BSTs Recitation 9: HW03; Rotations/Root Insertion Red-Black BSTs: Finish Insertion |
Ch. 13.1-13.3 Ch. 13.1-13.3 Ch. 13.3 |
|
|
03/27 03/29 03/30 03/31 |
Recursion and Dynamic Programming Dynamic Programming Recitation 10: Review for Exam 2. Dynamic Programming |
Ch. 15 Ch. 15 Ch. 15 |
PDF, PPT PDF, PPT PDF, PPT |
|
04/03 04/05 04/06 04/07 |
****
Exam 2 **** Graphs: Background and Representation Recitation 11: Knapsack Problem Graphs: Breadth-First Search and Depth-First Search |
Ch. 22.1 Ch. 22.2-22.3 |
|
|
04/10 04/12 04/13 04/14 |
Graphs: Minimum Spanning Tree Background Graphs: Prim's MST Algorithm Recitation 12: Exam 2 post-mortem. Graphs: Dijkstra's Single-Source Shortest Paths Algorithm |
Ch. 23 Ch. 23 Ch. 24.3 |
|
|
04/17 04/19 04/20 04/21 |
Graphs: Kruskal's MST Algorithm Union-Find Algorithm for Equivalence Relations Recitation 13: TBD String Search: Rabin-Karp |
Ch. 23.2 Ch. 21 Ch. 32.1-32.2 |
|
|
04/24 04/26 04/27 04/28 |
String Search: Hash Function for Rabin-Karp String Search: Using Finite Automata Recitation 14: String Search: KMP vs. Finite Automata String Search: Knuth-Morris-Pratt |
Ch. 32.2 Ch. 32.3 Ch. 32.4 |
|
|
05/01 TBD |
Course Wrap-Up
(Last day of class) TBD |
Review Sheet |
|
Bucknell University - Department of Computer Science
This page is maintained by Steve Guattery