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. CS 1
- 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.) CS 1
- Implement various algorithms for searching and sorting, including linear search, binary search, insertion sort, selection sort, merge sort, quicksort, and heap sort. CS 1
- Read and write recursive algorithms, and determine when recursion is suitable. CS 1
- Describe an algorithm's asymptotic performance and its practical implications. CS 1
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.