MASIS Class Prerequisites


Dear Applicant for the MASIS Programming Class,

For the class to serve its purpose best, I assume that you are familiar with (i.e. have already studied in university courses) the following fundamental concepts of computer science at the very minimum those highlighted in green:
Big-O notations also known as "the run time characteristic of an algorithm". Know about hash tables, heaps, binary trees, linked lists, depth-first search, recursion.
Graphs: There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); and you are familiar with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. If you get a chance, try to study up on fancier algorithms, such as Dijkstra and A*.
Abstract Machines and Complexity Classes: You should know about abstract computing machines and their relative power and/or equivalence: finite-state machines (non-deterministic, PDA), Turing machines (non-deterministic, multi-tape, etc.), and have a good mental picture of computational complexity classes.
Other Data Structures: You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman (Hamiltonian path) and the knapsack problem, and be able to recognize them when confronted with in real-life situations in disguise. Know what NP-complete means.
Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and know how it's implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.
Hash tables: Arguably the single most important data structure known to mankind. It'll be excellent if you already know their structure and how they work, but due to the importance of understanding them well I'm ready to make an exception for this one and explain the concept at an appropriate stage during our class.
Sorting: Know about various sorting algorithms and their pros & cons. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort – and you absolutely should know who invented merge sort as well as what else he invented or had significant contribution to – the more the better, but at the very minimum 7 more*). It'll be wonderful if you know about some non-comparison sorting algorithms (counting-sort, bucket-sort, radix sort). Although we'll talk about them in class, it's always a good idea to prepare yourself in advance.
Mathematics: Know about basic discrete math problems, including combinatorics (n-choose-k and their ilk) and their application in probability problems.



* 1. Arithmetic Logic Unit
2. Cellular Automata 3. Computer Virus 4. Game Theory 5. Monte Carlo method 6. Self-replication 7. Von Neumann architecture (I know, this one is a spoiler)