ICS 23/CSE 23
Minimum Knowledge and Skills |
Elementary analysis of algorithms
- Determine asymptotic time usage of simple, short fragments of code.
[mastery]
- Determine the recurrence for time usage of a simple recursive
procedure. [mastery]
- For each of the data structures listed under mastery or proficiency
below, be able to describe the space usage and worst-case (and
average-case, where appropriate) time complexity, and explain how this
would affect the choice of an appropriate solution when more than one is
available. [mastery]
- Recognize the difference between O-, Omega-, and Theta-notation.
[proficiency]
- Solve problems involving O-, Omega-, and Theta-notation.
[proficiency]
Multi-dimensional arrays
- Understand how multi-dimensional arrays behave, as compared to
single-dimension arrays. [proficiency]
Lists
- Traverse generalized list structures. [proficiency]
- Use iterable objects and iterators. [proficiency]
- Understand amortized complexity bounds as the worst-case average
over a sequence of operations, as applied to ArrayList. [proficiency]
General trees
- Recognize and generate preorder, postorder, and level-order
traversals. [proficiency]
- Describe a tree using conventional terms (parent, child, ancestor,
descendent, node, leaf, root, height). [proficiency]
- Describe implementation using linked structures. [proficiency]
Binary trees
- Apply basic definitions and terminology about binary trees (e.g.,
parent, descendant, height). [mastery]
- Determine the pre-, in-, post-, and level-order traversals of a
given binary tree. [mastery]
- Implement recursive traversal of binary trees and simple
applications (such as recursive computation of height). [mastery]
Priority queues
- Describe the abstract behavior (for example, by describing changes
or results of a series of operations) of a priority queue, including
enqueue, dequeue, front/peek, and isempty operations. [mastery]
- Implement a priority queue using a linked list and using a heap.
[proficiency]
Searching
- Describe each of the search structures in this section, and analyze
the performance of construction, insertion, deletion, and searching, in
terms of O-notation. [mastery]
- Do binary search tree insertions, searches, and deletions on paper.
[mastery]
- Do insertions and deletions in AVL trees on paper. [proficiency]
- Derive recurrence for average-case behavior of binary search trees.
[exposure]
- Do insertions and deletions in skip lists on paper. [proficiency]
- Execute hashing with separate chaining on paper. [mastery]
- Implement a hash table using separate chaining. [proficiency]
- Evaluate choices of divisor in division hashing. [mastery]
- Understand when open addressing is an appropriate technique.
[exposure]
- Construct hash functions for strings and other objects.
[proficiency]
Graphs
- Apply definitions and terminology (e.g., directed vs. undirected
graphs, cycles, paths, components). [mastery]
- Understand the characteristics and relative advantages of adjacency
matrix vs. adjacency list representations. [mastery]
- Perform a depth-first search and breadth-first search on paper.
[mastery]
- Implement depth-first search and breadth-first search. [mastery]
- Find a topological ordering of a directed acyclic graph on paper.
[mastery]
- Describe an efficient algorithm for finding shortest paths and for
constructing minimum spanning trees. [proficiency]
Non-linear data structure implementation
- Implement a non-linear data structure (e.g., tree, binary search
tree, skip list). [proficiency]
Sorting
- Describe insertion sort, quicksort, mergesort, and heap sort.
[mastery]
- Analyze the running times of insertion sort, quicksort, mergesort,
and heap sort. [proficiency]
- Explain how quicksort and mergesort are applications of the
divide-and-conquer paradigm. [mastery]
- Use a decision tree to show the lower bound on sorting using direct
key comparisons. [proficiency]
- Execute bucket sort and radix sort on paper, and explain why their
linear running time does not violate the lower bound on sorting using
direct key comparisons. [proficiency]
Data structures and algorithms for external memory
- Describe how the properties of external memory affect algorithm
design. [mastery]
- Describe the performance of construction, insertion, searching, and
deletion in B-trees. [proficiency]
- Do insertion and searching in B-trees on paper. [proficiency]
- Describe, in general terms, how to delete keys from a B-tree.
[exposure]
- Describe external memory mergesort. [proficiency]
Memory management
- Understand the main principles of memory management, including
allocation and deallocation, garbage collection, fragmentation,
compaction, and coalescing. [proficiency]
Union-Find
- Describe a data structure for Union-Find and be able to execute
Union and Find operations on paper for that structure. [proficiency]
|