COMP 7712 Algorithms/Problem Solving (Fall 2020)

Lectures: Tu,Th : 11:20 AM - 12:45 PM Dunn Hall 119

Textbook and reference books

Textbook: Algorithms by Dasgupta, Papadimitriou, and Vazirani

Reference book: Algorithms book by Jeff Erickson

Instructor Information

Name: Nirman Kumar
Office: Dunn Hall 307
Phone: (901) 678-3135
Office Hours : F 4-5 PM
Home page : http://www.cs.memphis.edu/~nkumar

Teaching Assistants

Sahil Nokhwal (snokhwal@memphis.edu). Office hours : W 10-11 AM.

Course Description

We will cover standard algorithm design techniques such as dynamic programming, recursion, greedy, graph traversals and paths, max flows and maybe some optimization algorithms. Randomized algorithms can make an appearance here and there.


See the Course Syllabus here.

Schedule

Date Item Relevant link
Tues Aug 18th Course intro
Thur Aug 20th Divide and Conquer Chapter 2 of Dasgupta-Papadimitriou-Vazirani book
Tues Aug 25th Divide and Conquer contd. Chapter 2 of Dasgupta-Papadimitriou-Vazirani book
Thur Aug 27th Divide and Conquer contd. and HW1 Chapter 2 of Dasgupta-Papadimitriou-Vazirani book and HW1
Tues Sep 1st Problem solving
Thur Sep 3rd Decomposition of graphs and HW1 due Chapter 3 of Dasgupta-Papadimitriou-Vazirani book
Tues Sep 8th Decomposition of graphs and HW2 Chapter 3 of Dasgupta-Papadimitriou-Vazirani book and HW2
Thur Sep 10th Decomposition of graphs contd. Chapter 3 of Dasgupta-Papadimitriou-Vazirani book
Tues Sep 15th Problem solving and HW2 due
Thur Sep 17th Paths in graphs Chapter 4 of Dasgupta-Papadimitriou-Vazirani book
Tues Sep 22nd Paths in graphs contd. Chapter 4 of Dasgupta-Papadimitriou-Vazirani book
Thur Sep 24th Paths in graphs contd. and PA1 Chapter 4 of Dasgupta-Papadimitriou-Vazirani book and PA1
Tues Sep 29th Problem solving
Thur Oct 1st Mid-term exam
Tues Oct 6th Greedy algorithms and PA1 due and HW3 Chapter 5 of Dasgupta-Papadimitriou-Vazirani book and HW3
Thur Oct 8th Greedy algorithms contd. Chapter 5 of Dasgupta-Papadimitriou-Vazirani book
Tues Oct 13 Greedy algorithms contd. and HW3 due Chapter 5 of Dasgupta-Papadimitriou-Vazirani book
Thur Oct 15th Problem solving and PA2 PA2
Tues Oct 20th Dynamic Prog. Chapter 6 of Dasgupta-Papadimitriou-Vazirani book
Thur Oct 22nd Dynamic Prog. contd. and PA2 due Chapter 6 of Dasgupta-Papadimitriou-Vazirani book
Tues Oct 27th Dynamic Prog. contd. and HW4 Chapter 6 of Dasgupta-Papadimitriou-Vazirani book and HW4
Thur Oct 29th Problem solving
Tues Nov 3rd NP-completeness and HW4 due and PA3 Chapter 8 of Dasgupta-Papadimitriou-Vazirani book and PA3
Thur Nov 5th NP-completeness contd. Chapter 8 of Dasgupta-Papadimitriou-Vazirani book
Tues Nov 10th NP-completeness contd., Problem Solving and PA3 due and HW5 Chapter 8 of Dasgupta-Papadimitriou-Vazirani book and HW5
Thur Nov 12nd Optimization Chapter 7 of Dasgupta-Papadimitriou-Vazirani book
Tues Nov 17th Optimization contd. and HW5 due Chapter 7 of Dasgupta-Papadimitriou-Vazirani book
Thur Nov 19th FINAL EXAM (8 AM - 10 AM)