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: 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: Tools and 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
      • On Aalto Linux computers
      • 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:
        • Package name ... does not correspond to...
    • Some basic tasks
      • Downloading exercise projects
      • Submitting your solutions for grading
      • Starting a Scala REPL
        • Opening a REPL in IntelliJ
        • Opening a REPL in a system terminal or VS Code
    • Getting help
      • On-campus exercise sessions
        • Queuing for help
      • Zulip workspace
        • Using
        • Etiquette
    • Accessing the Aalto VDI remote desktop
  • Acknowledgements
CS-A1120 Programming 2
  • »
  • Search

© Copyright 2013-2024, Petteri Kaski, Tommi Junttila, and Lukas Ahrenberg.

Built with Sphinx using a theme provided by Read the Docs.