CS111A. Introduction to Algorithms and Applications

Prerequisites: none

Syllabus:

• Background: History of technology and human thought, including technology as a catalyst of paradigmatic change; history of computing
• Algorithms and problem-solving: Problem-solving strategies; the role of algorithms in the problem-solving process; the concept and properties of algorithms; pseudocode descriptions of algorithms
• Introduction to recursion: The concept of recursion; recursive mathematical functions; simple recursive procedures; divide-and-conquer strategies
• Fundamental programming constructs: Variables, types, expressions, and assignment; conditional and iterative control structures; abstraction using functions and procedures
• Fundamental data structures: Primitive types; arrays; records; the idea of type abstraction
• Introduction to object-oriented programming: Object-oriented design; encapsulation and information-hiding; separation of behavior and implementation; classes and subclasses; inheritance; polymorphism
• Fundamental computing algorithms: Simple numerical algorithms; sequential and binary search algorithms; sorting algorithms
• Basic algorithmic analysis: Introduction to computational complexity; 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
• Basic computability: Tractable and intractable problems; uncomputable functions; the halting problem; implications of uncomputability; the limits of computing

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)
PF4	Recursion	3	core hours (of 5)
AL1	Basic algorithmic analysis	2	core hours (of 4)
AL2	Algorithmic strategies	2	core hours (of 6)
AL3	Fundamental computing algorithms	2	core hours (of 12)
AL5	Basic computability	1	core hour (of 6)
AL6	The complexity classes P and NP	1	hour
PL1	Overview of programming languages	1	core hour (of 2)
PL5	Abstraction mechanisms	2	core hours (of 3)
PL6	Object-oriented programming	4	core hours (of 10)
SP1	History of computing	1	core hour
SE1	Software design	2	core hours (of 8)
SE5	Software requirements and specifications	1	core hour (of 4)

Notes:
This course has a three-part agenda:

1. It introduces key algorithmic concepts and constructs apart from any particular programming language and without executable performance requirements. Students learn to construct and analyze algorithms in the context of a pseudocode that is executable only "by hand and mind." This permits students to distinguish between essential concepts/constructs and the features of any particular programming language. The absence of execution requirements permits comparatively rapid progress through the range of concepts and constructs essential to functional, imperative, and object-oriented paradigms.
2. Concurrent with the first agenda item, it introduces students to essential computing applications in order to (a) provide students with hands-on computing experience to complement the "by hand and mind" approach of the first item, (b) explicate the power of, and need for, abstraction in contexts other than traditional programming contexts, and (c) provide students with a foundation in powerful abstraction-based approaches to using such applications.
3. Subsequent to the first two agenda items, once students have experience in reasoned algorithmic development, tracing, and analysis, the course's lecture and project agendas merge, providing an introduction to applying these concepts and constructs in the context of a modern, production-quality programming environment.

The lecture-and-homework agenda emphasizes abstraction, algorithm construction and algorithm analysis in the context of a non-executable pseudocode. The lab-and-project agenda emphasizes the development of both application-use and programming skills, with an focus on abstraction as a key component in the successful use of applications and programming languages. The goal is to provide students with a broad foundation that explicates essential algorithmic constructs and their effective use in a language-independent way, thus preparing students for a fast-paced "Introduction to Programming" in any of a variety of programming languages and paradigms.

Online resources for CS111A