CPSC 327: Data Structures and Algorithms, Spring 2019

This course ended
May 13, 2019

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 (Answers)
Homework 5 Due March 1 (Answers)	Homework 6 Due March 29 (Sample Solutions)	Homework 7 Due April 19

Fifteenth Week and the End of Semester: May 6 and 13

Monday, May 6 is the last day of classes. There will be some student presentations of their final projects.

Final projects are due by the final exam period, Monday, May 13, at 7:00 PM. (Seniors are asked to turn in their projects by Sunday, May 12, since senior grades are due earlier than other grades.)

There will be some student presentations during the final exam period, but attendance is not required.

End-of-semester Office Hours:

    Monday, May 6:      1:30–4:00
    Tuesday, May 7:    10:00–2:00
    Wednesday, May 8:   1:00–4:00
    Thursday, May 9:    1:00–4:00
    Saturday, May 11:  11:00–2:00
    Sunday, May 12:    12:00–1:20

Fourteenth Week: April 29; May 1 and 3

There is a test on Monday, April 29. A study guide was handed out in class.

For the rest of the week, we should have some student presentations of final projects. I will fill any time that is not used for presentations with discussion of topics that didn't make it into the course. (We might start with the proof that, if P ≠ NP, then there is no approximation algorithm for the general traveling salesman problem. Unfortunately, the proof is based on the fact that HAMILTONIAN_CIRCUIT is NP-complete and you will have to take that on faith, since we didn't prove it.

Since there is no final exam and no further homework assignments, whatever we do for the rest of the week will not be tested. Hopefully, however, there will be some interesting things for you to learn about.

Thirteenth Week: April 22, 24, and 26

We finished our look at NP-completeness and looked briefly at approximation algorithms, Chapter 35. We covered the approximation algorithm for the Euclidean traveling salesman problem. On Friday, we review for the test.

Twelfth Week: April 15, 17, and 19

This week, we will be working on NP-Completeness, Chapter 34. We will define the classes P and NP, look at reduction of one problem to another, and define NP-completeness.

Eleventh Week: April 8, 10, and 12

We will continue with Dynamic Programming, Chapter 15. We will be covering the longest common subsequence problem and the edit distance problem, and maybe some of the problems from the exercises.

After that, we will look at some of the material from Chapter 16 on the theory of greedy algorithms. We will at least look at the activity selection problem that is used as an example in that chapter.

Tenth Week: April 1, 3, and 5

A take-home test was distributed in class last Friday, and is due at the start of class this Friday, April 5.

The topic for the week is Dynamic Programming, which is covered in Chapter 15 in the textbook.

Ninth Week: March 25, 27, and 29

We will finish up our look at basic graph algorithms on Monday by considering Dijkstra's algorithm in more detail and then covering Floyd's all-pairs shortest path algorithm. (We will continue to use graphs in examples and assignments.)

For the rest of the week, will be looking at "heuristic search." I will discuss hill climbing very briefly and then simulated annealing and the genetic algorithm in more detail.

Homework 6, the programming assignment about graphs, is due on Friday, March 29. The take-home midterm exam will be handed out on the same day and will be due Wednesday Friday of next week, April 5.

Eighth Week: March 11, 13, and 15

We covered Kruskal's and Prim's minimal spanning tree algorithms. In order to implement Kruskal's algorithm efficiently, we also covered the UNION-FIND data structure, and we discussed how to use a heap to make Prim's algorithm efficient. We looked at a proof of the correctness of Kruskal's algorithm using a loop invariant. And at the end of the week we looked briefly at Dijkstra's shortest path algorithm.

Seventh Week: March 4, 6, and 8

There is a test on Monday , March 4. A study guide was handed out in class last Wednesday.

After the test, we will continue our study of graphs. We will look at topological sort (Section 22.4) and then move on to minimum spanning tree algorithms, Chapter 23.

Sixth Week: February 25 and 27; March 1

This week, we begin one of the major topics of the course: Graphs and graph algorithm. We will look at the adjacency list and adjacency matrix representations of graphs, and we will cover basic graph traversal algorithms. The reading is Chapter 22.

Reminder: There is an in-class test coming up next Monday, March 4.

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.