CSCI 260 Fall 2013: final preparation

The final exam will be held in the gym, date and time TBA

Here is the 2010 final exam and one older final

A review will be held in the final lecture of the semester.
The final is three hours, 8 questions, 10 marks each
The final is closed books and no calculators, but you are permitted one sheet of notes: 8.5x11", double-sided.
The final can cover any material covered in the course, with extra emphasis on the material not covered by the midterm.
The material covered includes all lab exercises, the online lecture notes, and the material discussed in lectures.
Question styles
Questions will generally fall into one of these styles:
- Outline an algorithm that does ... and justify its validity
  (might specify special conditions, knowledge about input data, or implementation requirements)
- Describe the running time of algorithm ... and justify your answer
- Discuss the appropriateness (or pros/cons, advantages/disadvantages) of ...
- Under what circumstances would/should you use ... instead of ... and justify your answer
- Summarize the important differences between ... and ...
- Is the following possible ... and why
- Describe how the following algorithm ... achieves ...
- Modify/fix (or explain how to modify/fix) the following algorithm to do ...
- What does the following algorithm ... do with the following input ...
Topics outline
- Background / C++
  I assume you are familiar with allocating/deallocating dynamic data structures in C++, using classes, structs, pointers, recursion, etc.
  The final exam does not explicitly require you to code in C++
- Complexity
  - understand (and be able to explain) the purpose of using order notation when reviewing algorithms
  - understand (and be able to explain) the need for defining input size and elementary operations
  - be able to identify the complexity of basic code/algorithm constructs
  - know the heirarchy of common orders (constant, log, linear, etc)
  - be able to prove/disprove hypotheses using the following proof techniques:
    - constructive proofs
    - proof by contradiction
    - inductive proofs
    (The hypotheses are likely to cover things such as prove/disprove that a particular function is/is not in a given order, prove/disprove that a particular order is/is not a subset of another order, etc - similar in style to the assignment 1 exercises.)
- Lists
  - be able to create and use a basic doubly-linked list class, including maintaining the list in sorted or unsorted formats
  - understand (and be able to explain) the efficiency issues associated with searching and maintaining sorted versus unsorted lists
  - understand and be able to work with algorithms for merging and sorting linked lists
- Stacks (assumed review)
  - basic operations and complexity: top, pop, push, isempty
  - conventional array and pointer implementations
- Queues (assumed review)
  - basic operations and complexity: enqueue, dequeue, isempty
  - conventional array and pointer implementations
- Self organizing lists
  - understand (and be able to explain) the rationale for self-organizing lists, where the organization is done based on most-frequent use or most-recent use
  - understand (and be able to explain) the implications for efficiency of searches, inserts, removes, etc and the relationship to the distribution of requests
  - be able to create and use a class for self organizing lists, including the methods discussed in lectures
- Caches
  - understand (and be able to explain) the rationale for using caches, where replacement within the cache is done based on least-frequent use or least-recent use
  - understand (and be able to explain) the implications for efficiency of searches, inserts, removes, etc and the relationship to the distribution of requests and the probability of finding an item in the cache
  - be able to add caching techniques to lists or skiplists
- Sparse tables
  - understand (and be able to explain) the rationale for using sparse tables
  - understand (and be able to explain) the implications for efficiency of searches, inserts, removes, etc and the relationship to the sparseness of the table
  - be able to create and use a class for sparse tables, including the methods discussed in lectures
- Binary search trees
  - basic pointer-based implementation
  - array based implementation (with root in position 0 and appropriate computations to determine positions of parent, leftchild, rightchild)
  - inserts, removes, searches
  - recursive traversals (e.g. prints)
  - optimal versus worst case tree structure, and impact on operations
- AVL trees
  - implementations as an extension to binary search trees
  - inserts, removes, searches, traversals, and efficiency
  - left and right rotations, and tree balancing by performing single or double rotations
- Hash tables
  - implementation and applications
  - relevance to associative arrays
  - hash functions
  - collision resolution
  - hash sort and radix sort
  POST-MIDTERM MATERIAL (likely to be emphasized?)
- Sets
  - basic operations and complexity: intersection, union, difference, isin
  - array and linked list styles of implementation, and where each is/isn't appropriate
- B-trees
  - typical operations and complexity: insert, remove, search, split, join
  - emphasis on use of internal 'seperation keys' and use of leaf nodes to hold actual data elements
  - emphasis on use of split and join to maintain balance
  - typical array and pointer implementations
- Heaps
  - implementations as a modified form of binary tree
  - suitability for sorting and priority queues
  - unsuitability for searching
  - insert, remove, moveup, movedown operations
  - heapsort for in-place sorting of arrays
- Graphs
  - adjacency matrix and adjacency list implementations (implementation details, efficiency issues)
  - insert, remove operations for nodes and edges
  - breadth-first and depth-first searches using queues and stacks
  - minimal spanning tree computation
  - shortest path computations (Dijkstra's algorithm, Floyd's algorithm)
  - maximum flow computations, relationship to minimum cutset
  - graph colouring algorithms
- String matching
  - basic string matching/searching algorithm
  - use of finite state machines for faster processing
  - boyer-moore algorithm
  - computing minimum edit distance between two strings