#### Readings in the Class Text

Our discussion of recursion is largely review, and no no section of our text deals with the fundamentals of recursion. Please consult whatever text book you used for the prerequisite course.

Department of Computer Science

North Central College

CSCE 210 Spring 2019 Reading Assignments & Course Log

Our discussion of recursion is largely review, and no no section of our text deals with the fundamentals of recursion. Please consult whatever text book you used for the prerequisite course.

The first week focused on recursion: determine how to break up a problem into subproblems of the same type, determine the parameters for the recursive calls, and determine what your base cases are.

We looked at different recursive approaches to summing an array, the towers of hanoi, and recursive binary search of a sorted array; Recursive divide and conquer algorithms.

- 1.1 The need for efficiency
- 1.5 Algorithm correctness, time and space complexity

Quicksort. The partition algorithm. Mergesort and the merge algorithms. Efficiency and complexity of algorithms: computational problem, input size, basic step.

Laboratory 1 on recursion. Quiz 1 on recursion. Solutions to the quiz are posted here.

- 1.3.3 Asymptotic Notation
- 1.2 Interfaces

Worst case and average case complexity functions for an algorithm. Determining the complexity of Selection sort. Big O, Big Omega, and Big Theta.

Interfaces, ADTs, data types, equals(), toString(), and hashCode() methods and how to write them. Intro to lists and sets.

- 2.1 and 2.2 Array-based stacks
- 2.3 Array-based queues
- 2.4 Array-based deques

Comparable

- 3.x Linked Lists

Iterators and Iterable. How to implement an iterator for a collection. Iterable.forEach(action) method vs Iterator.forEachRemaining(action) method. Implementation of singly-linked and doubly-linked lists, Use of lists for recursive and non-recursive computation of lists of subsets and lists of permutations of sets.

- 3.x Linked Lists

Implementing singly and doubly linked lists. Use of class invariants and program invariants in program development and verification.

- 5.x Hash tables
- 6.x Binary trees

Hash tables, hash table buckets, Why hash tables support O(1) add, remove, search on average, Binary trees, preorder, postorder, and inorder traversal, binary search tree operations, recursive add operation to a binary search tree. Iterative add, remove, remove largest and smallest, and other binary (search) tree operations.