## Design and Analysis of Algorithms

CSCI 4020 @ RPI

## Numerical Methods for Differential Equations

### About

Notes and files from CSCI 4020 in Spring 2020 at RPI.

Instructor: Elliot Anshelevich

Course homepage: link

### Notes

**Lecture 02, Jan 17**: notes - Introduction

**Lecture 03, Jan 21**: notes - Greedy Algorithm; Exchange Argument; *Scheduling to Minimize Lateness*

**Lecture 04, Jan 24**: notes - Minimum Spanning Tree

**Lecture 05, Jan 28**: notes - Dynamic Programming; *Weighted Interval Scheduling*

**Lecture 06, Jan 31**: notes - *Segmented Least Squares*

**Lecture 07, Feb 04**: notes - *Subset Sum*; *Longest Increasing Subsequence Problem*

**Lecture 08, Feb 07**: notes - *Sequence Alignment and Edit Distance*

**Lecture 09, Feb 14**: notes - Divide and Conquer; *Merge Sort*; *Closest Pair of Points*

**Lecture 10, Feb 21**: notes - *Multiplying Polynomial*; *Fast Fourier Transform*

**Lecture 11, Feb 28**: notes - Max Flow and Min Cut; Residual Graph

**Lecture 12, Mar 03**: *N/A*

**Lecture 13, Mar 06**: notes - Edge-Disjoint Paths; Circulations w/o lower bounds

**Lecture 14, Mar 24**: notes - Survey Design; Image Segmentation

**Lecture 15, Mar 27**: notes - Image Segmentation; Project Selection

**Lecture 16, Mar 31**: notes - Polynomial-Time Reductions; Independent Set; Vertex Cover

**Lecture 17, Apr 03**: notes - P and NP; NP-Completeness; Set Cover

**Lecture 18, Apr 07**: notes - Reduction via Gadgets; SAT and 3-SAT; Independent Set

**Lecture 19, Apr 10**: notes - Sequenceing Problems; Hamiltonian Cycle

**Lecture 20, Apr 14**: notes - Longest Path; Travelling Salesperson Problem; 3-Coloring

**Lecture 21, Apr 17**: notes - Numerical Problems; Knapsack

### Problem Set

**Problem set 1**: my homework *(10/10)*, solutions

**Problem set 2**: my homework *(20/20)*, solutions

**Problem set 3**: my homework *(20/20)*, solutions

**Problem set 4**: my homework *(20/20)*, solutions

**Problem set 5**: my homework *(10/10)*

Note: Problem sets for this course are finished in group of two. The other author of these homework is **Xuan Liu**.

*Last Updated: May 07*