Department of Computer Science
North Central College
CSCE 210 Spring 2019 Reading Assignments & Course Log

Picture

CSCE 210 Spring 2019 Course Log

WEEK 1

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.

The Week in Review

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.

WEEK 2

Readings in the Class Text

Introduction
  1. 1.1 The need for efficiency
  2. 1.5 Algorithm correctness, time and space complexity

The Week in Review

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.

WEEK 3

Readings in the Class Text

  1. 1.3.3 Asymptotic Notation
  2. 1.2 Interfaces

The Week in Review

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.

WEEK 4

Readings in the Class Text

  1. 2.1 and 2.2 Array-based stacks
  2. 2.3 Array-based queues
  3. 2.4 Array-based deques

The Week in Review

Comparable and Comparator interfaces. Iterators. The Java Collection Framework hierarchy. List and Set operations. Java functional interfaces: Consumers, Suppliers, Functions, Operators, Predicates, and their variations. How to write lambda expressions.

WEEK 5

Readings in the Class Text

  1. 3.x Linked Lists

The Week in Review

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.

WEEK 6

Readings in the Class Text

  1. 3.x Linked Lists

The Week in Review

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

WEEK 7

Readings in the Class Text

  1. 5.x Hash tables
  2. 6.x Binary trees

The Week in Review

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.