Algorithms
Sorting
Concepts
-
Stability
-
Locality
-
Design, implementation (code), and common optimizations
Basic sorting algorithms
-
Bubble sort
-
Insertion sort
-
Selection sort
-
Shell sort
-
Pay attention to the implementation
-
Recursion
-
Principle
-
Divide and conquer
-
-
Call stack management
-
Impact on space complexity
-
Recursive form of common algorithms (e.g. binary search)s
Data structures
-
Stacks
-
Queues
-
Lists
Know their:
-
ADT & primitives
-
Implementation (contiguous vs. dynamic memory)
-
When to use them (as exemplified by code examples discussed in lectures)
-
Time and space complexity
Analysis
-
Big-O/Omega/Theta notations
-
Definition
-
Growth hierarchy of common functions
-
Time/space complexity of the algorithms that we have learnt
-
-
Little-o/Omega notations
-
Summation formulas
