CS-A1120 Programming 2
Introduction
Round 1: Warmup
Sequences
Transforming sequences
Cascading
Recursion
Classes and objects
Module I: The mystery of the computer
Round 2: Bits and data
Introduction
Bits
Data
Data and its format
Types of data
Fixed-length data, words, word length
Variable-length data
Units of measure for data
Witnessing the bits, in Scala
Data and its format – a roadmap for this round
tellAboutX
- Functions that expose the bits
Numerical data
The positional number system
Beyond base 10
Binary, octal, decimal, hexadecimal
Serendipity of hexadecimal
Bit positions in a word
Hexadecimal in Scala
Forcing and toggling bits in a word
Shifting the bits in a word
Four basic tricks of the trade
Packing and unpacking bits
Numerical computation (*)
Radix point notation (*)
Floating point numbers (*)
Arbitrary-precision numbers (**)
Textual data (*)
Representing individual characters (*)
Character encodings (*)
Strings (*)
Formatted text (*)
Tables as text (*)
Structured objects as text (*)
Programs as text – syntax and parsing (**)
Context-free grammars (**)
Round 3: Combinational logic
Introduction
Building machines that compute with bits, from the bottom up
Logic gates
The power of combination
Building combinational logic in Scala
Playing with a circuit
The art of bottom-up design – a roadmap for this round
Gate-level design
Defining operators in Scala
Our first design – the half adder
Specification and implementation – the truth table and synthesis
Configurability – data and control
Efficiency – circuit depth and size (*)
Bus-level design
Customizing Scala collections
Convention on indexing the bits in a bus
Functional design – encapsulating code that builds subcircuits
Arithmetic with words
Unsigned addition
The ripple-carry adder
Unsigned multiplication
Fixed-length arithmetic and overflows (*)
Signed integers (*)
Refresher: Objects, references, and recursion recalled
Objects and references recalled
Recursion recalled
Round 4: Sequential logic, state and feedback
Introduction
State, evolving the state
Feedback
Upgrade from
tinylog
to
minilog
Our first design with sequential logic – the counter
Our second design – the accumulator-adder
Our third design – the accumulator-adder-subtracter
Towards understanding the computer
Building an instructable data path – a roadmap for this round
Sequential logic in Scala (*)
Designing with patterns (*)
Spotting common patterns in package
tinylog
(*)
Why
tinylog
needs upgrading (*)
Building feedback to an input element (*)
Implementing the clock signal functionality (*)
Registering all gates with a host (*)
Speeding up the simulation (*)
The art of designing with patterns (*)
The
armlet
data path
The
armlet
architecture overview
Registers and processor state
The arithmetic logic unit (ALU), first version
Extending the ALU – loading immediate data
Trigger
time with the ALU
The ALU in Scala (**)
Memory and the
armlet
(*)
Memory interface unit
The load completion unit (*)
Summary
The
armlet
instruction set
An instruction – a symbol in the alphabet of the machine
Binary representation of the
armlet
instructions (**)
The instruction decoder unit
Instructing the data path with
Trigger
Towards programmability
Round 5: A programmable computer
Introduction
Towards programmability
Storing the program in memory
Automating execution
Resolving the mystery of programmability – a roadmap for this round
The
armlet
processor
The data path
The program counter and processor status
The comparison instructions
Default flow of execution
The jump and branch instructions
Jumps and branches versus if-then-else, while, and such
Reset
Halt
Trap (debugging)
The
armlet
architecture (*)
Programming the
armlet
Our first
armlet
program
Assembly language
The assembler
A playful introduction to
Ticker
Beyond the first example
Scanning data
Sorting data
Some conventions and hints for the exercises
From Scala to hardware (*)
From Scala to bytecode for the Java Virtual Machine (*)
A second example (*)
Bytecode beyond our examples (**)
From bytecode to hardware (*)
Mystery resolved?
Software and hardware
The operating system (*)
Virtualization and simulation (*)
Programming environments (*)
Conclusion – it is important to understand hardware
Module II: Programming abstractions and analysis
Round 6: Collections and functions
Collections
Example: ArrayBuffer
Why so many collections?
Functions
Anonymous functions
Methods as functions
Side effects and pure functions
Using collections in functional style
forall
foreach
map
flatMap
groupBy
foldLeft
zip
indices and zipWithIndex
More on functions
Closure
Call-by-value and call-by-name
Iterators
Independent use: generators
Round 7: Efficiency
Resources and efficiency, with a focus on time
Measuring run time
Case: Operations on matrices
Growth rates of functions
Matrix operations revisited: Fitting a function
Typical functions
The Big O notation
Indexing and search
Disorder and order, searching
Linear search
Indexing and sorting
Binary search
Round 8: Recursion
Introduction
Recursion and tail recursion recalled
Example: Palindromes
Tail recursion
Linked lists
A first implementation
A second implementation with case classes
Expressions
Evaluation
Simplification
Solving problems recursively
The subset sum problem
A word on hard problems and NP-completeness
Module III: Frontiers
Round 9: Concurrency and parallelism
Introduction
A single thread of execution
Multiple threads
Why concurrency and multithreading?
Easy parallelism
Our first multithreaded program in Scala
Asynchronous execution
Synchronization
Why synchronization?
Independence and dependence
What can be computed in parallel?
A functional perspective
Independence
Dependence
Modelling dependence with directed acyclic graphs (DAGs)
Minimum makespan and scheduling
Parallel speedup and Amdahl’s law
What can be computed in parallel, revisited
Abstractions for easy parallelism
Futures and Promises
Round 10: Virtualization and scalability
Scaling up from a single computer
Computation becomes a commodity
Resiliency, partitioning, and dependence
What can be computed in a computer cluster?
Driver node and worker nodes
Hardware failures and resiliency
Partitioning and persistence (*)
Resilient distributed datasets
Transformations on RDDs
Actions on RDDs
Next step: Try it for yourself
An example of using Spark in Scala
Example context
The program
Round 11: Machines that learn?
Introduction
What is teaching? What is learning?
Generalisation from presented examples – a roadmap for this round
Generalisation beyond presented examples
Presented examples
Generalising into the unknown
The role of the programmer/teacher
Testing
Risks, rewards, and types of learning
Risks in learning
Serendipity of learning
Types of learning techniques
Appendix: Instructions
Using the Visual Studio Code editor
On Aalto Linux computers
Installation on personal computer
First things first
macOS
Linux
Windows 10 & 11
Setup
Workflow
Trouble-shooting
The
Test
and
Run
links don’t appear in my source code
Scala not found
Java not found
Error message about build server
sbt command not found
Error:
code: No such file or directory
(Aalto Linux workstation)
Error:
the following module(s) are unknown
(Aalto Linux workstation)
Warning: Code navigation will not work
Using the IntelliJ IDEA
Installing IntelliJ on your own computer
Fresh install
Installing the Scala language plugin
Working with the exercises
Running tests and code
Opening a Scala REPL
Trouble-shooting
scalac:
Token
not
found:
Some basic tasks
Downloading exercise projects
Submitting your solutions for grading
Opening an sbt console from the command line
Getting help
On-campus exercise sessions
Queuing for help
On-line exercise sessions
Zulip workspace
Using
Etiquette
Accessing the Aalto VDI remote desktop
Acknowledgements
CS-A1120 Programming 2
»
Index
Index