Lectures:
Mon and Wed: 06:30 PM - 07:50 PM
WCH 138
Instructor:
Amey Bhangale (ameyb AT ucr.edu)
Office hours: Wednesdays, 05:00 - 06:00 PM or by appointment.
Teaching Assistants:
Yuta Nakamura
Office hours:
TBA
Discussion:
Tuesday 7:00PM - 7:50PM, (sec. 21),
Tuesday 12:00PM - 12:50PM (sec. 22),
Thursday 10:00AM - 10:50AM (sec 23).
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 Gradescope (check your gradescope account) no later than Monday, 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
Mar 28: Introduction
Mar 30: Asymptotic notations, recurrence relations
Week 2
Apr 4: (HW1 out) Master theorem, divide-and-conquer
Apr 6: (Quiz 1, in class) more divide-and-conquer
Week 3
Apr 11: Finish divide-and-conquer, greedy algorithms
Apr 13: (HW1 due) Greedy algorithms - Interval scheduling, fractional Knapsack
Week 4:
Apr 18: Greedy algorithms - Huffman encoding
Apr 20: (Quiz 2, in class) (HW2 out) Greedy algorithms - Finish Huffman encoding
Week 5
Apr 25: (Midterm 1, take home, submit by EoD) Dynamic programming - Counting, Fibonacci, 0/1Knapsack
Apr 27: (HW2 due) Dynamic programming - Finish /1Knapsack, longest increasing subsequence
Week 6
May 2: (Quiz 3, in class) Dynamic programming - Longest common Subsequence
May 4: (HW3 out) Dynamic programming - Sequence alignment. Trees - review
Week 7:
May 9: Graphs - DFS on undirected graphs/BFS
May 11: (HW3 due) Graphs - DFS/BFS on directed graphs, connected components, cycle, topological ordering, etc.
Week 8
May 16: (Quiz 4, in class) Graphs - Dijkstra's shortest path algorithm
May 18: (HW4 out) Graphs - Dijkstra's shortest path algorithm, Bellman-Ford
Week 9:
May 23: (Midterm 2, take home, submit by EoD) Graphs - Bellman-Ford, Floyd-Warshall, MSTs
May 25: (HW4 due) Finish MST, Review
Week 10
May 30: (no class, holiday)
June 1: Review, etc.