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:
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: 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:
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
(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