CS103O. Algorithms and Data Structures
Builds on the introduction to object-oriented programming begun in CS101O and CS102O with an emphasis on algorithms, data structures, and software engineering.
Prerequisites: a href="102O.html">CS102O
Syllabus:
- Review of object-oriented design
- Review of basic algorithm design
- Review of professional and ethical issues
- Algorithms and problem-solving: Classic techniques for algorithm design; problem-solving in the object-oriented paradigm; application of algorithm design techniques to a medium-sized project, with an emphasis on formal methods of testing
- Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; identifying differences among best, average, and worst case behaviors; big "O" notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms
- Recursion: The concept of recursion; recursive mathematical functions; simple recursive procedures; divide-and-conquer strategies; recursive backtracking; implementation of recursion; recursion on trees and graphs
- Fundamental computing algorithms: Hash tables; binary search trees; representations of graphs; depth- and breadth-first traversals; shortest-path algorithms; transitive closure; minimum spanning tree; topological sort
- Fundamental data structures: Pointers and references; linked structures; implementation strategies for stacks, queues, and hash tables; implementation strategies for graphs and trees; strategies for choosing the right data structure
- Software engineering: Software project management; building a medium-sized system, in teams, with algorithmic efficiency in mind
Units covered:
| PF2 | Algorithms and problem-solving | 3 | core hours (of 6) |
| PF3 | Fundamental data structures | 11 | core hours (of 14) |
| PF4 | Recursion | 6 | hours (5 core + 1) |
| AL1 | Basic algorithmic analysis | 3 | core hours (of 4) |
| AL2 | Algorithmic strategies | 6 | core hours |
| AL3 | Fundamental computing algorithms | 5 | core hours (of 12) |
| SE1 | Software design | 1 | core hour (of 8) |
| SE8 | Software project management | 1 | core hour (of 3) |
| | Elective topics | 4 | hours |
Notes:
This course represents the third and final semester of an objects-first introductory track that covers the fundamental programming concepts in three semesters rather than two. The rationale for including the three-course sequence CS101O-102O-103O as an alternative to the more traditional two-semester sequence CS111O-112O is summarized in the notes for CS101O and discussed in detail in Chapter 7 of the main report.
Online resources for CS103O