Editing 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 preceeded by [[CS 1332]], [[CS 2050]]/[[CS 2051]], and [[MATH 3012]]. It is succeeded by [[CS 4510]], [[CS 4540]], [[MATH 4150]], [[CS 6515]], and [[CS 4644|CS 4803/CS 4644]].

== Workload ==

== Topic List ==

# Basics of Pseudocode

# Recurrence Relations, Big-O, and the Master Theorem

# Divide-and-Conquer Algorithms

# Dynamic Programming

# Graph Algorithms

# Network Flow

# Optimization (with some semesters going over basic Linear Programming)

# NP-Completeness, Complexity, and Hardness,

# Approximation Algorithms

Textbooks used in this course in the past have included:

* ''Algorithms'' by Dasgupta, Papadimitriou, and Vazirani (used by Professor Vigoda, Spring 2020)<ref>https://www.cc.gatech.edu/~vigoda/3510/</ref>

* ''Algorithm Design'' by Kleinberg and Tardos (used by Professor Dovrolis, Spring 2020)<ref>https://www.cc.gatech.edu/~dovrolis/Courses/cs3510-S20.html</ref>

== 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]].

* CS 3510: Design and Analysis of Algorithms (Spring 2020, Vigoda): [https://www.cc.gatech.edu/~vigoda/3510/ click here]

* CS 3510: Design and Analysis of Algorithms (Spring 2020, Dovrolis): [https://www.cc.gatech.edu/~dovrolis/Courses/cs3510-S20.html click here]

[[Category:Courses|^CS^CS]]