CS103I. Data Structures and Algorithms
Builds on the foundation provided by the CS101I-102I sequence to introduce the fundamental concepts of data structures and the algorithms that proceed from them. Topics include recursion, the underlying philosophy of object-oriented programming, fundamental data structures (including stacks, queues, linked lists, hash tables, trees, and graphs), the basics of algorithmic analysis, and an introduction to the principles of language translation.
Prerequisites: CS102I; discrete mathematics at the level of CS105 is also desirable.
Syllabus:
- Review of elementary programming concepts
- Fundamental data structures: Stacks; queues; linked lists; hash tables; trees; graphs
- Object-oriented programming: Object-oriented design; encapsulation and information hiding; classes; separation of behavior and implementation; class hierarchies; inheritance; polymorphism
- Fundamental computing algorithms: O(N log N) sorting algorithms; hash tables, including collision-avoidance strategies; binary search trees; representations of graphs; depth- and breadth-first traversals
- Recursion: The concept of recursion; recursive mathematical functions; simple recursive procedures; divide-and-conquer strategies; recursive backtracking; implementation of recursion
- Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; identifying differences among best, average, and worst case behaviors; big "O," little "o," omega, and theta notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms; using recurrence relations to analyze recursive algorithms
- Algorithmic strategies: Brute-force algorithms; greedy algorithms; divide-and-conquer; backtracking; branch-and-bound; heuristics; pattern matching and string/text algorithms; numerical approximation algorithms
- Overview of programming languages: Programming paradigms
- Software engineering: Software validation; testing fundamentals, including test plan creation and test case generation; object-oriented testing
Units covered:
| DS5 | Graphs and trees | 2 | core hours (of 4) |
| PF3 | Fundamental data structures | 12 | core hours (of 14) |
| PF4 | Recursion | 5 | core hours |
| AL1 | Basic algorithmic analysis | 2 | core hours (of 4) |
| AL2 | Algorithmic strategies | 3 | core hours (of 6) |
| AL3 | Fundamental computing algorithms | 5 | core hours (of 12) |
| AL5 | Basic computability | 1 | core hour (of 6) |
| PL1 | Overview of programming languages | 1 | core hour (of 2) |
| PL6 | Object-oriented programming | 8 | core hours (of 10) |
| SE6 | Software validation | 1 | core hour (of 3) |
Notes:
This course represents the third and final semester of an imperative-first introductory track that covers the fundamental programming concepts in three semesters rather than two. The rationale for including the three-course sequence CS101I-102I-103I as an alternative to the more traditional two-semester sequence CS111I-112I is summarized in the notes for CS101I and discussed in detail in Chapter 7 of the main report.
Online resources for CS103I