Exam 1

Exam 1 is designed to explore the foundational concepts of C++ and Theory background as well as the material coverd through lecture 13. For on campus students it is in the CBTF for off campus students this is still being resolved.

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: Thursday, September 16

Start: Tuesday, September 28

End: Thursday, September 30