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!)