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

  • UCR Bookstore

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