Review of OOP concepts: classes, objects, instances of a class, instance members, static members, final classes,
final methods, final variables; inheritance, static initializers. Java interfaces, default methods and static methods in interfaces.
Java interfaces, default methods and static methods in interfaces,
instantiating anonymous classes, lambda expressions.
Total/Linear order on a set; natural order, the Comparable interface, implementing Comparable, Sorting through the
Comparable interface. Lambdas and Comparable Example .
Comparator interface; Analysis of Algorithms; Definition of computational problem, size of a problem, complexity of an algorithm,
Determining complexity empirically vs theoretically. Notion of a basic step for a problem, Worst case and average case complexity
Complexity analysis of simple sorting algorithms: Bubblesort and Insertion sort. Reasoning about correctness of algorithms by using program invariants.
Comparing complexity functions.
Fundamentals of recursion. Base cases, recursive calls, examples of recursion: linear search and binary search of arrays; complexity analysis of
linear search and binary search; Merge sort.
Complexity of Merge Sort; Quicksort, complexity of Quicksort.
Java Collection, List, and Set interfaces. Difference between Set and List. Contiguous and Linked allocation implementation of
lists; Tradeoffs between linked and contigous allocations.
- Hash sets and Tree sets.
Hashing, hash tables, equals and hashcode methods, characteristics of good hash functions. Balanced binary search trees as basis for
implementation of tree sets.
- Maps. The Map interface, the TreeMap and HashMap classes, common map operations get, put, containsKey, containsValue, forEach.
The three views of Maps as a set of Map.Entry objects, set of keys, and a collection of values. Applications of maps.
Backtracking algorithms. The N queens problem. Graphs and Digraphs. Adjacency matrices and adjacency lists used to represent graphs. Weighted graphs.
Graph traversal methods, Depth first search.
Recursive Depth First Search, Breadth First Search, applications of depth first search and breadth first search, how to recover paths
from one vertex to another when using DFS and BFS search. Dijsktra's shortest paths algorithm.