Things to know for exam

Sorts

          Bubble sort Insertion sort        Selection sort  - O(n2)

          Merge sort   Radix sort   Quick sort     O(n log2 n)

 

Big O

          Sorts (memorize)

          Code

 

Data structures

          Lists

Array

                   Linked structures

          Queues

                   Arrays

                   Linked structures

          Stacks

                   Arrays

                   Linked structures

 

          Graphs         - nodes, edges, directed, undirected

                   Trees – binary trees, binary search trees

                             heap

                                      Arrays

                                      Linked structures

          Hash tables -  array -  collisions -  collision resolution (chaining, linear probing), load factor

 

Searching

          Linear searches

          Binary searches

          Traversals of trees  - recursively

                   Pre-order

                   In-order

                   Post-order

          Depth first  -  stacks

          Breadth first - queues

 

Ada –

 

Recursion     - needs base or stopping case, recursively move towards base case

                   When recursive step is last step in procedure it is tail recursion