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

      • Mac OS 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 GitHub classroom

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

    • Enumeration problem (find all solutions)

    • Search problem (find a solution)

    • Optimization problem (find the best solution)

  • 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