CS 218: Design and Analysis of Algorithms

Fall Quarter, 2007

News

  • Dec 9: problems discussed in class posted.
  • Dec 7: hw5 solution posted.
  • Nov 27: hw5 and solution hw4 posted.
  • Nov 26: final time/date poster (12-12-07, OLMH 1133, 1130AM-230PM).
  • Nov 21: final syllabus posted.
  • Nov 14: hw3 solution updated.
  • Nov 13: hw4 posted.
  • Nov 13: hw3 solution posted.
  • Nov 12: hw3 revised (typo).
  • Nov 9: midterm and solution posted.
  • Nov 7: some more problems posted.
  • Nov 5: "dynamic programming" slides posted.
  • Nov 1: mock exam posted.
  • Oct 31: hw3 posted.
  • Oct 30: midterm syllabus posted.
  • Oct 30: hw2 solution posted.
  • Oct 18: hw1 solution revised.
  • Oct 16: hw2 and hw1 solution posted.
  • Oct 9: "divide and conquer" slides posted.
  • Oct 5: room change, Surge 171.
  • Oct 3: problems with the mailing list should be resolved.
  • Oct 1: homework 1 posted.
  • Sep 26: room change. SPIETH Hall 1222.
  • Lecture Schedule  Email list   Resources   Tutorials   Animations

    Overview

    Catalog description: CS 218. Design and Analysis of Algorithms (4) Lecture, 3 hours; outside research, 3 hours. Prerequisite(s): CS 141. Study of efficient data structures and algorithms for solving problems from a variety of areas such as sorting, searching, selection, linear algebra, graph theory, and computational geometry. Worst-case and average-case analysis using recurrence relations, generating functions, upper and lower bounds, and other methods. UCR course schedule, UCR course catalog.

    Basic information

    Instructor: Stefano Lonardi (stelo AT cs.ucr.edu)
    Office hours: Wedneday 10:30-12noon. Office: Engineering 2, 317.

    Teaching Assistant:
  • Vincent Peng (mpeng AT cs.ucr.edu)
    Office hours: Thu 2pm-3pm (EBU II 110).

  • Lectures:
  • TR, 3:40pm-5pm Surge 171

  • Text Book:
  • Introduction to Algorithms (2nd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, MIT Press.

  • Prerequisites:
  • Graduate standing, undergraduate courses in algorithms and data structures.

  • Prerequisites by topic:
  • Discrete Math: asymptotic notation, basic summation formulas, sets (operations on sets, relations, functions), counting (permutations, sets, combinations, binomial coefficients), probability (independence, random variable, expected value)
  • Basic Data Structures: array, list, queue, stack, binary search trees, balanced binary search trees, heap
  • Sorting and Searching: quicksort, mergesort, heapsort, radix-sort, binary search
  • Graph algorithms: DFS, BFS, connected components, biconnected components, transitive closure
  • Digraph algorithms: DFS, BFS, strongly connected components, topological sorting
  • Lectures


    Tentative list of topics
  • Intro to Analysis: recurrence relations, master theorem, amortized analysis
  • Pattern matching: brute force, KMP, tries and suffix trees
  • Greedy: task scheduling, factional knapsack, Huffman codes, Dijkstra, Prim, Kruskal
  • Union-Find: list and tree implementation, union by rank and path compression, analysis
  • Divide and conquer: lineat-time selection, Strassen, FFT, Integer multiplication
  • Dynamic programming: Subset sum, LCS, matrix chain multiplication, Floyd-Warshall
  • Graph algorithms: Flow and matching
  • Numerical algorithms: primality testing, RSA
  • Data structures: binomial heaps and Fibonacci heaps, splay trees
  • Actual list of topics

  • Sep 27: Course overview, Analysis of Algorithms (slides 1-22)
  • Oct 2: Analysis of Algorithms (23-45) [HW1 posted]
  • Oct 4: Analysis of Algorithms (46-63)
  • Oct 9: Analysis of Algorithms (64-end), Divide and Conquer (1-22)
  • Oct 11: Divide and Conquer (23-58)
  • Oct 16: Divide and Conquer (59-71) [HW1 due, HW2 posted]
  • Oct 18: Divide and Conquer (72-end), Greedy (1-28)
  • Oct 23: Gredy (29-52)
  • Oct 25: Greedy (53-75)
  • Oct 30: Greedy (76-108) [HW2 due, HW3 posted]
  • Nov 1: Greedy (109-end): Lecture by Prof. Young
  • Nov 6: Midterm Prep
  • Nov 8: [Midterm (80mins, in class, closed book, closed notes)]
  • Nov 13: Midterm review, Dynamic Programming (1-22) [HW3 due, HW4 posted]
  • Nov 15: Dynamic Programming (23-51)
  • Nov 20: Dynamic Programming (52-78)
  • Nov 22: Thanksgiving
  • Nov 27: Dynamic Programming (79-end), Network Flow (1-26)[HW4 due, HW5 posted]
  • Nov 29: Network Flow (27-end)
  • Dec 4: String Matching (1-end)
  • Dec 6: Review [HW5 due]
  • Dec 12: [Final (OLMH 1133, 1130AM-230PM, closed book, closed notes)]
  • Slides

  • Intro [PDF 2pages/slide]
  • Algorithm Analysis [PDF 2pages/slide]
  • Divide and Conquer algorithms [PDF 2pages/slide]
  • Greedy algorithms [PDF 2pages/slide]
  • Dynamic Programming algorithms [PDF 2pages/slide]
  • Network flow algorithms [PDF 2pages/slide]
  • Pattern Matching algorithms [PDF 2pages/slide]
  • Homework

    Quizzes/Exams

    General course features and policies

    Course email list

    Course mailing list (send mail now): Be sure to sign up to receive important announcements, which will be made only through the course email list. You must use your CS or EE account, or else some other UCR account, so be sure to learn how to read those accounts or at least automatically forward messages to your personal email address (just create in your home directory a file named ".forward" containing your personal email address).

    Tutorials

    Algorithm Animations