## CPSC 327: *Data Structures and Algorithms*

Department of Mathematics and Computer Science Hobart and William Smith Colleges Spring, 2019. Instructor: David J. Eck Textbook: Introduction to Algorithms, 3rd Edition, by Thomas Cormen et. al. Monday, Wednesday, Friday, 12:20–1:15 PM. Room Gulick 2000 Course Handout: http://math.hws.edu/eck/courses/cpsc327_s19.html

Homework | |||

Homework 1 Due January 30 (Answers) |
Homework 2 Due February 6 (Answers) |
Homework 3 Due February 15 (Answers) |
Homework 4 Due February 22 |

### Fifth Week: February 18, 20, and 22

We continue talking about hash tables (Chapter 11). We will then do some work with trees, especially binary sort trees (Chapter 12). Then, instead of covering balanced binary sort trees in general, we will look at another approach to balanced trees: B-Trees (Chapter 18).

### Fourth Week: February 11, 13, and 15

At the end of last week, we proved that a comparison sort requires Θ(n*log(n)) comparisons, in the worst case (Section 8.1). This week, we see that nevertheless there are sorting algorithms with worst-case running time Θ(n). We will cover counting sort (Section 8.2) and radix sort (Section 8.3). After that, we look at order statistics, such as the maximum and the median (Sections 9.1 and 9.2). We will then move on to hash tables (Chapter 11).

### Third Week: February 4, 6, and 8

We will continue to work on sorting. After completing Heapsort and Priority Queues, we will move on to Quicksort (Chapter 7 in the textbook).

### Second Week: January 28 and 30; February 1

We will finish the general, introductory material this week and move on to specific algorithms and data structures. We will spend most of the week on analysis of algorithms, including Big-Oh notation, recurrence relations, and the Master Theorem for solving recurrence relations. As an example, we will cover Karatsuba's algorithm for multiplying n-digit numbers. By Friday, hopefully, we will be able to move on to heaps and HeapSort (Chapter 6 in the textbook.)

### First Week: January 23 and 25

Welcome to the course!

The textbook for the course is: Introduction to Algorithms, 3rd Edition, by Thomas Cormen et. al., ISBN 9780262033848. There is a web site for the textbook, including answers to some of the exercises and OpenCourseware video lectures from an MIT online course, at

https://mitpress.mit.edu/books/introduction-algorithms-third-edition

In the first week of the course, we will discuss the difference between **problems** and
**algorithms**, and we will look at the design and analysis of algorithms in general terms.
The main reading for the week is Chapter 2, *Getting Started*, and Section 3.1, *Asymptotic Notation*.
We will need to review a few topics that you might or might not already be familiar with, including
summation notation and loop invariants.