# Course: SOFTENG 250

Here is the first course I bothered to make an outline for: SOFTENG 250. The intention of this outline is to give "stopping points" on what you need to learn about for the purpose of this course. In other words, "this is what they taught".

Note that most pages contain a lot more information that is required by the course. You should browse the pages only with the intention of understanding the concept that is mentioned here.

- python - recursion - abstract data type - time complexity - asymtotic growth rate - \Omicron, \Omega, \Theta - amortized analysis (of time complexity) - array-based list (example) - its operations' implementation - its operatoins' running time - linked list - singly linked list - doubly linked list - sorted linked list - implementations - time complexities - stack - implementations - array-based - linked list - time complexities - use: parsing postfix expressions (Google) - queue - deque - double-ended queue - priority queue - unbounded priority queue - bounded priority queue - implementations - linear - array-based - linked - circular array-based (example) - heap (see below) - array-based - linked - fixed-size array of linked-lists (for BPQ) - time complexities - hasing - hash table - hash function - operations (add, remove etc.) - collision resolution - open addressing, a.k.a. close hashing - clustering - linear probing - simple linear probing (slot = (home + i) % SIZE) - modified linear probing (slot = (home + c * i) % SIZE) - quadratic probing (slot = (home + c ∗ i^2 ) % SIZE) - double hashing (slot = (home + hash2(key) ∗ i) % SIZE - closed addressing, a.k.a. open hashing, separate chaining - load factor & performance - typical hash functions (e.g. modulus) - tree - concepts: node, vertex, edge, arc, path, parent, child, ancestor, descendent, interior, leaf, width, height, depth, level - binary tree - implementation - linked - operations - full binary tree ("0 or 2") - perfect binary tree ("2^n - 1") - complete binary tree ("leafs on left") - traversal - level order - inorder, preorder, postorder - algorithms - recursive - use: arithmetic expressions - [in/pre/post]fix - parsing/formatting - heap - binary heap - conceptual algorithms for operations (add, remove etc.) - implementations - array-based - linked - use - priority queue - binary search tree - inorder traversal - conceptual algorithms for operations (add, remove etc.) - (conceptual) time compleities - AVL tree - conceptual algorithms - Huffman Encoding - sorting - comparison-based sort - stable sort - bubble sort - selection sort - insertion sort - merge sort - quicksort - in-place partition - implementation - performance - time complexities - sorted list - almost-sorted list - random list - reversed list - comparisons required - swaps required - choosing a sorting algorithm for a given scenario - graphs - vertices, edges, arcs - storage / representation - adjacency matrix - adjacency list - operations (add, remove etc.) - depth-first search - implementation - recursive - iterative (using a stack) - breadth-first search - implementation - iterative (using a queue) - iterative-deepening depth-first search - spanning forest - tree arc, forward arcs, back arcs, cross arcs (example) - recurrance relation - time complexity analysis of recursive code (example)