# Algorithms and Computation Theory

### Course Description

The Algorithms and Computation Theory course combines multiple semesters of high-level college courses into one intensive summer session designed to help acquaint students with important topics in Computer Science, whether it is in preparation for future studies, interviews and careers, competitive programming, CS research, or even just to develop a further interest in the field. This course covers a vast amount of must-know topics for all programmers in a friendly, close-knit, collaborative environment - a tentative syllabus is listed below. Students will not only gain knowledge in data structures, algorithms, and computation theory, they will also develop key programming, critical thinking, and communication skills that will help them succeed in any field.

Requirements: basic programming in any imperative/object-oriented programming language (C/C++, Java, Python, C#, etc.), algebra

Helpful but not required: single-variable calculus, LaTeX, experience in competitive programming

Textbook (helpful but not required): Algorithms 4th ed. by Robert Sedgewick & Kevin Wayne

### Syllabus

Below is a tentative, best-case scenario syllabus. Note that because some topics may require more time, not all topics may ultimately be covered

 Class Topic Unit 1: Data Structures & Algorithms 1 Programming review: Data types Methods/functions Classes & objects Input & output Random generators 2 Basic data types and algorithms: Array Resizable lists Linked lists: queue, stack Binary search 3 Algorithm analysis & Big-O 4 Sorting: Selection sort Insertion sort Shellsort Mergesort Quicksort Priority queues & heapsort 5 Advanced data types: Sets and maps (dictionaries) Hashing Trees Binary search tree 2-3 tree Red-black BST 6 Introduction to graphs: Undirected & directed graphs Breadth-first search Depth-first search Cycle detection Topological sort Kosaraju-Sharir algorithm 7 Graph algorithms: Minimum spanning trees: Prim, Kruskal Shortest path: Dijkstra, Bellman-Ford, A* 8* Strings: String sorting: LSD, MSD Tries Substring search: KMP Regular expressions Compression: Huffman, LZW 9* Miscellaneous algorithms: Union-find Convex hull Linear programming: Simplex B-trees Suffix trees Network flow: Ford-Fulkerson 10 General search problems with DFS 11, 12 Greedy algorithms, Dynamic programming: 1-dimensional Multi-dimensional Knapsack Unit 2: Computation Theory 13 Deterministic & nondeterministic finite automata 14 Regular languages, regular expressions, pumping lemma 15 Pushdown automata, context-free grammar 16, 17 Turing machines, decidability & reductions 18, 19 Algorithm classifications (P, NP, etc.) & reductions 20, 21 Review (buffer space in case more time is needed for above topics)

### Instructor

Adam Xu - Computer Science BS and Music, Sound, and Culture BA (current student) at Tufts University, Computer Science TA (for CS105) at Tufts University, Machine Learning researcher, classical music composer, USACO Platinum qualifier; taught AP Computer Science and tutored at Springlight for 3 years (as a highschooler!)