• Home
  • Timetable and lecture rooms
  • Lab slides
  • News
  • Office hours
  • Tutoring
  • References
    • Part A References
    • Part B References
    • Editors
    • Further readings
  • Exams
    • Past exams
    • Exam modalities
    • Expectations
    • Grading
    • Exams FAQ
    • Exams How To
      • How to edit and run
      • Debugging
  • Acknowledgements
• Past Exams
  • Data science
    • Exam - Mon 06, Sep 2021
      • Download exercises and solutions
      • Part A - I CHING Divination
      • A1 load_db
      • A2 divine
      • A3 plot_divination
      • Part B
      • B1 Theory
        • B1.1 Complexity
        • B1.2 nlogn
      • B2 Train race
      • B3 linked algebra
    • Exam - Mon 12, Jul 2021
      • Download exercises and solutions
      • Part A - DOOM
      • A1 parse_map
      • A2 simulate
      • A3 plot_map
      • Part B
      • B1 Theory
        • B1.1 Complexity
        • B1.2 Hash
      • B2 PyraStack
      • B3 union_rec
    • Exam - Fri 11, Jun 2021
      • Download exercises and solutions
      • Part A - Trans-Atlantic Slave Trade
      • A1 read_trade
      • A2 Deportation
      • A3 The time to stop
      • Part B
      • B1 Theory
        • B1.1 Complexity
        • B1.2 Graph
      • B2 - is_heap_stack
      • B3 - sepel
    • Exam - Wed 10, Feb 2021
      • Download exercises and solutions
      • Part A - Wikispeedia
      • A1 filter_back
      • A2 load_db
      • A3 calc_stats
      • A4 plot_network
      • Part B
      • B1.1 Theory - Complexity
      • B1.2 Theory - BST
      • B2 Reconstruct BinaryTree
      • B3 Marvelous
    • Exam - Tue 14, Jan 2021
      • Download exercises and solutions
      • Part A - Witchcraft
      • A1 parse_bool_cols
      • A2 fix_date
      • A3 parse_db
      • A4 plot_cases
      • Part B
      • B1.1 Theory - Complexity
      • B1.2 Theory - Graph
      • B2 Bank
      • B2.1 constructor, log and pos
      • B2.2 revert
      • B2.3 max_interval
    • Midterm B - Wed 16, Dec 2020
      • Download exercises and solutions
      • Introduction
        • What to do
      • B1 Theory
        • B1.1. complexity
        • B1.2 dag topsort
      • B2 LinkedList pivot
      • B3 swap_stack
      • B4 family_sum_rec
    • Midterm A - Fri 06, Nov 2020
      • Download exercises and solutions
      • Music Sequencer
      • 1. parse_melody
      • 2. parse_tunes
      • 3. sequencer
      • 4. plot_tune
    • Midterm Sim - Mon 02, Nov 2020
      • Download exercises and solutions
        • What to do
      • Part A - Galactic Love
      • parse_stars
      • plot_stars 1
      • plot_stars 2 - new_center
      • parse_zodiac
      • plot_love
    • Exam - Mon 24, Aug 2020
      • Download exercises and solutions
      • Introduction
        • What to do
      • Part A - Prezzario
        • Pompa completa a motore Example
      • A1 extract_bounds
      • A2 extract_product
      • A3 plot_product
      • Part B
      • B1 Theory
        • B1.1 complexity
        • B1.2 describe
      • B2 couple_sort
      • B3 schedule_rec
    • Exam - Fri 17, Jul 2020
      • Download exercises and solutions
      • Introduction
        • What to do
      • Part A - NACE codes
        • Sections
        • Section detail
        • Specifications
        • NACE CSV
      • A1 Extracting codes
      • A1.1 is_nace
      • A1.2 extract_codes
      • A2 build_db
      • A3 plot
      • Part B
        • B1.1 complexity
        • B1.2 describe
      • B2 - OfficeQueue
      • B2.1 - time_to_service
        • Services not required by any client
      • B2.2 split
    • Exam - Tue 16, Jun 2020
      • Download exercises and solutions
      • Introduction
        • What to do
      • Part A - Zoom surveillance
        • CSV format
        • A1 time24
        • A2 load
        • A3.1 duration
        • A3.2 calc_stats
        • A4 viz
      • Part B
      • B1 Theory
        • B1.1 complexity
        • B1.2 describe
      • B2 - LinkedList slice
        • Special cases
      • B3 BinaryTree prune_rec
    • Exam - Mon 10, Feb 2020
      • Download exercises and solutions
      • Introduction
        • What to do
      • Part A
      • A1 parse_db
        • Field description
        • implement parse_db
      • A2 to_adj
        • Check results
      • A.3 hist
      • Part B
      • B1 Theory
        • B1.1 complexity
        • B1.2 graph visits
      • B2 ItalianQueue v2
      • B2.1 enqueue
      • B2.2 dequeue
    • Exam - Thu 23, Jan 2020
      • Download exercises and solution
      • Introduction
        • What to do
      • Part A
      • Metamath
        • Metamath db
      • A.1 Metamath db
      • A.2 Metamath proof
        • Checking proof
          • Overview plot
          • Detail plot
      • A.3 Metamath top statements
        • A3.1 histogram
        • A3.2 print list
      • Part B
      • B1 Theory
        • B1.1 my_fun
        • B1.2 differences
      • B2 plus_one
      • B3 add_row
    • Midterm B - Fri 20, Dec 2019
      • Download exercises and solution
      • Introduction
        • What to do
      • Part B
      • B1 Theory
        • B1.1 Complexity
        • B1.2 Data structure choice
      • B2 LinkedList
      • B2.1 rotate
      • B2.2 rotaten
      • B3 Binary trees
      • B3.1 sum_leaves_rec
      • B3.2 leaves_stack
    • Midterm - Thu 07, Nov 2019
      • Download exercises and solution
      • Introduction
        • Grading
        • Valid code
        • How to edit and run
        • Debugging
        • What to do
      • Part A
      • A.1 leap_year
      • A.2 full_date
      • A.3 partial_date
      • A.4 parse_dates_and
      • A.5 Fake news generator
    • Midterm sim - Tue 31, October 2019
      • Introduction
      • Part A - EURES Job Offers
      • MOVED TO en.softpython.org/pandas/eures-jobs-sol.html
    • Exam - Mon 26, Aug 2019
      • Download exercises and solution
      • Introduction
        • Grading
        • Valid code
        • How to edit and run
        • Debugging
        • What to do
      • Part A - University of Trento staff
        • A1 calc_uid_to_abbr
        • A2.1 calc_prof_roles
        • A2.2 plot_profs
        • A3.1 calc_roles
        • A3.2 plot_roles
        • A4.1 calc_shared
        • A4.2 plot_shared
      • Part B
      • B1 Theory
      • B2 Backpack
        • B2.1 class
        • B2.2 remove
      • B.3 Concert
        • B3.1 dequeue
          • Special dequeue case: broken group
    • Exam - Tue 02, July 2019
      • Download exercises and solution
      • Introduction
        • Grading
        • Valid code
        • How to edit and run
        • Debugging
        • What to do
      • Part A
      • A1 Botteghe storiche
        • A1.1 rank_categories
        • A1.2 plot
        • A1.3 enrich
      • A2 dump
      • Part B
      • B1 Theory
      • B2 Linked List sorting
        • B2.1 bubble_sort
        • B2.2 merge
      • B3 Stacktris
        • B3.1 _shorten
        • B3.2 drop1
        • B3.3 drop2h
    • Exam - Mon 10, Jun 2019
      • Download exercises and solution
      • Introduction
        • What to do
      • Part A
      • A1 ITEA real estate
        • A1.1 calc_types_hist
        • A1.2 calc_types_series
        • A1.3 Real estates plot
      • A2 Air quality
      • Part B
      • B1 Theory
      • B2 WStack
        • B2.1 implement class WStack
        • B2.2 accumulate
      • B3 GenericTree
      • B3.1 is_triangle
      • B3.2 has_triangle
    • Exam - Wed 13, Feb 2019
      • Download exercises and solution
      • Introduction
        • What to do
      • Part A - Bus network visualization
        • Colors and additional attributes
        • load_stops
        • A1 extract_routes
        • A2 to_int_min
        • A3 get_legend_edges
        • A4 calc_nx
        • A5 color_hubs
        • A6 plot_timings
      • Part B
      • B.1 Theory
      • B2 Company queues
        • B2.1 add_employee
        • B2.2 add_task
        • B2.2 work
      • B3 GenericTree
      • B3.1 fill_left
      • B3.2 follow
    • Exam - Wed 23, Jan 2019
      • Download exercises and solution
        • What to do
      • Part A
      • A.1 table_to_adj
      • A.2 bus stops
      • Part B
      • B.1 Theory
      • B.2 Linked List flatv
      • B.3 Generic Tree rightmost
    • Midterm - Thu 10, Jan 2019
      • Download exercises and solution
        • What to do
      • Introduction
      • B1 Theory
      • B2 Gaps linked list
      • B3 Tasks stack
        • B3.1 do
        • B3.2 do_level
      • B4 Exits graph
        • B4.1 cp
        • B4.2 exits
    • Midterm - Fri 16 Nov 2018
      • Download exercises and solution
      • Introduction
        • What to do
        • A1 union
      • A2 surjective
        • A3 ediff
    • Midterm Sim - Tue 13, Nov 2018
      • Download exercises and solution
      • Introduction
        • What to do
      • 1. matrices
        • 1.1 fill
        • 1.2 lab
      • 2. phones
        • 2.1 canonical
        • 2.2 prefix
        • 2.3 hist
        • 2.4 display calls by prefixes
  • 2017-18 (QCB)
  • 2016-17 (QCB)
• Slides 2021/22
  • Part A
  • Lab A.1
    • Links
  • Lab A.2
  • Lab A.3
  • Lab A.4
    • (sets)
    • Dictionaries
    • Conditionals
    • only for the pros
  • Lab A.5
    • In class:
    • At home:
  • Lab A.6
    • In class:
    • At home:
  • Lab A.7
    • In class:
• Commandments
  • MOVED TO https://en.softpython.org/commandments.html
• Part A
  • Installation
    • Visual Studio Code
    • The debugger
    • VS Code - collaborative coding
    • VS Code - Sharing test runs
  • Python basics
    • MOVED TO en.softpython.org/basics/basics-sol.html
  • Strings
    • MOVED TO https://en.softpython.org/#strings
  • Lists
    • MOVED TO https://en.softpython.org/#lists
  • Tuples
    • MOVED TO https://en.softpython.org/tuples/tuples-sol.html
  • Sets
    • MOVED TO https://en.softpython.org/sets/sets1-sol.html
  • Dictionaries
    • MOVED TO https://en.softpython.org/#dictionaries
  • Control flow
    • MOVED TO https://en.softpython.org/#control-flow
  • Functions
    • Download exercises zip
    • Introduction
      • What to do
      • What is a function ?
    • Namespace and variable scope
    • Argument passing
      • Positional arguments
      • Passing arguments by keyword
      • Specifying default values
    • Simple exercises
      • sum2
      • comparep
      • comparer
      • even
      • gre
      • is_vocal
      • sphere_volume
      • ciri
      • age
    • Verify comprehension
      • gre3
      • final_price
      • arrival_time
    • Lambda functions
      • Exercises: lambdas
      • apply_borders
      • process
  • Errors and testing
    • Testing
      • Where Is Your Software?
      • even_numbers example
        • Let’s add assertions
      • Error kinds
        • Error kind a) An external user misuses you program.
        • Error kind b): Your code is just plain wrong
    • Testing with Unittest
      • Running tests
      • When tests don’t run
      • Adding tests
      • Exercise: boundary cases
      • Exercise: expecting assertions
      • Exercise: good tests
      • Running unittests in Visual Studio Code
      • TROUBLESHOOTING
    • Functional programming
  • Matrices: lists
    • Moved to https://en.softpython.org/matrices-lists/matrices-lists1-sol.html
  • Matrices: numpy
    • Moved to https://en.softpython.org/matrices-numpy/matrices-numpy-sol.html
  • Data formats
    • MOVED TO https://en.softpython.org/formats/formats-sol.html
  • Graph formats
    • Moved to https://en.softpython.org/formats/formats4-graph-sol.html
  • Visualization
    • Moved to https://en.softpython.org/visualization/visualization-sol.html
  • Pandas
    • Moved to https://en.softpython.org/pandas/pandas1-sol.html
  • Binary relations
    • MOVED TO https://en.softpython.org/binary-relations/binary-relations-sol.html
• Part B
  • OOP
    • Download exercises zip
    • What to do
    • 1. Abstract Data Types (ADT) Theory
      • 1.1. Intro
      • 1.2. Complex number theory
      • 1.3. Datatypes the old way
      • 1.4. Finding the pattern
      • 1.5. Object Oriented Programming
    • 2. ComplexNumber class
      • 2.1. Class declaration
      • 2.2. Constructor __init__
      • 2.3. Defining methods
        • 2.3.1 phase
        • 2.3.2 log
        • 2.3.3 __str__ for printing
      • 2.4. ComplexNumber code skeleton
      • 2.5. Complex numbers magnitude
      • 2.6. Complex numbers equality
      • 2.7. Complex numbers isclose
      • 2.8. Complex numbers addition
      • 2.9. Adding a scalar
      • 2.10. Complex numbers multiplication
    • 3. MultiSet
    • 3.1 __init__ add and get
    • 3.2 removen
      • 4. Challenges
  • OOP Matrix Challenge
    • Download exercises zip
    • What to do
    • DenseMatrix
    • Constructors and printing
      • Constructor as list of lists
      • str and repr
      • constructor as list of triplets
    • shape
    • Brackets operator
    • nonzero
    • isclose
    • Equality
    • Sum
    • Multiplication
      • Matrix vector multiplication
      • Vector matrix multiplication
      • Matrix matrix multiplication
    • SparseMatrix
    • Sparse constructors and printing
    • Sparse shape
    • Sparse Brackets operator
    • Sparse nonzero
    • Sparse isclose
    • Sparse equality
    • Sparse sum
    • Sparse multiplication
      • Sparse matrix vector multiplication
      • Sparse vector matrix multiplication
  • Algorithm analysis and recursion
    • Introduction
    • List performance
      • Fast or not?
      • Sublist iteration performance
    • Some formulas
    • Lists - exercises
      • Exercise - rollsroyce
      • Exercise - honda
      • Exercise - lamborghini
      • Exercise - maserati
      • Exercise - toyota
      • Exercise - mercedes
      • Exercise - acura
      • Exercise - alfaromeo
      • Exercise - jeep
      • Exercise - chevrolet
      • Exercise - kia
      • Exercise - aston_martin
      • Exercise - subaru
      • Exercise - dodge
      • Exercise - lotus
      • Exercise - jaguar
      • Exercise - hyundai
      • Exercise - buick
      • Exercise - saab
    • Sets performance
    • Sets - exercises
      • Exercise - land_rover
      • Exercise - volkswagen
      • Exercise - pontiac
      • Exercise - volvo
      • Exercise - chrysler
    • Dictionaries performance
    • Dictionaries - exercises
      • Exercise - tesla
      • Exercise - bmw
      • Exercise - nissan
      • Exercise - ferrari
      • Exercise - bentley
      • Exercise - mclaren
      • Exercise - fiat
      • Exercise - mustang
    • Recursion
    • Recursion - exercises
      • Exercise - gap_rec
      • Exercise - yamaha
      • Exercise - mul2
      • Exercise - search_rec
      • Exercise - bin_search
      • Exercise - rev
      • Exercise - unnest
      • Exercise - cadillac
      • Exercise - ducati
    • Analysis - more exercises
    • Recursion - more exercises
  • Sorting
    • Download exercises zip
    • Introduction
      • References
      • What to do
    • Exercises
    • 1 Selection Sort
      • 1.1 Implement swap
      • 1.2 Implement argmin
      • 1.3: Full selection_sort
    • 2 Insertion sort
    • 3 Merge sort
      • Taking last element
        • Reversing a list
        • Removing last element with .pop()
      • Costly internal del
      • Costly internal pop
      • 3.1 merge 1
      • 3.2 merge2
    • 4 quick sort
      • 4.1 pivot
      • 4.2 quicksort and qs
    • 5 chaining
      • 5.1 has_duplicates
      • 5.2 chain
    • 6 SwapArray
      • 6.1 is_sorted
      • 6.2 max_to_right
      • 6.6 swapsort
    • Challenges
  • Sorting Challenge
    • Download exercises zip
    • Crime parade
    • McFat’s
    • Partitocracy
  • Linked lists
    • Download exercises zip
    • 0 Introduction
      • References
      • What to do
      • 0.1 Initialization
      • 0.2 Growing
      • 0.3 Visiting
    • 1 v1: a slow LinkedList
      • 1.a) Testing
      • 1.b) Differences with the book
      • 1.c) Please remember…
    • 2 v2 faster size
      • 2.1 Save a copy of your work
      • 2.2. Improve size
    • 3 v3 Faster append
      • 3.1 Save a copy of your work
      • 3.2 add _last field
      • 3.3 add method skeleton
      • 3.4 test driven development
      • 3.4.1 LastTest
      • 3.4.2 improve myAssert
      • 3.5 update methods that mutate the LinkedList
      • 3.6 Run tests
    • 4 v4 Go bidirectional
      • 4.1 Save your work
      • 4.2 Node backlinks
      • 4.3 Better str
      • 4.4 Modify add
      • 4.5 Add to_python_reversed
      • 4.6 Add invariant
      • 4.7 Modify other methods
      • 4.8 Run the tests
    • 5 EqList
      • 5.1 eq
      • 5.2 remsub
    • 6 Cloning
      • 6.1 rev
      • 6.2 clone
      • 6.3 Slice
        • Special cases
    • 7 More exercises
      • 7.1 occurrences
      • 7.2 shrink
      • 7.3 dup_first
      • 7.4 dup_all
      • 7.5 mirror
      • 7.6 norep
      • 7.8 find_couple
      • 7.9 swap
      • 7.10 gaps
      • 7.11 flatv
      • 7.12 bubble_sort
      • 7.13 merge
      • 7.14 couple_sort
    • 8 Last exercises
      • 8.1 rotate
      • 8.2 rotaten
      • 8.3 plus_one
    • Challenge
  • Linked lists Challenge
    • Download exercises zip
    • rshift
    • lshift
  • Stacks
    • Download exercises zip
    • 0. Introduction
      • References
      • What to do
    • 1. CappedStack
      • CappedStack Examples
      • Capped Stack basic methods
      • 1.1 __init__
      • 1.2 cap
      • 1.3 size
      • 1.4 __str__
      • 1.5 is_empty
      • 1.6 push
      • 1.7 peek
      • 1.8 pop
      • 1.9 peekn
      • 1.10 popn
      • 1.11 set_cap
    • 2. SortedStack
      • 2.1 transfer
      • 2.2 merge
    • 3. WStack
      • 3.1 implement class WStack
      • 3.2 accumulate
    • 4. Backpack
      • 4.1 class
      • 4.2 remove
    • 5. Tasks
      • 5.1 do
      • 5.2 do_level
    • 6. Stacktris
      • 6.1 _shorten
      • 6.2 drop1
      • 6.3 drop2h
  • Queues
    • Download exercises zip
    • Introduction
      • What to do
    • 1. LinkedQueue
      • 1.1 enqn
      • 1.2 deqn
    • 2. CircularQueue
    • 3. ItalianQueue
      • 3.1 Slow v1
      • 3.1.1 init
      • 3.1.2 Slow enqueue
      • 3.1.2 dequeue
      • 3.2 Fast v2
      • 3.2.1 Save a copy
      • 3.2.2 make it fast
    • 4. Supermarket queues
      • CashQueue
      • Supermarket
      • Supermarket as a queue
      • Implementation
      • 4.1 Supermarket size
      • 4.2 Supermarket dequeue
      • 4.3 Supermarket enqueue
    • 5. Shopping mall queues
      • Client
      • Shop
      • Mall
      • Mall as a queue
      • Implementation
      • 6.1 Mall enqueue
      • 6.2 Mall dequeue
    • 6. Company queues
      • 7.1 add_employee
      • 7.2 add_task
      • 7.3 work
    • 7. Concert
      • 7.1 dequeue
        • Special dequeue case: broken group
    • 8. OfficeQueue
      • 8.1 - time_to_service
        • Services not required by any client
      • 8.2 split
  • CircularQueue
    • Download exercises zip
    • 1. Introduction
    • 2. Example
    • 3. Circular span
    • 4. Implement CircularQueue
  • Binary Trees
    • Download exercises zip
    • 0. Introduction
      • What to do
    • 0. Introduction
      • 0.1 References
      • 0.2 Terminology - relations
      • 0.3 Terminology - levels
      • 0.4 Terminology - shapes
      • 0.2 Code skeleton
      • 0.3 Building trees
      • 0.3.1 Pointers
      • 0.3.2 Building with insert_left
      • 0.3.3 Building with bt
    • 1. Insertions
      • 1.1 insert_left
      • 1.2 insert_right
    • 2. Recursive visit
      • 2.1 sum_rec
      • 2.2 height_rec
      • 2.3 depth_rec
      • 2.4 contains_rec
      • 2.5 join_rec
      • 2.6 fun_rec
      • 2.7 bin_search_rec
      • 2.8 univalued_rec
      • 2.9 same_rec
      • 2.10 sum_leaves_rec
      • 2.11 schedule_rec
      • 2.12 paths
      • 2.12.1 paths_slow_rec
      • 2.12.2 paths_fast_rec
    • 3. Stack visit
      • 3.1 sum_stack
      • 3.3 height_stack
      • 3.3 leaves_stack
      • 3.4 others
    • 4. Queue visit
    • 5. Modifying the tree
      • 5.1 bin_insert_rec
      • 5.2 add_row
      • 5.3 prune_rec
  • Generic Trees
    • Download exercises zip
    • 0. Introduction
      • What to do
      • 0.1 References
      • 0.2 Code skeleton
      • 0.3 Building trees
      • 0.3.1 Pointers
      • 0.3.2 Building with insert_child
      • 0.3.3 Building with gt
      • 0.4 Displaying trees side by side with str_trees
      • 0.5 Look at the tests
      • 0.6 Look at gen_tree_test.GenericTreeTest
    • 1 Implement basic methods
      • 1.1 insert_child
      • 1.2 insert_children
      • 1.3 insert_sibling
      • 1.4 insert_siblings
      • 1.5 detach_child
      • 1.6 detach_sibling
      • 1.7 detach
      • 1.8 ancestors
    • 2 Implement more complex functions
      • 2.1 grandchildren
      • 2.2 Zig Zag
        • 2.2.1 zig
        • 2.2.2 zag
        • 2.2.3 zigzag
      • 2.3 uncles
      • 2.4 common_ancestor
      • 2.5 mirror
      • 2.6 clone
      • 2.7 rightmost
      • 2.8 fill_left
      • 2.9 follow
      • 2.10 is_triangle
      • 2.11 has_triangle
  • Graph algorithms
    • Download exercises zip
      • What to do
    • Introduction
      • 0.1 Graph theory
      • 0.2 Directed graphs
      • 0.3 Serious graphs
      • 0.4 Code skeleton
      • 0.5 Building graphs
      • 0.5.1 Building basics
      • 0.5.2 dig()
      • 0.6 Equality
      • 0.7 Basic querying
      • 0.7.1 adj
      • 0.7.2 is_empty()
      • 0.7.3 verteces()
      • 0.8 Blow up your computer
    • 1. Implement building
      • 1.1 has_edge
      • 1.2 full_graph
      • 1.3 dag
      • 1.4 list_graph
      • 1.5 star_graph
      • 1.6 odd_line
      • 1.7 even_line
      • 1.8 quads
      • 1.9 pie
      • 1.10 Flux Capacitor
    • 2. Manipulate graphs
      • 2.1 remove_vertex
      • 2.2 transpose
      • 2.3 has_self_loops
      • 2.4 remove_self_loops
      • 2.5 undir
    • 3. Query graphs
      • 3.1 distances()
      • 3.2 equidistances()
      • 3.3 Play with dfs and bfs
      • 3.4 Exits graph
      • 3.4.1 Exits graph cp
      • 3.4.2 Exit graph exits
      • 3.5 connected components
      • 3.6 has_cycle
      • 3.7 top_sort
  • Part B References
    • LeetCode for Part B
      • LeetCode LinkedLists
      • LeetCode Queues
      • LeetCode Trees
      • LeetCode Graphs
    • Geeks for geeks
      • Geeks for geeks Queues
      • Geeks for geeks Graphs
• Index