CSCI B503: Algorithms Design and Analysis

Spring 2017

Monday, Wednesday 1:00pm - 2:15pm, BH 310

Description

This is an introductory graduate-level course on algorithm design and analysis, covering fundamental techniques in designing algorithms and proving bounds on their time and space complexity.

As the course focuses on the analysis (therefore mathematical aspect) of algorithms, students are expected to have a solid undergraduate mathematical background (e.g., elementary combinatorics, discrete probability, basic linear algebra and calculus). Students are also expected to have learned elementary algorithms, including basic data structures, basic sorting and searching, elementary graph terminology, and asymptotic analysis of time and space complexity for algorithms (i.e. big-O/Omega/Theta notation). There will be no programming requirement in this course. However, it will be very helpful to have past experience with implementation of basic algorithms and data structures.

Course Information Syllabus

Date Topic   Reading     Homework  
Jan 9 (Mon) Introduction on course materials,
logistics, and pre-requisites
Jan 11 (Wed) Lecture 01: Interval Scheduling Problem KT 4.1 (Before "A Related Problem") Homework 1 out
Jan 18 (Wed) Lecture 02: Scheduling All Intervals
and Minimum Spanning Trees
KT 4.1 (After "A Related Problem"),
KT 4.5 (before "Analyzing the Algorithms")
Jan 23 (Mon) Lecture 03: Kruskal's Algorithm
and the Reverse-Delete Algorithm
KT 4.5
Jan 25 (Wed) Lecture 04: Implementing Kruskal's Algorithm
with the Union-Find Data Structure
KT 4.6 Homework 1 due
Homework 2 out
Jan 30 (Mon) Lecture 05: Prim's Algorithm
and Boruvka's Algorithm
KT 4.5
Wikipedia Page on Boruvka's Algorithm
Feb 1 (Wed) Lecture 06: The Single Source Shortest Path Problem
and Dijkstra's Algorithm
KT 4.4
Feb 6 (Mon) Lecture 07: The Stable Matching Problem KT 1.1
Feb 8 (Wed) Lecture 08: One-Side Optimality of Gale-Shapley
and the Parity of Intervals Problem
Homework 2 due
Feb 13 (Mon) Midterm 1
Feb 15 (Wed) Lecture 09: Merge Sort and Solving Recurrences KT 5.1 & 5.2 Homework 3 out
Feb 20 (Mon) Lecture 10: Counting Inversions and Peak Finding KT 5.3
Feb 22 (Wed) Lecture 11: Integer Multiplication KT 5.5
Feb 27 (Mon) Lecture 12: Closest Pair of Points KT 5.4
Mar 1 (Wed) Lecture 13: Convolution and
Fast Fourier Transform (Part I)
KT 5.6 Homework 3 due
Homework 4 out
Mar 6 (Mon) Lecture 14: Fast Fourier Transform (Part II) and
Introduction to Dynamic Programming
KT 5.6, 6.1 & 6.2
Mar 8 (Wed) Lecture 15: Segmented Least Squares KT 6.3
Mar 20 (Mon) Lecture 16: The Knapsack Problem KT 6.4
Mar 22 (Wed) Lecture 17: RNA Secondary Structure KT 6.5 Homework 4 due
Mar 27 (Mon) Midterm 2
Mar 29 (Wed) Lecture 18: Sequence Alignment KT 6.6 Homework 5 out
Apr 3 (Mon) Lecture 19: Linear Space Algorithm for Sequence
Alignment and Bellman-Ford Algorithm
KT 6.7, 6.8 & 6.10
Apr 5 (Wed) Lecture 20: All-Pair Shortest Path Problem
and Floyd-Warshall Algorithm
Wikipedia page on
Floyd-Warshall Algorithm
Apr 10 (Mon) Lecture 21: The Maximum Flow Problem
and Ford-Fulkerson Algorithm
KT 7.1
Apr 12 (Wed) Lecture 22: The Maximum Flow Minimum Cut Theorem KT 7.2 Homework 5 due
Homework 6 out
Apr 17 (Mon) Lecture 23: Capacity-Scaling Algorithm and
the Maximum Matching Problem
KT 7.3
Apr 19 (Wed) Lecture 24: Hall's Theorem and
the Image Segmentation Problem
KT 7.5 & 7.10
Apr 24 (Mon) Lecture 25: Baseball Elimination KT 7.12
Apr 26 (Wed) Lecture 26: Project Selection KT 7.11 Homework 6 due