jagomart
digital resources
picture1_Programming Pdf 185167 | 5 Dp Item Download 2023-02-01 13-18-13


 176x       Filetype PDF       File size 0.24 MB       Source: www.cse.unsw.edu.au


File: Programming Pdf 185167 | 5 Dp Item Download 2023-02-01 13-18-13
dynamic programming reminder algorithmic complexity dynamic programming what is dynamic comp4128 programming challenges programming dponatree exponential dp dpwith data structures school of computer science and engineering more example unswaustralia problems ...

icon picture PDF Filetype PDF | Posted on 01 Feb 2023 | 2 years ago
Partial capture of text on file.
   Dynamic
  Programming
 Reminder:
 Algorithmic
 Complexity                    Dynamic Programming
 What is
 dynamic                   COMP4128 Programming Challenges
 programming?
 DPonatree
 Exponential
 DP
 DPwith Data
 Structures                  School of Computer Science and Engineering
 More example                          UNSWAustralia
 problems
                  Table of Contents                                                                              2
    Dynamic
  Programming
                    1   Reminder: Algorithmic Complexity
 Reminder:
 Algorithmic
 Complexity
                    2   What is dynamic programming?
 What is
 dynamic
 programming?
 DPonatree          3   DPonatree
 Exponential
 DP                 4   Exponential DP
 DPwith Data
 Structures
 More example       5   DPwith Data Structures
 problems
                    6   More example problems
            Reminder: Algorithmic Complexity                                  3
   Dynamic
  Programming
                   The running time of your solution is important!
 Reminder:         If you don’t think about the time complexity of your
 Algorithmic       algorithm before coding it up, sooner or later you’ll end up
 Complexity
 What is           wasting a lot of time on something something that’s too
 dynamic           slow.
 programming?
 DPonatree             This is especially tragic in exam environments.
 Exponential       For simple code, analysing complexity can be as simple as
 DP                multiplying together the bounds of nested for loops.
 DPwith Data
 Structures        For recursive solutions, a rough bound is
 More example      O(time spent in recursive function ×
 problems
                                                recursion depth
                   number of recursion branches              )
                   For DP, it usually comes down to carefully determining the
                   state space and cost of recursion.
            Reminder: Algorithmic Complexity                                  4
   Dynamic
  Programming
                   On most online judges (this applies to the problem sets), a
 Reminder:         rough guideline is 50 million operations per second.
 Algorithmic
 Complexity            Constant factors occasionally matter, e.g. if you have no
 What is               recursion, or only tail-recursion, you might manage more
 dynamic
 programming?          operations than this.
 DPonatree             If you do float arithmetic, everything will be slow
 Exponential       This means that for n ≤ 1,000,000, an O(nlogn)
 DP
                   algorithm will probably run in time, but an O(n2)
 DPwith Data
 Structures        algorithm will definitely time out.
 More example
 problems          Best way to get a gauge of an online judge’s speed is to
                   submit a simple for loop and compare the number of
                   iterations it can do in 1 second to your local environment.
The words contained in this file might help you see if this file matches what you are looking for:

...Dynamic programming reminder algorithmic complexity what is comp challenges dponatree exponential dp dpwith data structures school of computer science and engineering more example unswaustralia problems table contents the running time your solution important if you don t think about algorithm before coding it up sooner or later ll end wasting a lot on something that s too slow this especially tragic in exam environments for simple code analysing can be as multiplying together bounds nested loops recursive solutions rough bound o spent function recursion depth number branches usually comes down to carefully determining state space cost most online judges applies problem sets guideline million operations per second constant factors occasionally matter e g have no only tail might manage than do oat arithmetic everything will means n an nlogn probably run but denitely out best way get gauge judge speed submit loop compare iterations local environment...

no reviews yet
Please Login to review.