# CSE 203A

# 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

## 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

Correctness proof for Dijkstra's shortest-path algorithm