Lectures:
Mon and Wed: 06:30 PM - 07:50 PM
Instructor:
Amey Bhangale (ameyb AT ucr.edu)
Office hours: Wednesdays, 05:00 - 06:00 PM or by appointment.
Teaching Assistants:
Jacob Fauber (jfaub001@ucr.edu)
Office hours:
Tuesday 06:00PM-07:00PM.
Thursday 11:00AM-12:00PM.
Firday 02:00PM-03:00PM
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: 4 Quizzes + 4 Homework (50%), 2 -3 Midterms (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 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
The actual list of topics:
Week 1
Mar 29: Introduction
Mar 31: Asymptotic notations, recurrence relations
Week 2
Apr 5: (HW1 out) Master theorem, divide-and-conquer
Apr 7: (Quiz 1, in class) (HW1 out) more divide-and-conquer
Week 3
Apr 12: Finish divide-and-conquer, greedy algorithms
Apr 14: (HW1 due) Greedy algorithms - Interval scheduling, fractional Knapsack
Week 4:
Apr 19: (Quiz 2, in class) Greedy algorithms - Huffman encoding
Apr 21: (Quiz 2, in class) (HW2 out) Greedy algorithms - Finish Huffman encoding
Week 5
Apr 26: (Midterm 1, take home, submit by EoD) Dynamic programming - Counting, Fibonacci, 0/1Knapsack
Apr 28: (HW2 due) Dynamic programming - Finish /1Knapsack, longest increasing subsequence
Week 6
May 3: (Quiz 3, in class) Dynamic programming - Longest common Subsequence
May 5: (HW3 out) Dynamic programming - Sequence alignment. Trees - review
Week 7:
May 10: Graphs - DFS on undirected graphs/BFS
May 12: (HW3 due) Graphs - DFS/BFS on directed graphs, connected components, cycle, topological ordering, etc.
Week 8
May 17: (Quiz 4, in class) Graphs - Dijkstra's shortest path algorithm
May 19: (HW4 out) Graphs - Dijkstra's shortest path algorithm, Bellman-Ford
Week 9:
May 24: (Midterm 2, take home, submit by EoD) Graphs - Bellman-Ford, Floyd-Warshall, MSTs
May 26: (HW4 due) Finish MST, Review
Week 10
May 31: (no class, holiday)
June 2: [6:30pm - 8:30pm] Last lecture (Midterm 3, in class)