Exam 1

Exam 1 is designed to explore the foundational concepts of C++ and Theory background as well as the material coverd through lecture 14 (2/26/2021). It is scheduled in your lecture time with conflicts availble for any student who needs them.

Exam 1 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.

There is a practice exam availibe on PrairieLearn.

Topics Covered

Topics from lecture:

• Classes in C++
  • Public members functions
  • Private helper functions
  • Private variables
  • Constructors
  • Automatic default constructor
  • Custom constructors (default and non-default)
  • Copy constructor
  • Automatic copy constructor
  • Custom copy constructor
• Namespaces in C++
  • Creating a class that is part of a namespace (eg: Cube is part of the cs225 namespace)
  • Using a class from a namespace (eg: cs225::Cube)
  • Purpose and usefulness of namespaces
• Variables
  • Four properties: name, type, location (in memory), and value
  • Primitive vs. user-defined
• Memory
  • Indirection in C++:
    • Reference variables
    • Pointers
    • Differences and trade-offs between each type
  • Stack memory
  • Heap memory
• Functions: Calling and Returning
  • Pass by value, by reference, and by pointer
• Array List
  • Operation insertAtFront, including running time, resize strategies, and proofs
  • Operation insertAtIndex, including running time, on both a sorted and unsorted list
  • Operation removeAtIndex, including running time, on both a sorted and unsorted list
  • Operation insertAfterElement, including running time, on both a sorted and unsorted list
  • Operation removeAfterElement, including running time, on both a sorted and unsorted list
  • Operation findIndex, including running time, on both a sorted and unsorted list
  • Operation findData, including running time, on both a sorted and unsorted list
• Linked List
  • Operation insertAtFront, including running time and insertion strategies
  • Operation insertAtIndex, including running time, on both a sorted and unsorted list
  • Operation removeAtIndex, including running time, on both a sorted and unsorted list
  • Operation insertAfterElement, including running time, on both a sorted and unsorted list
  • Operation removeAfterElement, including running time, on both a sorted and unsorted list
  • Operation findIndex, including running time, on both a sorted and unsorted list
  • Operation findData, including running time, on both a sorted and unsorted list
• Iterators
  • Operations *, !=, and ++.
  • Applications of iterators
  • Utility of iterators
• Trees
  • Basic tree terminology (CS 173)
  • Tree Property: Binary
  • Tree Property: Height
  • Tree Property: Full
  • Tree Property: Perfect
  • Tree Property: Complete (as defined in data structures)
• Mathematical foundations:
  • Be able to give a closed form solution to a recurence relation.
    • Reference: Chapter 12: Recursive Definition in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)
  • Be able to indicate the big-O running time of common algorithms (eg: binary search, merge sort, etc).
    • Reference: Chapter 14: Big-O in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)
  • Be able to identify the relationship between two sets or functions (eg: reflexive, symmetric, transitive, ordered, equivalence, onto, one-to-one, etc)
    • Reference: Chapters 6-8 in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)
  • Be able to understand basic graph terminology.
    • Reference: Chapters 9 in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)
  • Be able familar with Trees
    • Reference: Chapters 13 in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)
  • Be able to understand a standard proof and proof by induction.
    • Reference: Chapters 3 and 11 in “Building Blocks for Theoretical Computer Science” by Prof. Margaret Fleck (CS 173)

Assignments referenced:

• lab_intro, lab_debug, lab_memory
• mp_intro, mp_stickers

Points:100

Registration: Friday, February 19

Start: Friday, March 05

End: Saturday, March 06