Lectures:
(Section 1) Mon and Wed: 06:30 PM - 07:50 PM (Humanities and Social Sciences | Room 1501)
(Section 2) Mon and Wed: 03:30 PM - 04:50 PM (Gordon Watkins Hall | Room 1101)
Instructor:
Amey Bhangale (ameyb AT ucr.edu)
Office hours: (Section 1) Mondays 2 pm - 3 pm
(Section 2) Wednesdays 2 pm - 3 pm
Teaching Assistants:
Yezhou Zhang & Yitong Dai
Office hours:
TBA
Discussion:
Tuesday 7:00PM - 7:50PM, (sec. 21) -- Yezhou
Tuesday 12:00PM - 12:50PM (sec. 22) -- Yitong
Thursday 10:00AM - 10:50AM (sec 23) -- Yitong.
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 (50%), 2 Midterms and a Final Exam (50%)
(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 Monday, April 8. 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/01: Introduction
04/03: Asymptotic notations, recurrence relations
Week 2
04/08: (HW1 out) Master theorem, divide-and-conquer - Linear-time selection, Integer multiplication
04/10: more divide-and-conquer - Matrix Multiplication, Closest pair
Week 3
04/15: (Quiz 1, in class) Finish divide-and-conquer, greedy algorithms
04/17: (HW1 due) Greedy algorithms - Interval scheduling, fractional Knapsack
Week 4:
04/22: (HW2 out) Greedy algorithms - Huffman encoding
04/24: Greedy algorithms - Finish Huffman encoding
Week 5
04/29: (Quiz 2, in class) Dynamic programming - Counting, Fibonacci, 0/1Knapsack
(Midterm 1, take home, submit by EoD)
05/01: (HW2 due) Dynamic programming - Finish /1Knapsack, longest increasing subsequence
Week 6
05/06: (HW3 out) Dynamic programming - Longest common Subsequence
05/08: Dynamic programming - Sequence alignment. Trees - review
Week 7:
05/13: (Quiz 3, in class) Graphs - DFS on undirected graphs/BFS
05/15: (HW3 due) Graphs - DFS/BFS on directed graphs, connected components, cycle, topological ordering, etc.
Week 8
05/20: (HW4 out) Graphs - Dijkstra's shortest path algorithm
05/22: (Midterm 2*) Graphs - Dijkstra's shortest path algorithm, Bellman-Ford
Week 9:
05/27: (no class, holiday)
05/29: (HW4 due) Graphs - Bellman-Ford
Week 10
06/03:, (Quiz 4, in class) Floyd-Warshall, MSTs
06/05: Finish MST, Review, etc.
Finals week
06/10-06/14: Midterm 3 (a.k.a the final exam)