CSCI 358 - Fall 2021
Applied Algorithms
Home | Lectures | Assignments | Handouts | Leaderboard | CS@Williams
Home
| Instructor: | Sam McCauley |
| Email: | srm2@cs.williams.edu |
| Phone: | x2744 |
| Office: | TCL 306 |
| Office Hours: | Mon 2:30-4 & 5-6:30pm, TCL 306 Wed 2-4pm, TCL 312 |
| TA: | Christopher Chung |
| TA Office Hours: | Tue 3-5pm, TCL 312 Wed 8-10pm, TCL 312 |
| Lectures: | MR 1:10-2:25 |
| Assignments are due Wednesday @ 10 pm |
Course Description
This course is about bridging the gap between theoretical running time and writing fast code in practice. The course is divided into two basic topics. The first is algorithmic: we will discuss some of the most useful tools in a coder's toolkit. This includes topics like randomization (hashing, filters, approximate counters), linear and convex programming, similarity search, and cache-efficient algorithms. Our goal is to talk about why these efficient algorithms make seemingly difficult problems solvable in practice. The second topic is applications: we will discuss how to implement algorithms in an efficient way that takes advantage of modern hardware. Specific topics covered will include blocking, loop unrolling, pipelining, as well as strategies for performance analysis. Projects and assessments will include both basic theoretical aspects (understanding why the algorithms we discuss actually work), and practical aspects (implementing the algorithms we discuss to solve important problems, and optimizing the code so it runs as quickly as possible).
Coding in this course will be done in C. All testing will be done on TCL 312 lab computers.
Syllabus & Textbook
The course syllabus is here.
There is no textbook for this course. Readings for specific topics will be linked to from the Lectures page.
Certain textbooks may be helpful for background, however; here are some suggestions that I have found useful in the past. Copies of these books will be available in TCL 312.