CSCI 311 - Algorithms and Data Structures

Fall 2019 - Lecture Schedule and Course Notes

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
08/26
08/28 
08/29 
08/31 		Administrative Issues and Introduction.
Basic Assumptions and Approach; Insertion Sort
Recitation 1: Summations, functions, and proof techniques
Analysis of Iterative Code (Insertion Sort)
 Ch. 1 
Ch. 2.1-2.2
App. A, Ch. 3.2
Ch. 2.1-2.2
[PDF], [PPT]



09/02  
09/04
09/05  
09/06		 Merge Sort, Divide and Conquer, and Recurrences
Asymptotic Bounds
Recitation 2: Running times for iterative code
Little-o Notation
 Ch. 2.3
Ch. 3.1

Ch. 3.1
09/09 
09/11
09/12  
09/13		 Solving Recurrences
Sorting Properties; Elementary Sorting Methods
Recitation 3: Practice Solving Recurrences
Elementary Sorting Methods
 Ch. 4.1, 4.3-4.4

 

09/16
09/18
09/19  
09/20		 Priority Queues and Heaps
Building Heaps
Recitation 4: Stoogesort
Heapsort; Heapsort vs. Mergesort
 Ch. 6.1-6.2, 6.5
Ch. 6.3
   
Ch. 6.4
09/23
09/25
09/26  
09/27		 Quicksort
Quicksort; Median-of-3 Partitioning
Recitation 5: Review for Exam 1
Sorting in Linear Time: Counting Sort
 Ch. 7.1-7.2
Ch. 7.3-7.4

Ch. 8.1-8.2
09/30  
10/02
10/03  
10/04		 Sorting in Linear Time: Radix Sort
**** Exam 1 ****
Recitation 6: Circular Data Structures
Dictionaries
 Ch. 8.3-8.4

 
Ch. 11.1-11.2 
10/07  
10/09
10/10  
10/11 		Hashing: Hash Functions
Hash Functions cont'd.
Recitation 7: Exam 1 post-mortem.
Hashing: Open Addressing
 Ch. 11.3
Ch. 11.3

Ch. 11.4
PDF, PPT
10/14  
10/16
10/17  
10/18 		Fall Break
Dictionaries: Binary Search Trees (BSTs)
Recitation 8: Hash Functions and Linear Probing
Rotations and Randomized BSTs
Ch. 12.1-12.3
 
Ch. 13.2


PDF, PPT
10/21
10/23  
10/24  
10/25		 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




10/28
10/30
10/31  
11/01		 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
11/04  
11/06  
11/07
11/08
 **** 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



11/11  
11/13
11/14  
11/15		 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

11/18  
11/20
11/21  
11/22		 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

11/25  
11/27
11/28  
11/29		 Thanksgiving Break
Thanksgiving Break
Thanksgiving Break
Thanksgiving Break
  

 

  
 
 
 
12/24  
12/26
12/27
12/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

12/09 
TBD
Course Wrap-Up  (Last day of class)
Final Exam
Review Sheet 
 
 
 
 

Bucknell University - Department of Computer Science

This page is maintained by Steve Guattery