CS1570: Design and Analysis of Algorithms
Fall 2023
Course Info
This is a core undergraduate Computer Science course on the foundations of algorithmic theory and applications. The questions it aims to answer are:We will cover these questions and, in the process, explore the use of algorithms in important applications such as artificial intelligence, data management, network analysis, and geographic information systems. The course has lectures, written homework assignments, and exams.
- What are the different algorithmic archetypes? How can we analyze the performance of algorithms?
- Which design guidelines should be followed towards achieving efficient algorithms?
- What data structures can be used for specific algorithmic tasks?
Lectures
Lectures are held in-person on Tuesdays and Thursdays from 2:30 to 3:50p.m. in CIT 241. Lecture slides will be posted on EdStem and recordings will be available on Panopto.
| Lecture Topic | Date |
|---|---|
| Introduction | 09/07 |
| Preliminary Concepts | 09/12 |
| Comparison-Based Sorting | 09/14 |
| Searching & Non-Comparison Sorting | 09/19 |
| Greedy Algorithms I | 09/21 |
| Greedy Algorithms II | 09/16 |
| Dynamic Programming Algorithms I | 09/28 |
| Dynamic Programming Algorithms II | 10/03 |
| Divide & Conquer Algorithms I | 10/05 |
| Divide & Conquer Algorithms II | 10/10 |
| Basic Data Structures | 10/12 |
| Tree Data Structures | 10/17 |
| Hash-Based Data Structures | 10/19 |
| Graph Algorithms I | 10/26 |
| Graph Algorithms II | 10/31 |
| Text Processing & Pattern Matching | 11/02 |
| Computational Geometry I | 11/07 |
| Computational Geometry II | 11/09 |
| Limits of Computation I | 11/11 |
| Limits of Computation II | 11/16 |
| Limits of Computation III | 11/28 |
| External Memory Algorithms I | 11/30 |
| External Memory Algorithms II | 12/05 |
Assignments
All assignments must be typeset using LaTeX and submitted on Gradescope. Please refer to the syllabus for the class collaboration and late submission policy.
| Assignment | Out | Due | Solution |
|---|---|---|---|
| Getting Started | 09/07 | 09/14 | |
| Proof Techniques | 09/12 | 09/19 | |
| Searching & Sorting | 09/19 | 09/26 | |
| Greedy Algorithms | 09/26 | 10/03 | |
| Dynamic Programming | 10/03 | 10/12 | |
| Divide & Conquer | 10/12 | 10/19 | |
| Data Structures | 10/26 | 11/02 | |
| Graph Algorithms | 11/02 | 11/09 | |
| String Algorithms & Computational Geometry | 11/09 | 11/30 | |
| Complexity Theory | 11/30 | 12/7 |
Hours
Hours will follow an open format, where students can work together in groups to brainstorm solutions and ask the TA for help when needed.
In order to safeguard everyone's health, please refrain from going to in-person hours if you are feeling unwell or experiencing any symptoms. Reach out to the TA staff to inquire about the availability of remote TA hours.
Resources
Course Syllabus
You can find the course syllabus here! The course collaboration policy and late day policy for all assignments are also included in the syllabus.Anonymous Feedback Form
If you have any feedback for the course staff, please feel free to submit it here! All submissions are welcome!LaTeX Resources
For this course your solutions must be typeset using LaTeX. Below are some resources that you might find helpful:- Overleaf is an online LaTeX editor that you can use to write your solutions.
- Overleaf LaTeX Documentation is a great resource for learning LaTeX.
- Detexify is a tool that allows you to draw a symbol and get the corresponding LaTeX code.
- Pseudocode Guide contains our recommendations for typesetting pseudocode in LaTeX.
- The CS1570 class file is used to apply our styles and macros for your LaTeX documents. You'll want this if you prefer not to use our Overleaf template.
Department Resources
The CS department provides many resources to help students succeed in their courses.Brown CS Health And Wellness
If you need accommodation for your physical and mental health, please feel free to reach out to Professor De Stefani — we want to support you as much as we can in the most comfortable way for you. It is important to note that TAs should not be handling health and accomodations information, so inquiries should be directed towards the professor only. Resources for physical/mental health, accessibility, and accommodations can be found here.Staff
You can reach the entire course staff at cs1570tas@lists.brown.edu, the HTA and Professor at cs1570htas@lists.brown.edu and just the Professor at lorenzo_destefani@brown.edu.
Lorenzo De Stefani Professor
Hammad Izhar HTA
Luke Choi UTA
Nishchay Parashar UTA
Neil Xu UTA
Michael Youssef UTA
