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:
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.
Data structures: linked list, queues, stacks, binary search trees, hashing, heaps.
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:
Recurrence relations, lower bounds, amortized analysis
Greedy Algorithms: task scheduling, shortest path.
Divide and Conquer: faster matrix multiplication, FFT, median-finding.
Dynamic Programming: Longest common subsequence, matrix chain multiplication.
Randomized algorithms: max-cut, primality test
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