CS 58000 Algorithm Design, Analysis and Implementation

Course Information, Spring 2014

Overview:

This course is about designing algorithms and analyzing correctness and running time. A tentative list of covered topics include

- Data structure: the way to store and organize data. (We assume you already know what are binary trees, heaps and linked lists from previous courses).
- Random Binary Tree (Treaps)
- Union find

- Techniques: “template" for designing algorithms
- Greedy algorithm
- Dynamic programming
- Divide and Conquer
- Fast Fourier Transform
- Network Flow
- Randomized Algorithms

- Tools for Analyzing Algorithm
- Asymptotic Analysis
- Amortized Analysis
- Probabilistic Analysis

- Classic Problems
- Graph Algorithm
- Algorithm on Integers
- String Algorithms

- Intractability, NP-Completeness Reduction and Approximation Algorithms

Discussion Board:

sign up at

It is recommended to ask questions on the Board instead of directly Emailing the teaching staffs.

Grading: Grading will be done as follows:

- biweekly homework: 20%
- midterm: 40%
- final: 40%
- class and piazza participation & bonus problem: adjust borderline scores

Homework Policy:

- Written homeworks are due at the start of class on their due date.
- If you do not know the answer of question, you will receive 15% of the grade for the problem if you admit it up-front by writing “I don’t know how to solve this problem” and nothing else. If your solution is wrong, you get a score of 0 for that problem.
- You are encouraged to work in groups of 2 or 3. On all assignments each person should hand-in their own writeup. That is, collaboration should be limited to talking about the problems, so that your writeup is written entirely by you alone, in your own words.
- We
**will not**accept late submission. To offset this strict policy, - we will drop the lowest homework grade in the end so that the occasional absence won’t hurt you.
- each individual student has a single 48 hours pass. This pass can be used to extend the deadline for one homework by 48 hours.

- We prefer that you type up your solutions (preferably using LaTeX). You may neatly hand-write your solutions, but if we have trouble reading them you will be required to type up future solutions.
- If you find a solution from
*any*other source, you must rewrite entirely using your own words and cite properly. - The TA rules when it comes to grading homework; their decisions are ﬁnal. However, they will be available to listen to your explanations.

Recommended Textbook

- Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS").
- Algorithm Design by J. Kleinberg and E. Tardos (hereafter refererred as "KT").

Academic Integrity: