Lectures:

MWF: 09:00 AM - 09:50 AM

Location: (on Zoom from 01/03 to 01/28) Student Success Center | Room 216

Instructor:

Amey Bhangale (ameyb AT ucr.edu)

Office hours: Fridays 10am - 11 am PST

TA:

Aakash Ramchandani (aramc003 AT ucr.edu)

Office hours: Fridays 12pm - 2 pm PST

Text Books:

• "Algorithms" by S. Dasgupta, C. Papadimitriou, U. Vazirani, McGraw Hill 2008.

• Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, MIT Press.

Prerequisites by topic:

1. Mathematics: Asymptotic notation, counting (permutations, sets, combinations, binomial coefficients), recurrence relations (linear and divide-and-conquer), basic probability (independence, random variable, expected value), basic linear algebra (vectors, matrices, and operations on them, solving linear systems), modular arithmetic.

2. Data structures: linked list, queues, stacks, binary search trees, hashing, heaps.

3. Algorithms: Sorting algorithms (selection, insertion, bubblesort, shellsort, quicksort, mergesort, heapsort, radix-sort, bucket-sort), graph searching (DFS, BFS), connected components, strongly connected components, transitive closure, topological sorting.

Grading: (2-4) Quizzes 30%, (4) Homework 40%, (1) Final Exam 30%

(Homework papers need to be formatted with LaTeX. For your convenience, a LaTeX template for homework assignments will be available.)

Tentative list of topics:

1. Recurrence relations, lower bounds, amortized analysis

2. Greedy Algorithms: task scheduling, shortest path.

3. Divide and Conquer: faster matrix multiplication, FFT, median-finding.

4. Dynamic Programming: Longest common subsequence, matrix chain multiplication.

5. Randomized algorithms: max-cut, primality test

6. Graph Algorithms: Spanning trees, Max-flow Min-Cut.

Tentative schedule:

Week 1

Introduction, course overview, Fibonacci sequence.

Fibonacci sequence - near linear time algorithm

Basic data structures review: Binary search trees, Heaps

Week 2:

Basic data structures review: Hashing, Universal Hash function, stacks, queue.

Basic algorithms review: Asymptotic notations, Master Theorem, Sorting, DFS, BFS, Strongly Connected Components,

Topological sorting, Minimum spanning tree.:

Divide and Conquer: Merge Sort, Integer multiplication, Median finding.

Divide and Conquer: Fast Fourier Transform introduction.

Week 3:

(HW1 out) FFT algorithm, O(n poly(log n)) integer multiplication.

Dynamic Programming: Shortest path in a DAG, Max independent sets in trees.

Week 4:

(HW1 due) Dynamic Programming: Longest increasing subsequence, Edit distance, Knapsack.

(Quiz *) Greedy Algorithms: Minimum spanning trees

Week 5:

(HW2 out) Greedy Algorithms: MST cont., Union-Find data structure

Union-Find data structure cont., Huffman Encoding

Week 6:

Greedy Algorithms: Task scheduling, Dijkstra's algorithm

(HW2 due) Correctness of Dijkstra's algorithm, Bellman-Ford shortest path

Week 7:

Max-Flow and Min-Cut, Ford-Fulkerson Algorithm.

(HW3 out) Applications of Max-Flow algorithm

Week 8:

Randomized Algorithms: Contention Resolution, Ramsey graphs

(HW3 due)

Week 9:

(HW4 out) Randomized Algorithms: Expectation, Max-Cut, QuickSort

(Quiz *) P, NP, NP-completeness

Week 10:

(HW4 due) Reductions, proving NP-completeness

Week 11:

March 14: Final Exam