# CSCI 103 Fall 2017: Introduction to Programming

## Final Exam Information

When: Tuesday May 9th, 4:30-6:30pm

Where:

• SGM 101: 9am section
• SGM 123: 11am and 2pm section
• PHE223: DSP students

### Format

• You will be allowed to bring a two-sided cheatsheet (8.5"x11") written or printed is fine.
• Other than the cheatsheet being two-sided, the format is identical to the written midterm. No calculators, computers, or textbooks are allowed.

### Practice

• Final exam from Fall 2014 here and its solutions.
• Final exam from Spring 2015 here and its solutions.
• Practice questions created in Fall 2014 here.

Caveats:

• Fall 2014's exams had a significant on-paper coding component, which will not be done this semester. So you can ignore those last couple of questions. Also bit-wise operations was covered in past semesters but is no longer something covered in CS 103.
• The topics on those exams will not be exactly the same as the topics this semester, see below.

### Topics

Anything that was covered in lecture, homework, labs, or the programming assignments can come up on the final exam. Material from the first half of the course will come up again because the concepts in the first half of the course are fundamental, but the focus will be to gauge your familiarity and understanding of the concepts from the second half of the course.

Therefore, you should anticipate that there will probably be at least one question focusing on each of the following topics:

• object-oriented programming
• recursion
• linked lists (and dynamic memory)
• algorithms and performance
• streams (file streams and/or string streams)

To help you study and to specifically include/exclude some topics, we provide a detailed list below. Anything from the midterm topics list can come up again, so the below information only covers topics not from that list.

Chapter 2:

• C++ strings
• NOT included: output manipulators

Chapter 3:

• NOT included: switch

Chapter 4:

• NOT included: do...while

Chapter 5:

• C++ reference parameters (pass-by-reference)
• recursion (see Chapter 11 below)

Chapter 6:

• vectors

Chapter 7:

• structs
• dynamic allocation and deallocation
• interpreting valgrind messages

Chapter 8:

• input and output file streams
• input and output string streams
• NOT included: random access, unget(), output manipulators, page 359 Table 1, tab characters, clear(), ignore()
• you do NOT need to memorize any ASCII codes to correctly answer the final questions

Chapter 9:

• object-oriented programming:
• declaring, defining, public/private, . and -> operators
• declaring, defining and calling member functions, constructors (and constructor overloading), destructors
• value semantics of passing object as argument, in assignment, or as return value
• NOT initializer lists, compilation, this pointer

Chapter 10:

• NOT this chapter (inheritance)

Chapter 11:

• recursion
• helper functions
• tracing the call tree
• NOT games and memoization

Chapter 12:

• binary search / comparison with linear search
• NOT sorting

Chapter 13:

• linked lists: NULL, helper class, doubly linked lists, head/tail pointers
• efficiency of list, array, and vector operations
• NOT stacks, queues, deques

Chapter 14:

• NOT this chapter (sets, maps, priority queues)

Other:

• efficiency (scattered throughout book):
• difference between a constant-time operation and a linear-time one (e.g. add to front of linked list versus vector)
• difference between binary search (logarithmic time) and linear search (linear time)
• why recursion can generate exponential-time algorithms
• reasoning about the efficiency of a small program (<10 lines)
• extrapolating program performance from measurements (doubling method)
• NOT included: iterators

APIs that you should be familiar with (if anything not from this list is on exam, it will be defined in exam text):

• string: everything from the class notes except NOT find
• vector: everything from vector_eg example except NOT iterators
• ifstream/ofstream/stringstream:
constructing, inserting/extracting (i.e. <</>>),
fstream::close()istream::get()istream::fail(),
ostringstream::str()
• getline(istream&, string&)