Introduction to Algorithms and Data Structures II Course

What should be known before taking this course

The following are covered in the prerequisite courses at UWF. If any of these are not familiar, please review them before taking this course or when needed. I will revisit some of them in this course as needed.

  • Development environment setup

    • Local

      • Linux native

      • macOS native

      • Windows system for Linux (WSL)

    • Remote

      • SSH server (Linux)

  • Basic programming skills in C++

    • Variables and types

    • Control flow

    • Functions

    • Pointers and references

    • Classes and objects

    • Templates

    • Standard library

  • Basic knowledge of of computational complexity

    • Big-O notation

    • Big-Omega notation

    • Big-Theta notation

  • Basic knowledge of data structures and abstract data types

    • Array

    • Linked list

    • Stack ADT

    • Queue ADT

    • Heap

    • Priority queue ADT

    • Tree

      • Binary tree

      • Binary search tree

    • Hash table

    • Map ADT

    • Set ADT

    • Graph

  • Knowledge of algorithms

    • Sorting

      • Insertion sort

      • Selection sort

      • Merge sort

      • Quick sort

      • Heap sort

      • Radix sort

    • Searching

      • Linear search

      • Binary search

      • Search in a search tree

      • Search in a hash table

    • Graph

      • Depth-first search

      • Breadth-first search

      • Single source shortest path: Dijkstra’s algorithm

    • Brute force

    • Backtracking

  • Basic knowledge of mathematics

    • Computational complexity

  • Version control system (git) and Classroom 50

What will be covered in this course

  • Mathematical foundations

    • Basics

      • Exponent

      • Logarithm

      • Modular arithmetic

      • Proof methods

    • Recurrence relations and their solutions

    • Combinatorics and counting

      • Arrangement

      • Selection

      • Distribution

      • Addition principle

      • Multiplication principle

      • Inclusion-exclusion principle

      • Division principle

      • Pigeonhole principle

    • Probabilistic analysis

      • Random variables

      • Expectation

      • Events

      • Classic probability

  • Type of problems

    • Search problem (find one qualifying solution)

    • Enumeration problem (find all qualifying solutions)

    • Optimization problem (find the best solution under an objective)

    • Decision problem (answer yes or no)

    • Counting problem (report how many qualifying solutions)

    These are requested output goals, not algorithmic paradigms. A paradigm is chosen based on the structure of the problem and the required output; no paradigm is limited to only one goal. Enumerating all solutions can answer search, decision, counting, and optimization questions, but may do more work than a direct algorithm.

  • Algorithmic classification

    • Brute force paradigm

    • Backtracking paradigm

    • Greedy paradigm

    • Divide-and-conquer paradigm

    • Dynamic programming paradigm

    • Evolutionary paradigm

      • Genetic algorithm

    • Exact and approximate algorithms

    • Randomized algorithms

      • Monte Carlo algorithm

    • Heuristic/metaheuristic algorithms

  • Core data structures and related algorithms

    • Self-balancing trees

      • AVL tree

      • B-tree

    • Graph

      • Minimal spanning tree

      • Shortest path

  • Classic problems and solutions

    • Traveling salesman problem

    • Bin packing problem

    • Huffman coding

    • Max sum subarray problem

    • Chain matrix multiplication

    • Longest common subsequence

    • Minimal spanning tree

    • Shortest path