CSCI 315

Appearance

Final Exam Study Guide ​

See the syllabus for the deadline.

NOTE

In-person students must take the exam in class during the last class period and the official exam time.

This exam shall have 2 sections, each worth 50%:

  1. a GitHub/Auto-Grader with multiple problems and

  2. a Blackboard section.

Both sections will be timed and cannot be paused. Blackboard will allow you to reconnect if you lose your connection. Each Auto-Graded problem will have a separate time limit, as stated in its instructions.

The final will consist of programming problems and stepping through the iterations of algorithms (showing the state at each step). Big O will also be a significant topic during your final. Your Auto-Grader grade is based on the percentage of passing test cases.

Included Topics ​

  1. Data Structures:

    • Arrays

    • Linked List (singly- and doubly-linked)

    • Vectors, Stack, Queue, Circular Buffer

    • Trees:

      • Binary Search Tree (Ordered Sets, Ordered Maps)
      • Heaps
      • Priority Queues
      • B-trees
      • Quadtrees

    • Hash Tables implemented via Chaining and Linear Probing: (a.k.a., Unordered Set, Unordered Map,)

    • Graphs (Adjacency List, Adjacency Matrix)

      • Types: Directed, Undirected, Simple (no loops or parallel edges), and Strongly-Connected (all vertices are connected)

  2. Algorithms:

    • Sorting: Bubble, Selection, Insertion, Quick, Merge, Heap

    • Searching: Linear, Binary, Depth-first search (DFS), Breadth-first search (BFS)

    • Traversing: preorder, inorder, postorder

    • Graphs: DFS, BFS, Dijkstra's Shortest Path, Prim's Minimum Spanning Tree

    • Deleting and inserting into each data structure

    • Copy constructor for each data structure

  3. Other:

    • Compare/contrast, with space complexity and runtime complexity in Big-O notation.

    • Know what each data structure does and how it does it.

    • Recursive and iterative solutions to the above algorithms

    • Function pointers and function objects

    • Memory Allocation: Dynamic/Heap, Stack, and Static memory

    • Templates

    • Operator Overloading

Example Question ​

You may reference the Midterm Study Guide for example questions. The format will be very similar.

I have provided an example problem in the exam2-0/ directory that you can try before starting the real exam problems. Use it to understand the procedure before you focus on problem-solving when timed.

Last updated: