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

  • UCR Bookstore

• "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)