ICS 22/CSE 22
Minimum Knowledge and Skills |
Algorithm analysis
- Derive a polynomial describing the execution time of simple
iterative code with nested loops. [proficiency]
- ('Big') O-notation:
- Recognize its use in providing a machine-, language-, and
problem-size-independent description of an algorithm's performance.
[mastery]
- Recognize and distinguish the growth rate of common function
classes, including exponential, polynomial, n-squared, n log n, linear,
log n, and constant. [mastery]
- Recognize its limitations (e.g., not distinguishing between
constant-factor differences in performance, not applying when n is
small). [mastery]
- Recognize informally the O-notation for common operations on the
classic data structures described below. [mastery]
- Given a polynomial, state its O-notation. [mastery]
- Recognize informally the O-notation of a simple recursive algorithm
(e.g., using a recursion trace diagram). [proficiency]
- Reason about the performance of functions and programs, evaluating
the significance of proposed optimizations and trade-offs (e.g.,
constant-time improvements are less important, for large enough n, than
O-notation improvements; frequently-executed methods are better
candidates for optimization than rarely-executed routines).
[proficiency]
Classic data structures
- Describe the abstract behavior (e.g., by describing changes or
results of a series of operations) of:
- Stack (push, pop, top, isempty) [mastery]
- Queue (enqueue, dequeue, front, isempty) [mastery]
- Map indexed by a key (insert, search/member, remove, isempty),
distinguishing between sorted and unsorted maps [mastery]
- Recognize operations inconsistent with the abstract behavior of a
stack, queue, or map (e.g., direct access to the third item in a stack).
[mastery]
- Given a real-world problem for whose solution one of the above data
structures serves as an appropriate model, identify which of those data
structures is most appropriate. [proficiency]
Conventional algorithms
- Recognize, describe (in terms of behavior and O-notation), and
implement the following conventional algorithms.
- Linear and binary search [mastery]
- Opening, reading from, writing to, closing, and handling errors
associated with sequential text files [mastery]
- For an ArrayList and for a singly-linked list:
- Traversing and applying an operation to each element of the list
[mastery]
- Moving within, adding items to, and deleting items from the list
[mastery]
Implementation
- Understand the distinction between single-dimension arrays and
ArrayLists, and be able to make the appropriate choice about which to
use in an implementation (e.g., using arrays in non-list use cases, such
as arrays of boolean flags). [proficiency]
- Understand when it is appropriate to use array- and ArrayList-based
implementations of stacks, queues, and maps. [proficiency]
- Implement a singly-linked list with an iterator. [mastery]
- Implement dynamically-allocated linked implementations of stacks,
queues, maps (both sorted and unsorted), in a simple linear fashion
(i.e., as linked lists). [proficiency]
- Identify the costs and advantages of these coding techniques for
dynamically allocated, linked data structures: single linking and
trailing pointers, double linking, header and trailer nodes vs. head and
tail pointers, and circular vs. non-circular linking. [proficiency]
- Recognize the performance implications, both in time and storage, of
the alternative implementations covered above. [proficiency]
- Recognize trade-off situations where using more space saves
execution time, or vice versa. [proficiency]
Recursion
- Recognize and implement recursive algorithms of these three types:
tail recursive, linear (non-tail recursive) with a return value, and
multiple recursive calls. [proficiency]
Sorting
- Understand the general concept of sorting, as it applies not only to
numbers, but also to arbitrary comparable objects. [mastery]
Object-oriented programming
- Navigate documentation for a class hierarchy to identify the
appropriate class and methods for a task. [proficiency]
- Design object-oriented solutions to problems using the data
structures described above. [proficiency]
- Write and understand a program containing multiple classes arranged
in an inheritance hierarchy, as well as code that uses the inheritance
hierarchy polymorphically. [proficiency]
- Recognize situations where inheritance is a preferable design
strategy to containment/composition, and vice versa. [proficiency]
- Recognize that design patterns offer well-understood solutions to
commonly-occurring object-oriented design problems. [exposure]
- Understand the role and appropriate use of interfaces in Java.
[proficiency]
Java programming
- Write code to read and write sequential text from external files.
[proficiency]
- Write code using standard exceptions appropriately, including the
exceptions that arise from dealing with files. [mastery]
- Write programmatic unit tests that verify that portions of a program
behave as specified, both from scratch and using a testing framework
(e.g., JUnit). [proficiency]
- Trace the flow of control through code that raises exceptions and
handles them via catch clauses. [proficiency]
- Recognize the importance of resource deallocation, including the
role of Java's automatic garbage collector, and resources (such as
files) that require explicit deallocation in Java. [exposure]
- Write static methods. [mastery]
Alternative approaches to program design
- Functional programming:
- Describe the differences between the functional programming paradigm
and object-oriented and imperative programming. [proficiency]
- Recognize situations where functional programming could be an
advantageous approach. [exposure]
|