15-110: Principles of Computing
(Fall 2019)

Overview

As defined P. Denning et al. in an 1989 ACM report on Computing as a Discipline, computing is the "systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all computing is what can be (efficiently) automated?". This course precisely aims at introducing the science (and the art) of computing to students with little or no prior background in the matter.

Given the inherent vastity of the topics involved in computing, the course will focus on a subset of the core aspects of computing, providing a brief, yet substantial introduction to many topics. The goal is to provide an idea of what's possible and how to realize it when it's useful (or, most often, necessary) to employ computation and computers to accomplish a complex goal.

The course will balance the discussion of concepts central to design and understand computation with their practical implementation and testing using a specific programming language, Python. The choice of python is motivated by its widespread use, relative simplicity, availability of tools for scientific, graphical, and web programming, among others.

The course will take the student along the way that starts from a complex, possibly large problem to solve, and then move step by step to its abstraction, to its formalization into an algorithmic recipe, to the encoding of the algorithm using the constructs of the python language, to the run-time execution and error correction of the programming code, to the efficiency analysis of the developed algorithm and code. A number of practical application scenarios will be considered to ground the concepts to problems of interest.

In a nutshell, the course will tackle the following topics:

• Problem analysis: abstraction and representation
• Concepts central to design and understand algorithms
• Fundamental concepts of programming:
• Knowledge representation (data types and structures)
• Flow control (conditionals, iteration, recursion)
• Data organization (lists, matrices, dictionaries)
• Decomposition, reusability, information hiding (modules, functions, class objects)
• Python programming language to implement the above general concepts
• Computational problem-solving techniques (divide-and-conquer, greedy, dynamic programming)
• Correctness and efficiency of algorithms (testing, error finding, algorithmic complexity, optimization)
• Data visualization, animation, and statistical analysis
• Simulation models (deterministic and stochastic approaches)

While the theoretical understanding of the concepts is always fundamental, the course emphasizes hands-on, meaning that learning will be mostly driven by the repeated implementation and application in python of the general concepts.

Almost every class will feature some hands-on and/or solving excercises together with the teacher.

Homework will progressively and incrementally address more complicated problems, asking for designing and implementing relatively large and complex code.

Learning goals

• To achieve a broad understanding and a practical expertise of what computing is, and, more in general, of what computer science is.
• To develop the knowledge of what classes of problems computers are good at or are necessary for.
• To build the ability to analyze and abstract a given problem to represent it in a way which is ameneable to an algorithmic solution.
• To acquire the skills to step from a problem description, to a problem abstraction, to an effective algorithm, to an optimized computer program.
• To acquire the basic knowledge of some fundamental algorithmic solution techniques.
• To reach a proficiency level programming in Python using both procedural and object-oriented techniques.
• To become a skilled practioner for using computer programming to read, write, and process complex data.
• To achieve a clear understanding of the time and memory requirements of a specific algorithm, and, more in general, of the inherent limits of what a specific computer can solve.
• To know how to effectively use python programming for general-purpose tasks such as data visualization and design and execution of simulated experiments.

Prerequisites

None.

Credits

This is a 10 unit course.

Place and time

Schedule (Subject to changes)

In the table below, labs are in blue, exams are in red and the next lecture/lab is orange. Green days are in the past, and grey days have no lectures.

Staff