Lectures:

Mon and Wed: 06:30 PM - 07:50 PM

Sproul Hall | Room 1340

Instructor:

Amey Bhangale (ameyb AT ucr.edu)

Office hours: Wed 4 pm - 6 pm

Teaching Assistants: 

Suryaa Charan Shivakumar

Yezhou Zhang

Office hours: 

TBA

Discussion:

• Tuesday 7:00PM - 7:50PM, (sec. 21) -- Yezhou

• Tuesday 12:00PM - 12:50PM (sec. 22) -- Suryaa

• Thursday 10:00AM - 10:50AM (sec 23) -- Suryaa.

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 eLearn (check your eLearn account) no later than Wednesday, 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

04/03: Introduction

04/05: Asymptotic notations, recurrence relations

Week 2

04/10: (HW1 out) Master theorem, divide-and-conquer - Linear-time selection, Integer multiplication

04/12: (Quiz 1, in class) more divide-and-conquer - Matrix Multiplication, Closest pair

Week 3

04/17: Finish divide-and-conquer, greedy algorithms

04/19: (HW1 due) Greedy algorithms - Interval scheduling, fractional Knapsack

Week 4:

04/24: Greedy algorithms - Huffman encoding

04/26: (Quiz 2, in class) (HW2 out) Greedy algorithms - Finish Huffman encoding

Week 5

05/01: (Midterm 1, take home, submit by EoD) Dynamic programming - Counting, Fibonacci, 0/1Knapsack

05/03: (HW2 due) Dynamic programming - Finish /1Knapsack, longest increasing subsequence

Week 6

05/08: (Quiz 3, in class) Dynamic programming - Longest common Subsequence

05/10: (HW3 out) Dynamic programming - Sequence alignment. Trees - review

Week 7:

05/15: Graphs - DFS on undirected graphs/BFS

05/17: (HW3 due) Graphs - DFS/BFS on directed graphs, connected components, cycle, topological ordering, etc.

Week 8

05/22: (Quiz 4, in class) Graphs - Dijkstra's shortest path algorithm

05/24: (HW4 out, Midterm 2)  Graphs - Dijkstra's shortest path algorithm, Bellman-Ford

Week 9:

05/29:   (no class, holiday)

05/31: (HW4 due) Graphs - Bellman-Ford

Week 10

06/05:, Floyd-Warshall, MSTs

06/07: Finish MST, Review, etc.

Finals week

06/13: Midterm 3 (a.k.a final exam)