CS111I. Introduction to Programming

Prerequisites: No programming or computer science experience is required. Students should have sufficient facility with high-school mathematics to solve simple linear equations and to appreciate the use of mathematical notation and formalism.

Syllabus:

• Background: History of computing, overview of programming languages and the compilation process
• Fundamental programming constructs: Syntax and semantics of a higher-level language; variables, types, expressions, and assignment; simple I/O; conditional and iterative control structures; functions and parameter passing; structured decomposition
• Algorithms and problem-solving: Problem-solving strategies; the concept of an algorithm; properties of algorithms; implementation strategies; sequential and binary search algorithms; quadratic sorting algorithms (selection, insertion)
• Basic computability theory: Tractable and intractable problems; the existence of noncomputable functions
• Graphics: Using a graphics API
• Principles of encapsulation: Encapsulation and information-hiding; separation of behavior and implementation
• Fundamental data structures: Primitive types; arrays; records; strings and string processing; pointers and references; static, stack, and heap allocation; runtime storage management
• Machine level representation of data: Bits, bytes, and words; binary representation of integers; representation of character data; representation of records and arrays
• Assembly level machine organization: Basic organization of the von Neumann machine; instruction fetch, decode, and execution; assembly language programming for a simulated machine
• 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:

PF1	Fundamental programming constructs	9	core hours
PF2	Algorithms and problem-solving	3	core hours (of 6)
PF3	Fundamental data structures	6	core hours (of 14)
AL3	Fundamental computing algorithms	2	core hours (of 12)
AL5	Basic computability	1	core hour (of 6)
PL1	Overview of programming languages	1	core hour (of 2)
PL4	Declarations and types	1	core hour (of 3)
PL5	Abstraction mechanisms	2	core hours (of 3)
PL6	Object-oriented programming	3	core hours (of 10)
AR2	Machine level representation of data	1	core hour (of 3)
AR3	Assembly level machine organization	2	core hours (of 9)
GV1	Fundamental techniques in graphics	2	core hours
SP1	History of computing	1	core hour
SE1	Software design	2	core hours (of 8)
SE3	Software tools and environments	1	core hour (of 3)
SE5	Software requirements and specifications	1	core hour (of 4)
SE6	Software validation	1	core hour (of 3)
	Elective topics	1	hour

Notes:
This course introduces the fundamental concepts of programming, emphasizing the traditional procedural or imperative paradigm. Most modern programming languages are suitable as a foundation for the programming assignments in this course, including those that support the object-oriented paradigm; indeed, introductory courses that use object-oriented languages often begin by emphasizing the procedural aspects of those languages. What sets this course apart from the objects-first implementation in CS111O is the ordering and emphasis of topics. In this course, the discussion of control statements precedes the discussion of classes, subclasses, and inheritance; in the objects-first version, this ordering is reversed.

Just as the procedural aspects of programming can be taught in an object-oriented language, some of the fundamental principles of object-oriented programming can be included even in the context of a traditional imperative language. The syllabus topic entitled "Principles of encapsulation" makes sense in either domain, but would be approached differently depending on the language. In either case, this presentation would encompass some of the ideas in the PL6 unit on object-oriented programming.

Online resources for CS111I