CS 3510

CS 3510, formally known as Design and Analysis of Algorithms, is a 3-credit Computer Science class taken as a thread requirement for six of the eight CS threads. Unlike CS 1332, which goes over a suite of specific algorithms, CS 3510 goes over broader categories of algorithms and algorithm design techniques, and in addition it teaches proof of correctness and proof of efficiency for algorithms. It is preceded by CS 1332 and CS 2050/CS 2051 or MATH 3012. It is succeeded by CS 4510, CS 4540, MATH 4150, CS 6515, and CS 4803/CS 4644.

Topic List

1. Basics of Pseudocode
2. Recurrence Relations, Big-O, and the Master Theorem
3. Divide-and-Conquer Algorithms
4. Dynamic Programming
5. Graph Algorithms
6. Network Flow
7. Optimization (with some semesters going over basic Linear Programming)
8. NP-Completeness, Complexity, and Hardness,
9. Approximation Algorithms

Textbooks used in this course in the past have included:

• Algorithms by Dasgupta, Papadimitriou, and Vazirani (used by Professor Vigoda, Spring 2020)
• Algorithm Design by Kleinberg and Tardos (used by Professor Dovrolis, Spring 2020)

Prerequisite Knowledge

Algorithms

As CS 3510 is an algorithms course, a working knowledge of basic sorting and graph algorithms is suggested. A good understanding of mergeSort and Djikstra's Single-Source Shortest-Path algorithm is a useful benchmark in assessing algorithms knowledge for the class.

Data Structures

While there is no explicit programming in this class, a lot of algorithms are written in psuedocode, and thus, a knowledge of basic data structures and how they work is essential. In particular, arrays, trees, and graphs are the most important data structures for success in the class.

Discrete Mathematics

An understanding of basic Set Theory, Big-O bounds, and fundamental number theory (Euclid's Algorithm, Fast Exponentiation) is useful for success in the class. Big-O is absolutely critical, while the other two are useful and will help, but are not required.

Combinatorial Mathematics

An understanding of graph theory and recurrences is absolutely essential for CS 3510. In addition, basic combinatorial mathematics (such as permutations and combinations) is useful for the class.

Proof Writing

Basic proof writing at the level of CS 2050/MATH 2106 is suggested, but extensive proof writing experience is not required. Most of the arguments in the class are more high-level than formal proof writing, but this varies by semester and professor.

Future Outlook

CS 3510 is the introductory course in the design and Analysis of Algorithms. The course is more math-based, and unlike most courses, it programs exclusively in pseudocode.

For Theory and Intelligence threads, CS 3510 is an important prerequisite for the theory courses for the two threads, namely CS 4510, and CS 4540.

Current Registration Info

In order to register for the course, you must register under a certain section as depicted by letters (A, B, C...).

Prerequisites

• CS 2050/2051/2106 (min. grade of C)
• CS 1332 (min. grade of C) or MATH 3012/3022 (min. grade of D)

Resources

• CS 3510: Design and Analysis of Algorithms (Fall 2017): click here
• CS 3510: Design and Analysis of Algorithms (Spring 2020, Vigoda): click here
• CS 3510: Design and Analysis of Algorithms (Spring 2020, Dovrolis): click here
• Oscar Details: click here