CSC 210 Data Structures and Algorithms Course Log

Winter 2018

Week 1

- 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, functional 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 .

Week 2

- 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 of algorithms.

Week 3

- Complexity analysis of simple sorting algorithms: Bubblesort and Insertion sort. Reasoning about correctness of algorithms by using program invariants. Comparing complexity functions.

Week 4

- 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.

Week 5

- Review of JavaFx.

Week 6

- Java Collection, List, and Set interfaces. Difference between Set and List. Contiguous and Linked allocation implementation of lists; Tradeoffs between linked and contigous allocations.

Week 7

- 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.

Week 8

- 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.

Week 9

- 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.

Week 10

- 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.