Sciprog DS Lab
dev
  • Home
    • Timetable and lecture rooms
      • Moodle
      • Zoom links
    • News
    • Slides
    • Office hours
    • Labs timetable
    • 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 12, Jul 2021
        • Download exercises and solutions
        • Part A - DOOM
        • A1 parse_map
        • A2 simulate
        • A3 plot_map
        • Part B
        • B1 Theory
        • 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
        • 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
        • B1 Theory
        • 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
        • 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
        • Part A - Prezzario
        • A1 extract_bounds
        • A2 extract_product
        • A3 plot_product
        • Part B
        • B1 Theory
        • B2 couple_sort
        • B3 schedule_rec
      • Exam - Fri 17, Jul 2020
        • Download exercises and solutions
        • Introduction
        • Part A - NACE codes
        • A1 Extracting codes
        • A1.1 is_nace
        • A1.2 extract_codes
        • A2 build_db
        • A3 plot
        • Part B
        • B2 - OfficeQueue
        • B2.1 - time_to_service
        • B2.2 split
      • Exam - Tue 16, Jun 2020
        • Download exercises and solutions
        • Introduction
        • Part A - Zoom surveillance
        • Part B
        • B1 Theory
        • B2 - LinkedList slice
        • B3 BinaryTree prune_rec
      • Exam - Mon 10, Feb 2020
        • Download exercises and solutions
        • Introduction
        • Part A
        • A1 parse_db
        • A2 to_adj
        • A.3 hist
        • Part B
        • B1 Theory
        • B2 ItalianQueue v2
        • B2.1 enqueue
        • B2.2 dequeue
      • Exam - Thu 23, Jan 2020
        • Download exercises and solution
        • Introduction
        • Part A
        • Metamath
        • A.1 Metamath db
        • A.2 Metamath proof
        • A.3 Metamath top statements
        • Part B
        • B1 Theory
        • B2 plus_one
        • B3 add_row
      • Midterm B - Fri 20, Dec 2019
        • Download exercises and solution
        • Introduction
        • Part B
        • B1 Theory
        • 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
        • 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
        • Part A - University of Trento staff
        • Part B
        • B1 Theory
        • B2 Backpack
        • B.3 Concert
      • Exam - Tue 02, July 2019
        • Download exercises and solution
        • Introduction
        • Part A
        • A1 Botteghe storiche
        • A2 dump
        • Part B
        • B1 Theory
        • B2 Linked List sorting
        • B3 Stacktris
      • Exam - Mon 10, Jun 2019
        • Download exercises and solution
        • Introduction
        • Part A
        • A1 ITEA real estate
        • A2 Air quality
        • Part B
        • B1 Theory
        • B2 WStack
        • B3 GenericTree
        • B3.1 is_triangle
        • B3.2 has_triangle
      • Exam - Wed 13, Feb 2019
        • Download exercises and solution
        • Introduction
        • Part A - Bus network visualization
        • Part B
        • B.1 Theory
        • B2 Company queues
        • B3 GenericTree
        • B3.1 fill_left
        • B3.2 follow
      • Exam - Wed 23, Jan 2019
        • Download exercises and solution
        • 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
        • Introduction
        • B1 Theory
        • B2 Gaps linked list
        • B3 Tasks stack
        • B4 Exits graph
      • Midterm - Fri 16 Nov 2018
        • Download exercises and solution
        • Introduction
        • A2 surjective
      • Midterm Sim - Tue 13, Nov 2018
        • Download exercises and solution
        • Introduction
        • 1. matrices
        • 2. phones
    • 2017-18 (QCB)
    • 2016-17 (QCB)
  • Slides 2020/21
    • Part A
    • Lab A.1
      • Links
        • What I expect
        • Course contents
    • Lab A.2
    • Lab A.3
    • Lab A.4
    • Lab A.5
    • Lab A.6
    • Lab A.7
    • Lab A.8
      • How to see graphviz on repl.it
    • Lab A.9
    • Lab A.10
    • Lab A.11
    • Lab A.12
    • Part B
    • Lab B.1
    • Lab B.2
    • Lab B.3
    • Lab B.4
    • Lab B.5
    • Lab B.6
    • Lab B.7
    • Lab B.8
    • Lab B.9
      • Lab B.10
  • 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/sets-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 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-lists-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/graph-formats/graph-formats-sol.html
    • Visualization
      • Moved to https://en.softpython.org/visualization/visualization-sol.html
    • Pandas
      • Moved to en.softpython.org/pandas/pandas-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.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
        • 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
      • 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
      • 8. OfficeQueue
        • 8.1 - time_to_service
        • 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.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
    • Changelog
      • 1.0 September 2020
      • 0.1, September 2018
  • Index
Sciprog DS Lab
  • Home
    • Timetable and lecture rooms
      • Moodle
      • Zoom links
    • News
    • Slides
    • Office hours
    • Labs timetable
    • 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 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 2020/21
    • Part A
    • Lab A.1
      • Links
        • What I expect
        • Course contents
    • Lab A.2
    • Lab A.3
    • Lab A.4
    • Lab A.5
    • Lab A.6
    • Lab A.7
    • Lab A.8
      • How to see graphviz on repl.it
    • Lab A.9
    • Lab A.10
    • Lab A.11
    • Lab A.12
    • Part B
    • Lab B.1
    • Lab B.2
    • Lab B.3
    • Lab B.4
    • Lab B.5
    • Lab B.6
    • Lab B.7
    • Lab B.8
    • Lab B.9
      • Lab B.10
  • 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/sets-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 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-lists-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/graph-formats/graph-formats-sol.html
    • Visualization
      • Moved to https://en.softpython.org/visualization/visualization-sol.html
    • Pandas
      • Moved to en.softpython.org/pandas/pandas-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
Next

© Copyright # 2020 - 2021, David Leoni

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