MT1 Info

Spring 2024 Canary: The following information HAS NOW been updated for Spring 2024!

Overview and Process

The test will be IN PERSON

• Time/Date: Thursday Feburary 22nd at 7 PM Pacific
  • The test will be set for 1 hour, 40 minutes
  • If you have USC approved accommodations, you must upload your accomodation information HERE by 11am on Thursday February 15th, otherwise you will not be able to use your accomodations.
• Location: depends on your lecture section and the letter your last name starts with
  • 11 AM section:
    • SLH 102 Last Name Starts with A - G
    • SLH 200 Last Name Starts with H - Z
  • 8 AM section:
    • SLH 100 Last Name Starts with A - K
    • SGM 101 Last Name Starts with L - Z
  • If you have OSAS accomodations you should schedule your exam at the OSAS offices on Thursday or Friday during OSAS hours
• The test will be taken on Gradescope and on paper. Be prepared with your laptop, and a pencil/pen.
• The exam is Closed book, Closed notes, Closed Internet (search/reference). You may use your mind, and blank scratch paper but nothing else. No referencing your labs, homeworks, etc.
• You are allowed 1 8.5x11 handwritten (front and back) cheatsheet. No printed cheat sheets. No single-sided, taped pages to form a double-sided sheet. You will be asked to turn your cheatsheet in when you are done with the exam (so if you want it for posterity, make a copy beforehand).

Topics and Style

The exam is a mix of short answer, multiple choice, and coding snippets. We will visually grade your code snipets and be fairly lenient with small syntax errors (e.g. a missing semicolon).

Unit 2a-2f - Review of CS 103 and CS 170

• Memory allocation (when to use dynamic allocation)
• Scope and lifetime of variables
• Pointers, references
• Classes (access modifiers), construction, destructions, initialization lists, use of const )
• Operator overloading
• Runtime (you’ll probably want your basic series formulas on your cheat sheet)
• Linked lists
• Copy Constructors / Assignment Operators / Rule of 3.

Unit 3 - Recursion

• Simple recursion
• Tracing of recursive functions
• Understanding order of execution (head vs. tail recursion)
• Linked list recursion

Unit 4 - ADTS

• List, Set, Map, Priority Queue, Queue, Stack
• When to use each given a problem description

Unit 5 - STL

• Iterators and their use
• std::map usage and runtime of its operations
• std::set usage and runtime of its operations

Unit 6 - Inheritance and Polymorphism

• Order or construction/destruction of parent/child classes
• Public, private, protected members
• Public, private, protected inheritance
• Inheritance vs. Composition relationships (is-a vs. has-a)
• virtual functions (static vs. dynamic binding)
• Abstract classes and pure virtual functions
• Tracing of polymorphic code execution
• Class hierarchy and design

Unit 7 - Queues and Stack

• Implementaiton options and their efficiency
• Applications of queues and stacks

Unit 9 - PQ and Heaps

• Tree representations and storage
• Full, complete, and balanced tree definitions
• Implementation of a priority queue
• Heap implementation and operations (push, pop, top) and runtime
• build-heap (make-heap) algorithm and runtime
• heap-sort
• Functors

Practice Materials

Sample Midterms

• Sample Midterm - Solutions
  • Copy construction, operator overloading are not a major focus of CS104 but were in previous years.
• Sample Midterm 2 (partial solutions)
  • Q1 Solution
  • Q2 and Q3 Solution
• Summer 2020 Midterm (Programming) (no solutions)
• Summer 2021 Midterm (Hybrid)
  • Skeleton Code
  • Solutions

Practice Quizzes

• ADTs - Solutions
• Streams and Simple Recursion - Solutions
• Runtime and Recursion - [No Solutions]
• Linked Lists and Recursion - Solutions
• Build-heap - Solutions