CSE 203A - Advanced Algorithms

Winter 2017

People

Professor: Ramamohan Paturi
Room: CSE 4246
Email: paturi@cs.ucsd.edu
Teaching Assistant: Zhen Zhai
Email: zzhai@eng.ucsd.edu

Syllabus, evaluation, and hours

Syllabus
Evaluation and hours

Prerequisites

  • Combinatorics and discrete mathematics (as covered in CSE 20 and 21 at UC San Diego)
  • Algorithms as covered in CSE 101 at UC San Diego.
  • Linear algebra and calculus
  • Probability
  • Preferably a graduate course in algorithms (for example, CSE 202)
  • Specifically, the course assumes competency in the following topics:
    • growth rates of functions,
    • formulating and solving recurrence relations,
    • combinatorial reasoning,
    • basic graph theory,
    • proving the correctness of algorithms,
    • sorting, selection, and searching algorithms,
    • standard data structures: arrays, stacks, queues, trees, heaps, binary search trees, and graphs, 
    • divide-and-conquer, greedy and dynamic programming techniques,
    • graph exploration techniques: breadth-first search and depth-first search, and
    • standard graph algorithms: minimum spanning trees and shortest paths
    • linear algebra:
    • probability:

Academic Honesty

Each student is expected to work by herself/himself to complete homework, tests, and projects. However, in the case of homework, students are encouraged to discuss high-level ideas and strategies among themselves in small groups. This in no way relieves the responsibility on the part of each student to work out all the details and write the solutions by herself/himself.

The authorized materials for this course include the course text book (as well as textbooks or lecture notes of prerequisite courses), supplementary reading,  and materials posted on this website for the current quarter. Use of any other materials or aids to complete a homework, test or project requires an explicit approval from the instructor. Here is the UCSD Policy on Integrity of Scholarship, which you are expected to adhere in letter and spirit. You may also find my colleague Scott Baden's write-up on Integrity of Scholarship Agreement useful.

General Resources

  1. Guidelines for writing solutions
  2. Correctness proof for Dijkstra's shortest-path algorithm
  3. Scheduling events to minimize the number of rooms
  4. Makespan problem --- approximation algorithm
  5. Weighted vertex cover --- approximation algorithm using layering method by Yatharth Saraf