CS310 - Section 1 — General Programming & Java

Q: When Java executes Car c = new Car(); what’s stored in c, and what actually gets created in memory?

A: new Car() allocates a Car object on the heap; the variable c stores a reference (pointer) to that object (not the object itself). If you later do Car d = c;, both c and d hold the same reference (aliasing the same heap object).

Q: What do these Java keywords mean: private, protected, static, final, interface, abstract?

A:

• private: member is accessible only inside its own class.

• protected: accessible in the same package and by subclasses.

• static: member belongs to the class, not to instances; shared by all objects.

• final: cannot be changed/overridden (variable’s value can’t be reassigned; method can’t be overridden; class can’t be subclassed).

• interface: specifies a contract (methods to implement) focusing on the what, not the how.

• abstract: a class that cannot be instantiated and may include abstract methods; use when several similar subclasses share fields/behavior.

Q: What’s the Big-O of concatenating n strings using String s = s + t; in a loop, and how can we improve it?

A: With immutable String, each concatenation copies existing characters ⇒ O(total length) per step, yielding O(n²) overall for similar-sized strings. Use StringBuilder (or StringBuffer) and call append in a loop to achieve O(n) over the total characters.

Q: What are generic classes and why are they important in data structures?

A: Generics let you reuse one data-structure implementation for many element types with type safety (compile-time checks, no unchecked casts). They’re motivated by OOP reusability goals and often require bounded type parameters (e.g., T extends Comparable<T>) when operations need capabilities like compareTo.

Q: Define recursion and its key parts; mention readability, efficiency, and how it relates to iteration.

A: Recursion is when a method calls itself. Every recursive solution needs:

• Base case — when to stop.

• Recursive case — how to reduce the problem and call yourself again.
  Readability: often clearer for self-similar problems (trees, divide-and-conquer). Efficiency: extra call-stack overhead; some recursive solutions mirror iterative ones (loops) and can be rewritten to avoid recursion if needed.

Q: How should you approach “understand what an iterative function is doing”?

A: Track loop variables and invariants: identify what changes each iteration (counters, indices, accumulators) and what remains true (e.g., “sum holds the total of processed items”). Relate the loop’s stop condition to problem size n. (Your slides emphasize modeling code as T(n) functions and reasoning about loops.)

Q: How can you walk backward in a singly linked list using recursion or a stack, and why does recursion work without building your own stack?

A:

• With a stack: traverse forward pushing nodes; then pop to visit nodes in reverse.

• With recursion: recurse to the end, then process nodes on the way back (post-order), which visits them in reverse.
  Recursion works because the call stack (managed by the runtime) is your stack.