CS 515: Data Structures

(Coordinator: Karen Jin)

Catalog description

This class has a number of goals: to provide an introduction to the C++ programming language; to provide an introduction to address and dynamic memory manipulation; to provide an introduction to the analysis of algorithms; to introduce a number of sorting algorithms; to introduce more advanced data structures; and to provide an insight as to how the basic and advanced data structures may be implemented. Prereq: CS 416.

Attributes

  • This course is one of the required courses for CS majors.

Outcomes

  • methodologies of software development: Object-oriented programming; software testing and debugging.
  • principles of data structures: implementation of basic to more advanced data structures; use appropriate data structures and Abstract Data Types (ADTs) under a given set of constraints.
  • fundamental computer science algorithms: Understand and apply algorithms to solve moderately complex problems; understand algorithm classes such as backtracking, divide-and-conquer, dynamic programming, randomized algorithms and greedy algorithms.
  • concepts of programming languages: C++ programming language.
  • think abstractly and reason logically about computer science problems: Determine the efficiency category of algorithms (including sorts and searches), data structure operations, and code segments using big O notation. Evaluate trade-offs in data structure and algorithm selection.

Evaluation

Weekly programming assignments (40%), weekly labs (25%), midterm exam (15%) and final exam (20%).

Topics

  • C++ fundamentals and language features:
    • basic C++, memory model, pointers and reference types, file I/O
    • functions and parameter passing; object and class;
    • class and function template; standard template library
    • operator overloading;
    • inheritance and polymorphism
  • Abstract Data Types (ADTs) and concrete data structures:
    • basic data structures: linked-list, stack, queue, binary search tree
    • introduction to amortized analysis.
    • skiplists and introduction to randomized algorithms.
  • map and set ADTs:
    • implementation with balanced search tree
    • AVL tree, red-black tree, 2–3–4 tree, B-tree
  • hashing:
    • hash function, collision resolution, closed hashing and open addressing
    • Cuckoo hashing
    • map ADT and set ADT using hash tables, performance analysis and comparison.
  • priority queue ADT:
    • binary heap, Floyd algorithm
    • implement priority queue using a binary heap
  • trie:
    • map ADT and set ADT using tries, performance analysis and comparison.
    • Hoffman encoding and introduction to greedy algorithms
  • sorting algorithms:
    • tree sort, heap sort, merge sort and quicksort
    • lower bound of comparison based sorting algorithms
    • bucket sort and radix sort
  • graph algorithms:
    • graph representations, depth-first and breadth-first graph traversals
    • minimal spanning tree algorithms: Kruskal’s algorithm, Prim’s algorithm
    • shortest path algorithms: Dijkstra’s algorithm, Folyd-Warshall’s algorithm, Bellman-Ford’s algorithm
    • introduction to dynamic programming algorithms.

Textbooks

Recommended:

  • Mark Allen Weiss. Data Structures and Algorithm Analysis in C++, 4th edition, 2013.
  • Stanley Lippman et al. C++ Primer, fifth edition, 2012.