COSC 320 - Final Study Guide

Study Material  Chapters 3 (3.3, 3.6-3.7), 10-11, 12, 14(14.1-14.3), 16, 15(15.1), Labs, and programming assignments

Chapter 16:

Graph Terminology (path, cycle, subgraph, connected, complete, directed, in/out degree)
Directed cyclic graph (strong connected, weekly connected)
Representation of Graphs (adjacency matrix, adjacent set)
Graph traversal algorithms

    Breadth-First Visit (Search)
    Depth-First Visit (Search)
Graph Traversal Applications

    Acyclic graphs

    Topological sort

    Strongly connected component

Graph-Minimization Algorithms

    Shortest-Path Algorithm

    Dijkstra’s Minimum-Path Algorithm

    Minimum-Spanning Tree Algorithms: Prim algorithm, Kruskal’s algorithm

Chapter 15:

Sorting algorithms ( insertion sort, selection sort, merge sort, quick sort)

Factionary Knapsack and binary Knapsack problems

Optional Topics:

Stable matching problem and GS algorithm

Test Format

Close book, close notes, and no calculators needed.

There are total about10 problems. Each problem may contain multiple questions

The test questions are similar to the questions given in homework, text review questions,  class discussion problems, labs, and programming/project assignments.