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 

  • UCR Bookstore

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