CSCI-C 310 Data Structures – Python
3 credits
- Prerequisite(s): CSCI-C 212 OR CSCI 24000 OR INFO-B 211 OR CSCI-A 205 AND CSCI-C 241 OR INFO-I 201 OR CSCI 34000
- Delivery: Online
- Semesters offered: Fall, Spring, Summer (Check the schedule to confirm.)
Description
The focus of this course is on solving computational problems that involve manipulating collections of data. We will study a core set of data abstractions, data structures, and algorithms that provide a foundation for writing efficient programs.
Topics
Introduction
- Overview of data structures
- Importance of data efficiency
Python primer
- Basic syntax
- Control structures
- Functions and modules
Software design
- Design principles
- Testing and debugging
- Version control
Object-oriented Python
- Classes and objects
- Inheritance
- Polymorphism
Algorithm analysis
- Big O notation
- Time complexity
- Space complexity
Array-based sequences
- Arrays
- Dynamic arrays
- Amortized analysis
- Efficiency of sequence operations
Stacks and queues
- Stack ADT
- Queue ADT
- Deques
- Applications
Lists
- Singly linked lists
- Doubly linked lists
- Circularly linked lists
Recursion
- Principles of recursion
- Recursion in practice
- Recursive backtracking
Sorting
- Insertion sort
- Selection sort
- Merge sort
- Quicksort
- Heap sort
Selection problem
- Selection algorithms
- Quick-select
- Analysis of selection
Trees
- Binary trees
- Tree traversal
- Expression trees
Search trees
- Binary search trees
- AVL trees
- Splay trees
Priority queues
- Abstract data type
- Implementing priority queues
Heaps and heap sort
- Binary heaps
- Heap operations
- Heap sort algorithm
Maps
- Abstract data type
- Unsorted and sorted maps
Hashing
- Hash tables
- Collision resolution
- Hash functions
Graphs
- Graph terminology
- Graph representations
- Graph algorithms (e.g., DFS and BFS)
Learning Outcomes
- Describe, explain, and use abstract data types, including stacks, queues, lists, sets, and maps.
- Implement those data types using both contiguous and linked representations. (Contiguous representation mechanisms include arrays and hash tables. Linked representation mechanisms include singly and doubly linked lists and trees.)
- Implement various algorithms for searching and sorting, including linear search, binary search, insertion sort, selection sort, merge sort, quicksort, and heap sort.
- Read and write recursive algorithms, and determine when recursion is suitable.
- Describe an algorithm's asymptotic performance and its practical implications.
Policies and Procedures
Please be aware of the following linked policies and procedures. Note that in individual courses instructors will have stipulations specific to their course.