Lectures:

T T: 11:00 AM - 12:20 PM

Location:  Student Success Center | Room 316

Instructor:

Amey Bhangale (ameyb AT ucr.edu)

Office hours: Tue 02:00 PM - 03:00 PM

TA:

  Yezhou Zhang (yzhan823 AT ucr.edu) 

Office hours: Thursday 1:00 PM - 1:50 PM at WCH 110

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:  4 Homework 20%, (1) Midterm Exam 30%,  (1) Final Exam 50%

(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

(HW0 out)

Introduction, course overview, Fibonacci sequence.

Fibonacci sequence - near-linear time algorithm

       Basic data structures review. Binary search trees, Heaps, Hashing, Universal Hash function, stacks, queue.

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

Topological sorting, Minimum spanning tree.:

Week 2:

(HW1 out)

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

Divide and Conquer: Fast Fourier Transform introduction.

Week 3:

(HW1 due) 

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

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

Week 4:

(HW2 out) 

Dynamic Programming: Longest increasing subsequence, Edit distance, Knapsack.

Greedy Algorithms: Minimum spanning trees

Week 5:

(HW2 due)

Greedy Algorithms: MST cont., Union-Find data structure

Union-Find data structure cont., Huffman Encoding

Week 6:

(HW3 out) (Midterm Exam)

Greedy Algorithms: Task scheduling, Dijkstra's algorithm

 Correctness of Dijkstra's algorithm, Bellman-Ford shortest path

Week 7:

(HW3 due) 

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

Applications of Max-Flow algorithm

Week 8:

(HW4 out) 

Randomized Algorithms: Contention Resolution, Ramsey graphs

Randomized Algorithms: Expectation, Max-Cut, QuickSort

Week 9:

(HW4 due)

P, NP, NP-completeness

Week 10:

Reductions, proving NP-completeness

Week 11:

Final Exam