Lectures:
Tue and Thu: 2:00pm-3:20pm
Instructor:
Amey Bhangale (bhangale AT cs.ucr.edu)
Office hours: Monday 2:00-3:00pm or by appointment.
TA:
Wei Song (wsong008 AT ucr.edu)
Office hours: Monday 3:00-5:00 pm.
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) Quizzes 40%, (4) Homework 40%, (1) Final Exam 20%
(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.
Actual list of topics
Week 0
OCT 1: Introduction, course overview, Fibonacci sequence.
Week 1
OCT 6: Basic data structures review: Binary search trees, Heaps, hashing, asymptotic notations
OCT 8: (Quiz 0) Basic algorithms review: Master Theorem, Sorting, DFS, BFS, Strongly Connected Components,
Topological sorting, Minimum spanning tree.
Week 2:
OCT 13: (HW1 out) Divide and Conquer: Merge Sort, Integer multiplication, Median finding.
OCT 15: (Quiz 1) Divide and Conquer: Fast Fourier Transform introduction.
Week 3:
OCT 20: (HW1 due) FFT algorithm, O(n poly(log n)) integer multiplication.
OCT 22: Dynamic Programming: Shortest path in a DAG, Max independent sets in trees.
Week 4:
OCT 27: (HW2 out) Dynamic Programming: Longest increasing subsequence, Edit distance, Knapsack.
OCT 29: (Quiz 2) Greedy Algorithms: Minimum spanning trees
Week 5:
NOV 3: (HW2 due) Greedy Algorithms: MST cont., Union-Find data structure
NOV 5: Union-Find data structure cont., Huffman Encoding
Week 6:
NOV 10: Greedy Algorithms: Task scheduling, Dijkstra's algorithm
NOV 12: (HW3 out, Quiz 3) Correctness of Dijkstra's algorithm, Bellman-Ford shortest path
Week 7:
NOV 17: Max-Flow and Min-Cut, Ford-Fulkerson Algorithm.
NOV 19: (HW3 due) Applications of Max-Flow algorithm
Week 8:
NOV 24: Randomized Algorithms: Contention Resolution, Ramsey graphs
NOV 26: (HW4 out) no class (Thanksgiving)
Week 9:
DEC 1: Randomized Algorithms: Expectation, Max-Cut, QuickSort
DEC 3: (Quiz 4) P, NP, NP-completeness
Week 10:
DEC 8 : (HW4 due) Reductions, proving NP-completeness
DEC 10: Review
Week 11:
Final Exam
.
.
.