Exam 1 Info

1. The exam is closed book, notes, internet, etc.
2. The exam assumes you are able to program efficiently in C++
3. The exam assumes you have mastered principles of object orientation at the level of CPSC 231 or equivalent
4. The exam will be on paper.
   • Make sure that you are comfortable writing code by hand.
   • Be prepared to write blocks of code demonstrating the topics below
   • If you can’t think of code, write step-by-step instructions on how to solve the problem
   • Be able to determine aspects of or the output of certain blocks of code
5. There will be conceptual questions
   • You should always know the why and benefits of each topic listed below
   • Be prepared to provide short answers with detail on any of the topics below
6. Don’t leave problems blank!

Exam 1 Topics

1. C++ Basics
2. Theory
   1. Empirical vs asymptotic analysis
   2. Big O and Little O notation
   3. Big Omega and Little Omega notation
   4. Common complexity classes (e.g. - constant, logarithmic, linear, etc.)
   5. Ability to analyze code asymptotically
3. Arrays
   1. Pros and cons
   2. Layout in memory
4. Stacks
   1. LIFO
   2. Standard operations and their runtimes
   3. Array-based implementation
   4. List-based implementation
   5. Applications
5. Queues
   1. FIFO
   2. Standard operations and their runtimes
   3. Array-based implementation
   4. List-based implementation
   5. Applications
6. Linked Lists
   1. Singly vs doubly linked lists
   2. Dynamic sizing and allocation
   3. Standard operations and their runtimes
   4. Applications
   5. Advantages and disadvantages compared to fixed-size data structures
7. Priority Queues
   1. MinQueue vs MaxQueue
   2. Standard operations and their runtimes
   3. Applications