CS112A. Programming Methodology

Prerequisites: CS111A

Syllabus:

• Review of elementary programming and data structures
• Overview of programming languages: History of programming languages; brief survey of programming paradigms; virtual machines
• Recursion: Divide-and-conquer strategies; recursive backtracking; game trees; implementation of recursion
• Fundamental data structures: Strings and string processing; data representation in memory; static, stack, and heap allocation; runtime storage management; 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
• Object-oriented programming: Review of basic concepts; object-oriented design; class hierarchies; collection classes and iteration protocols; internal representations of objects and method tables
• Event-driven programming: Event-handling methods; event propagation; exception handling
• Introduction to language translation: Comparison of interpreters and compilers; language translation phases; machine-dependent and machine-independent aspects of translation
• Algorithmic strategies: Brute-force algorithms; greedy algorithms; divide-and-conquer; backtracking; branch-and-bound; heuristics; pattern matching and string/text algorithms; numerical approximation algorithms
• Fundamental computing algorithms: Hash tables; binary search trees; representations of graphs; depth- and breadth-first traversals; shortest-path algorithms; transitive closure; spanning trees; topological sort; heaps
• Fundamental techniques in graphics: Using a graphics API; graphical user interfaces
• Introduction to cryptography: Historical overview of cryptography; private-key cryptography and the key-exchange problem; public-key cryptography; digital signatures
• Software development methodology: Fundamental design concepts and principles; structured design; testing and debugging strategies; test-case design; programming environments; testing and debugging tools

Units covered:

PF3	Fundamental data structures	5	core hours (of 14)
PF4	Recursion	2	core hours (of 5)
PF5	Event-driven programming	3	core hours (of 4)
AL2	Algorithmic strategies	2	core hours (of 6)
AL3	Fundamental computing algorithms	4	core hours (of 12)
AL9	Cryptographic algorithms	2	hours
PL1	Overview of programming languages	1	core hour (of 2)
PL2	Virtual machines	1	core hour
PL3	Introduction to language translation	2	core hours
PL4	Declarations and types	3	core hours
PL5	Abstraction mechanisms	1	core hour (of 3)
PL6	Object-oriented programming	4	core hours (of 10)
GV1	Fundamental techniques in graphics	2	core hours
SE1	Software design	2	core hours (of 8)
SE2	Using APIs	2	core hours (of 5)
SE3	Software tools and environments	2	core hours (of 3)
SE6	Software validation	1	core hour (of 3)
SE7	Software evolution	1	core hour (of 3)

Notes:
As specified in the description of CS111A, students in that course are exposed to the complete range of algorithmic concepts and constructs. This liberates the teaching-and-learning agenda of the current course to focus on effective programming skills, including systematic approaches to design, implementation, testing and debugging. It also permits students to proceed more rapidly through this agenda than might otherwise be possible, as they enter the course with a broad and appropriate conceptual foundation.

Transfer students who have had only a single CS course other than a href="111A.html">CS111A are likely to have difficulty in this course, as they will not likely have an adequate foundation. Except in exceptional circumstances, they should be counseled to obtain a remedial foundation in a href="111A.html">CS111A material prior to taking this course. Transfer students who have succeeded in alternate versions of both CS111 and CS112 are likely to succeed in this course and to appreciate its orientation to effective programming skills.

Online resources for CS112A