CS 218: DESIGN&ANALYSIS OF ALGORITHMS (Fall 2020)

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:


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


  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.

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

.

.

.