Lectures:
Mon and Wed: 06:30 PM - 07:50 PM
Sproul Hall | Room 1340
Instructor:
Amey Bhangale (ameyb AT ucr.edu)
Office hours: Wed 4 pm - 6 pm
Teaching Assistants:
Suryaa Charan Shivakumar
Yezhou Zhang
Office hours:
TBA
Discussion:
Tuesday 7:00PM - 7:50PM, (sec. 21) -- Yezhou
Tuesday 12:00PM - 12:50PM (sec. 22) -- Suryaa
Thursday 10:00AM - 10:50AM (sec 23) -- Suryaa.
Prerequisites: CS 014, CS 111, MATH 009C (MATH 009HC). The prerequisites are strictly enforced.
Text Book:
Introduction to Algorithms - Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein -
ISBN 9780262033848
"Algorithms" by S. Dasgupta, C. Papadimitriou, U. Vazirani, McGraw Hill 2008.
Grading: (approximately) 4-5 Quizzes + 4-5 Homework (40%), 3 Midterms (50%) & possibly a final presentation (10%)
(Homework papers need to be formatted with LaTeX. For your convenience, a LaTeX template for homework assignments will be available.)
Academic Integrity: Zero-tolerance policy on plagiarism is enforced. Cheating on homework assignments or tests will result in an F grade for the course and a disciplinary action, independently of the extent of plagiarism. You are required to print, read, and sign the academic integrity statement, and upload it to eLearn (check your eLearn account) no later than Wednesday, April 5. You can find more information here.
Tentative list of topics:
1. O-notation & Recurrence relations
2. Divide-and-conquer approach
3. Greedy algorithms
4. Dynamic programming
5. Graph algorithms and shortest path
Tentative Schedule:
Week 1
04/03: Introduction
04/05: Asymptotic notations, recurrence relations
Week 2
04/10: (HW1 out) Master theorem, divide-and-conquer - Linear-time selection, Integer multiplication
04/12: (Quiz 1, in class) more divide-and-conquer - Matrix Multiplication, Closest pair
Week 3
04/17: Finish divide-and-conquer, greedy algorithms
04/19: (HW1 due) Greedy algorithms - Interval scheduling, fractional Knapsack
Week 4:
04/24: Greedy algorithms - Huffman encoding
04/26: (Quiz 2, in class) (HW2 out) Greedy algorithms - Finish Huffman encoding
Week 5
05/01: (Midterm 1, take home, submit by EoD) Dynamic programming - Counting, Fibonacci, 0/1Knapsack
05/03: (HW2 due) Dynamic programming - Finish /1Knapsack, longest increasing subsequence
Week 6
05/08: (Quiz 3, in class) Dynamic programming - Longest common Subsequence
05/10: (HW3 out) Dynamic programming - Sequence alignment. Trees - review
Week 7:
05/15: Graphs - DFS on undirected graphs/BFS
05/17: (HW3 due) Graphs - DFS/BFS on directed graphs, connected components, cycle, topological ordering, etc.
Week 8
05/22: (Quiz 4, in class) Graphs - Dijkstra's shortest path algorithm
05/24: (HW4 out, Midterm 2) Graphs - Dijkstra's shortest path algorithm, Bellman-Ford
Week 9:
05/29: (no class, holiday)
05/31: (HW4 due) Graphs - Bellman-Ford
Week 10
06/05:, Floyd-Warshall, MSTs
06/07: Finish MST, Review, etc.
Finals week
06/13: Midterm 3 (a.k.a final exam)