Final Topic Review

The final exam is comprehensive. This outline focuses on contents after midterm II and should be used together with the past midterm reviews.

Materials to prepare (sorted by the order of importance)

1. Practice exam

2. Past midterm exams

3. Past projects (know what you did wrong)

4. This outline and outlines for past exams

5. Course notes website

6. Zybook content and activities

Hint and tips for preparation

• All contents covered in the semester will be tested

• Self-test using this document to see what concepts are challenging to you.

• Course notes document is the main resource for tips, pitfalls. High priority in midterm preparation.

• The past midterm exams are important materials to prepare.

• Re-do all participation activities and challenge activities in zyBook

• Practice your ability to finish the patterns listed here from scratch without editor or IDE

Tree

• Concepts

  • definition

    • graph theory: connected undirected graph

    • computer science: root and sub-trees

  • recursive definition

  • terms: tree, sub-tree, node, root, leaf, internal node, edge, parent, child, sibling, ancestor, descendant, height, path, ordered

• Binary tree

  • definition

  • ordered, degree 2

  • full tree, complete tree, perfect tree

• Binary search tree

  • definition

  • applications

  • behaviors (know the big O complexity)

    • search

    • insert

    • remove/delete

    • in-order traversal

  • implementation

    • node class

    • BST class

    • implementation of behaviors

Heap

• Logically a complete binary tree, physically an array

• Min Heap and Max Heap

• behaviors

  • insert - add to last and percolate up

  • remove

  • percolate up/down

• Make a heap

  • heapify an array :math`Theta(n)`

  • insert to an empty heap one by one \(\Theta(n \log n)\)

• Heap sort

  • heapify first

  • repeat

    • take the root

    • put into the sorted region

    • percolate down

• Priority queue ADT

  • not really a queue

Backtracking and Exhaustive Algorithms

Both algorithms search in a tree problem space for solutions.

Exhaustive Algorithms

• Exhaustive searches all possible solutions

• Always generate final solutions and check, never check partial solutions

• Implementation

  • Recursive

• Examples

  • All permutations

  • All combinations

Backtracking

• Backtracking searches tree problem spaces with pruning (reject partial solutions)

• Similar/identical to DFS

• Implementation

  • Recursive

  • iterative - stack

• Applications

  • N queens - reject when attacking each other

  • Maze - reject when hitting the dead end

  • Sudoku - reject when violating the rule

• Recursive implementation

Graph

• Nodes/Vertices and Edges/Arcs

• Types: directed/undirected, weighed/unweighed, cyclic/acyclic, complete/dense/sparse, connected/unconnected

• Terms: too many to list, check course note

• Representations: adjacency list, adjacency matrix, pro and con

• Traversal

  • Depth-first search (DFS)

  • Breadth-first search (BFS)

• Shortest path problem

  • BFS for unweighted

  • Dijkstra’s for weighed/unweighed

    • select minimal (priority queue or other)

Patterns

Must be able to reproduce in an exam environment.

• Write class declarations of ADTs (Priority Queue), may ask templated version

• Write simple recursive exhaustive/backtracking algorithm

• Mimic a graph traversal given a graph as diagram, adjacency list or matrix

• Write typical algorithms of BST (search, insert, traversal)

• Write typical algorithms of Heap (insert, remove, heapify, percolate up/down, heap sort)

• Write typical algorithms of Graph (BFS, DFS)

• Understand how algorithm works (Dijkstra)