CSE 247 502N Data Structures and Algorithms: course objectives - bsiever/WUSTL-CSE-Curriculum GitHub Wiki

Week 0: Array Expansion

  1. Have a better understanding of simple data structures
  2. Understand the concept of time complexity
  3. Know how to contact or find your instructor and TAs
  4. Navigate the course web site
  5. Understand the course structure
  6. Know how to use the Eclipse programming environment to:
  • check out a project from your repository
  • edit Java source code
  • correct compilation errors
  • execute programs
  • commit your work
  1. Know how to use the 'Ticker' class to quantify complexity

Week 1: Asymptotic Complexity

  1. Be able to count statements in simple nested loops
  2. Have an understanding of what asymptotic complexity is
  3. Be able to determine the leading term of a polynomial
  4. Have an understanding of what Big-O time-complexity is
  5. Be able to compare the asymptotic growth rates of two functions

Week 2: Simple Data Structures

  1. Be able to apply limit tests to compare the asymptotic growth of two functions
  2. Be able to distinguish the fastest/slowest among several algorithms given their asymptotic complexities
  3. Describe the functionality of a collection abstract data type
  4. Describe the operation of some basic data structures that can implement a collection ADT

Week 3: Priority Queues

  1. Be able to describe the interface of a priority queue ADT
  2. Be able to discern good vs. bad implementations of priority queues
  3. Understand the implementation and use of heaps
  4. Be able to perform the fundamental heap operations
  5. Be able to create a heap from a set of ordered values
  6. Know how to implement a binary heap using an array

Weeks 4/5: Recurrences

  1. Know how to describe the running time of a recursive program with a recurrence
  2. Be able to use substitution to confirm a closed-form solution to a recurrence
  3. Know how binary search works
  4. Be able to sketch recursion trees and use them to solve a recurrence
  5. Be able to use the master method to solve recurrences
  6. Be able to determine when the master method is applicable to a recurrence

Week 6: Sorting

  1. Be able to enumerate some common sorting algorithms and their complexities
  2. Understand how the merge sort algorithm works
  3. Understand how the radix sort algorithm works
  4. Understand the basis of the comparison-sorting lower bound, and why it does not apply to radix sort

Weeks 7/8/9: Hashing

  1. Know why a direct table or hash table might be preferable to other implementations of a collection ADT
  2. Understand how to resolve collisions in a hash table by chaining
  3. Be able to explain the Simple Uniform Hashing assumption and why it is needed to ensure good average-case performance of hash table operations
  4. Know common strategies for converting integer-valued hashcodes to table indices, including both division and multiplicative hashing
  5. Know some strategies for converting non-integer objects to hashcodes
  6. Be able to articulate the difference in behavior between hashing a set and hashing a sequence
  7. Understand how to resolve collisions in a hash table by open addressing
  8. Be able to describe a hashDoS attack and to explain why most common hash functions are not resistant to a malicious attacker

Weeks 10/11: BSTs and Balanced BSTs

  1. List some fundamental operations supported by an ordered collection type
  2. Describe how to do these fundamental operations on a binary search tree
  3. Define "balance" in a tree and explain why it is important its performance as an ordered collection
  4. Explain how to efficiently maintain the height and/or size of each subtree in a tree under dynamic insertion and deletion
  5. List some properties that guarantee that a tree will be balanced
  6. Explain how to dynamically maintain these properties in a tree under insertion and deletion
  7. Explain how to do a rotation operation on a tree and why it is important for rebalancing
  8. Perform insertion and deletion in an AVL tree
  9. Perform insertion in a 234 tree

Week 12: Graph Searches (BFS and DFS)

  1. Understand graph terminology such as:
  • simple
  • connected
  • directed and undirected
  • dense and sparse
  1. Understand how to represent a graph using an
  • adjacency list
  • adjacency matrix
  1. Understand breadth-first and depth-first search
  2. Be able to perform both of these on a graph
  3. Know how to tell if a directed graph has a cycle
  4. Understand what a topological sort is
  5. Be able to apply topological sort to a directed acyclic graph

Week 13: Shortest Paths

  1. Understand how Dijkstra's shortest-paths algorithm works
  2. Be able to analyze its complexity on dense and sparse graphs, with a binary or Fibonacci heap
  3. Understand why priority queues are relevant to graph algorithms

Week 14: Greedy Algorithms

  1. Understand what is meant by term "greedy"
  2. Understand the definition of a minimum spanning tree for a graph
  3. Understand and be able to perform Prim's and Kruskal's MST algorithms
  4. Understand the asymptotic complexity of Prim's and Kruskal's algorithms
  5. Understand the general approach to proving a greedy algorithm correct